Production Systems Scheduling and Optimization - 4GUL09D5

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.
-Batch 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

-Modelling
-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
Course language(s):

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.