CO454 Scheduling Theory, Spring 2009

Instructor: Deeparnab Chakrabarty (Office: MC4009, Email: deepc[at]uwaterloo.ca)
          Time: Tuesday - Thrusday 11:30am - 12:50pm
          Location: MC4060
          Office Hours: Fridays 11am - 1pm

Teaching Assistant: Irene Pivotto (Office: DC3145, Email: ipivotto[at]math.uwaterloo.ca)
          Office Hours: Tuesdays 3pm - 4pm, Fridays 2pm - 3pm
Home         Course Information         Announcements         Assignments, Solutions and Notes

  • ``Formula'' for Final Grades I am going to reweigh the grading scheme so that if you think you have not done well in-term, you can make-up with your end-term. However, I am not going to take the best of your in-term and end-term. Thus, getting a 0 in the in-term and 100 in the end-term won't give you 100. The final grade will be a weighted average of your in-term and end-term, where you can put more weight on your end-term by doing better on your end-term. I will not say the exact formula, although I could tell you, by email, how much you would need to get a pass-grade.


  • Graded HW6 assignments and all uncollected old assignments+midterm have been put in a box outside my office. I am going to keep two extra office hours (11am to 1pm) on 12th and 13th August.


  • There will be NO CLASS on Thursday, July 23rd. There will be class on July 28th, where I will review what all we did on the course. You are all encouraged to ask questions, as long as you do not ask me what will be on the end term. I might not know that answer myself. Time permitting, I will also say what I know about the state of the art of various scheduling problems, and also tell you what I know (not much) about practical scheduling. We got a flavour of things done in practice today (July 21st) - the shifting bottle heuristic.


  • FINALS are on August 14th, 12:30pm at PAC 6. The exam duration is 2hrs and 30 minutes. You will be allowed to bring in one "help-page" written in your handwriting (both sides allowed). I will also provide the models.pdf file in the finals, so do not bother copying stuff from it. You are encouraged to hand in the sheet with your examination to show how much, or less, you needed for the help-page. GOOD LUCK!


  • HW6 is out. It is due on July 28th, the last day of class. I have also put up the lecture notes till just before shop-scheduling. I have followed shop scheduling from the text-book; so if you want to get a heads up before I post the notes for those, refer to Chapter 6 & 7 of the textbook. Recall, the textbook is online and available via your waterloo accounts.


  • HW5 is out. It is due on July 21st.


  • There was a portion missing in the solution of Q2 in HW3, it is correted now. Irene will be taking a review lecture on Tuesday, June 23rd. BEST OF LUCK, for the Midterms!!


  • As I mentioned in class, I will be out of town from the 22nd of June to 29th of June. Which means, I will not be able to have office hours on 26th of June, which is just before the due date for HW4. Please make use of the 19th June office hours to the fullest. I will be in touch with email though to answer specific questions.


  • HW4 is posted. Sorry for the delay in posting it!


  • HW2 Solutions are posted. Remember: the username-passwd is co454 and 454co, respectively. Lecture notes for June 9,11 are posted. I will post HW4 containing questions on parallel machines by the weekend. These are mainly meant for you to get practise on parallel machines, since they will be in the syllabus for the midterm. However, I will make the HW4 due only on the 30th of June, in case you do not find time to write the homework up before the midterm. Tentatively, there will be two more homeworks after that. HW5 will be tentatively posted on July 7th, and due on July 16th, and HW6 will be tentatively posted on July 21st and due by July 30th. The FINALS for co454 is on August 14th, 12:30pm.


  • Typos in HW3: Q4, part (b), $\beta > 1$ instead of $\beta > 0$. Q5, part a) and b), you need to show NP-hardness by reducing $(1|r_j|L_{max})$ to partition and bin-packing, not the other way around, as was mentioned in the earlier version. The HW3 now contains the correct version.

  • MIDTERM will be on June 25th. It will be in-class, closed notes and books. Homeworks 3 has been posted and is due on June 18th.

  • Lecture notes for this week have been posted. Homework 2 has been posted. It is due on June 4th. We strongly advise students not to start the homework till the last few days. Corrected homework 1 copies will be returned on Tuesday.

  • May 21st We looked at dynamic programming, in particular, a dynamic programming solution to the knapsack problem. In the last 10 minutes, we noted that the problem of minimizing the weight of late jobs when all the due dates are the same is equivalent to the knapsack problem. Next time, we will generalize the DP for knapsack to a DP for maximizing the total weight of timely jobs.

  • I had erroneously put the TA's office room as DC3154. It should be DC3145. Sorry for the trouble!

  • May 19th We looked at minimizing maximum latency and saw EDD gives an optimal schedule. We also looked at a generalization of $(1||L_{max})$, called $(1||f_{max})$ where each job comes with a nondecreasing function $f_j$ and the goal is to minimize the maximum $f_j(C_j)$ over all $j$. We showed a greedy algorithm LCL solves the problem optimally.

  • May 14th We looked at average completion time problem with release dates. I told you guys that the problem $(1|r_j|\sum C_j)$ is NP-complete. Later in the course we will first understand what NP-complete means and then we will prove the above assertion. Nevertheless, we showed that with preemption, the problem is solvable by a modification of SPT called SRPT (R for Remaining). We then used the SRPT algorithm to get a factor $2$ algorithm for the non-preemptive version. I ended the class asking if the algorithm was tight? I don't know the answer to the question. Update: See Homework 2 for an answer to this!!

    Two things I forgot to mention in class. The average weighted completion time problem (which is ofcourse harder than without weights) remains NP-hard even with preemptions. Secondly, the CFP is not the best approximation algorithm for the problem. The state of the art algorithm actually achieves any factor strictly bigger than $1$, say $1.01$, approximation in polynomial time. However, this algorithm is slightly out of the scope of the syllabus of the course, but we might flirt with it later on.

  • May 12th We started on algorithms! We first studied the notion of reduction among scheduling problems and reduced $(\alpha|\beta|L_{max})$ to $(\alpha|\beta|\sum U_j)$. To obtain a polynomial time reduction we need binary search . We then studied the SPT and WSPT rule for solving $(1||\sum C_j)$ and $(1||\sum w_jC_j)$ problem. Can you think of other performance measures when SPT be applied?

  • Homework 1, question 6: the order of the machines in the flow shop problem is every job needs to be processed on machine 1 followed by machine 2.

  • Homework 1 is out. It is due on 21st May, Thursday, before class starts. Assignments should be written as legibly as possible and handed in as a singled stapled stack of papers. Typing out solutions is recommended, although email submissions will not be allowed. If you are not able to make it to class that day, then you must submit the solution beforehand to the instructor. For instance, submitting by sliding beneath my office is fine, but not encouraged. No submissions after 11:30am will be accepted unless extenuating circumstances prevail.
  • The Lecture 1 and Lecture 2 notes are out. Although they don't represent the order of things we did in the class, all the stuff should be there in both combined.

  • May 7: We covered what regular performance measures are and indicated why most of the objectives we did in class are regular. We saw how to use Gantt charts or block diagrams to represent schedules. We studied nondelay schedules and showed that some optimal schedule must be nondelay if preemption is allowed. We studied a generalization called active schedules. Atlhough, we didn't do in class, all active schedules are nondelay. Can you see why?

  • Sharon pointed out that the recommended (not required) textbook is available online via a school computer or by getting logged into TRELLIS. The book link is (here) and the TRELLIS catalogue entry is (here) . Thanks Sharon!

  • May 5: We covered a few examples of scheduling problems and started on the (\alpha | \beta | \gamma) notation. We covered the machine environment (\alpha) and almost whole of the objective function (\gamma). Next class we will study the various constraints (\beta) after a review of what we did today.

  • May 5: Welcome to the first lecture of the term. I will be using this page to make announcements that were made in class - so keep an eye out for this place once in a while.