Scheduling consists in allocating resources to tasks over time, with various constraints. It is a major and very rich field of Operations Research. The first part of this course introduces the fundamental problems of this theory: one-machine, parallel-machine, and workshop (flowshop, jobshop, openshop) problems, the main optimization criteria (makespan, flow-time, etc.) and the classical three-field notation. Then it addresses various tools and techniques to analyze and solve such problems optimally or near-optimally:

  • list algorithms,
  • lower bounds,
  • weak and strong NP-hardness,
  • MILP models,
  • approximation techniques,
  • inapproximability results,
  • dynamic programming,
  • branch and bound procedure.

Last modified on April 22, 2016, at 08:48 AM