OR&IE 6335 Scheduling Theory: Design and Analysis of Scheduling Algorithms

Fall 2014

Basic Info:


  • 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


  • Problem Set 1