Scheduling

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.