Scheduling theory deals with how to use the resources we have (machines, trucks, energy, budget) in the best possible way to achieve some activities (production, transportation, project steps) by planning on a time schedule. Scheduling is a wide topic including: finishing as quick as possible, reducing delays, minimising work in progress etc... Usually resources are scarce and constraints numerous (deadlines, precedence between tasks) which make scheduling problems some of the most challenging combinatorial issues to solve in practice.
In addition to scheduling theory, the course presents heuristic techniques in Operations Research to find solutions to industrial problems. The lecture presents through different examples (production, transportation) the role of scheduling inside companies. Then modelling and resolution techniques are developed both for deterministic scheduling (when everything is known in advance) and for stochastic scheduling (when uncertainties occur).
In addition to scheduling theory, the lecture also presents heuristics in order to tackle industrial problems. In particular the lecture gives an introduction to constraint satisfaction programming (CSP) which is an efficient tool for modelling and solving difficult scheduling problems.
• Deterministic Scheduling
-Examples, definition and formalism.
-One machine sequencing according to different criteria, list algorithms.
-More machines: parallel machines, shop scheduling.
-Project scheduling: multi-resource scheduling, energetic reasoning.
-Heuristics: what can be expected in limited time, performance guarantee, approximation techniques.
-On-line algorithms: can we optimise without knowing about the future?, competitive analysis, how randomness may help.
• Stochastic Scheduling.
-Formalism: random variables, definition of a policy, comparison of policies.
-Single machine scheduling with tasks of random duration.
-Single machine scheduling with random release dates.
-Link with Queueing Theory.
• Constraint Satisfaction Programming
-Propagation algorithms arc and node consistence.
• Practical work and Project
-Scheduling and Constraint programming software (ORTEMS / ILOG SOLVER / SCHEDULER)
-Simulation of scheduling rules with randomness (ARENA)
Operations Research, Probabilities
CC1 : written exam on Scheduling
CC2 : written exam on Constraint Programming
Pro : project
N1 = 0,4 CC1 + 0,2 CC2 + 0,4 Pro
N2 = S2
The course exists in the following branches:
Date of update June 5, 2015