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
Course Description

Scheduling problems form a large part of resource allocation problems where sparse resources have to be assigned over time to complete tasks and optimize over one or multiple objectives. Such problems are ubiquitous in industrial manufacturing, operations research, economics and computer science. This course will cover the basics of scheduling theory from an algorithmic perspective. In particular, we will study efficient algorithms to solve various scheduling problems stressing on proofs of correctness rather than focussing on heuristics. The course will also contain a brief overview of computational complexity and various techniques for the design of efficient exact and approximate algorithms.

Prerequisites

MATH 239/249 and either CO350 or CO352; or CO 355. Students should be familiar with discrete math, and an introductory course on algorithms will be advantageous. If in doubt, talk with the instructor.

Textbooks

There is no required textbook. The book Scheduling: Theory, Practices and Applications by Michael Pinedo is a good reference though.

Grading

There will be bi-weekly assignments which will count for 30% towards the final marks. There will be one midterm in the third week of June counting for 25% and a final counting for 45% of the total marks. Students who are unable to take the midterm must submit an university regulated reason (for instance a medical certificate) for not doing so in which case some alternative will be discussed with the instructor.