OR&IE 6335 Scheduling Theory: Design and Analysis of Scheduling Algorithms
Fall 2014
Basic Info:
- Instructor:
David Shmoys (214 Rhodes Hall, 255-9146)
- Time and Place: Tuesdays and Thursdays, 11:40-12:55, 315 Upson Hall
- Prerequisites: There is no specific prerequisite for this course, but
some previous exposure to linear programming and to the design and analysis of
approximation algorithms will be assumed.
- Handouts
- Assignments
Handouts:
Course Announcement
Single Machine Min-Max Chapter
Tools from Algorithms and Complexity
Single Machine Min-Sum Chapter
2-Dimension Gantt Chart paper of Goemans and Williamson
and the citeseer page with alternate formats
Fragment of paper by Hall, Schulz, Shmoys, and Wein
Algorithms for 1||sum wjCj and 1|rj|sum wjCj
Sidney decomposition based algorithm and
accompanying figure
Sidney decomposition theorem
Stochastic scheduling
A chapter on minimizing the weighted sum of late jobs (Chapter 6)
A new section of the previous chapter on minimizing the weighted sum of late jobs
A chapter on minimizing total completion time on parallel machines (Chapter 8)
A chapter on approximation algorithms for makespan on parallel machines
(Chapter 9)
A chapter on preemptive algorithms on parallel machines
(Chapter 10)
A brief write-up of the uncrossing proof for P2|pj=1,prec|Cmax
Assignments:
Problem Set 1