Number of hours
- Lectures 15.0
- Projects -
- Tutorials 15.0
- Internship -
- Laboratory works -
- Written tests -
- The student shall know the concepts of Scheduling Theory and shall identify when a problem can be tackled within this scope.
- The student shall know the main technics used in Scheduling to analyze and solve problems.
- The student shall know the bases of Complexity Theory and shall be capable of using them to analyze simple problems.
- The student shall know the foundations of Constraint Programming, and shall be capable of modeling and solving optimization problems within this framework.
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,34*E1 + 0,16*P1 + 0,34*E2 + 0,16*P2
N2 = S2
The course exists in the following branches:
- Curriculum - Engineer student Master SCM - Semester 8
Course ID : 4GUL09D5
You can find this course among all other courses.
- M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer, 2012.
- P. Brucker, Scheduling Algorithms, Springer, 2007.
- G. Ausiello et al., Complexity and Approximation, Springer, 1999.