Production Systems Scheduling and Optimization - 4GUL09D5

Goal(s)

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

Content(s)

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