Aller au menu Aller au contenu
Design & Organisation
High level education
Design & Organisation
Design & Organisation

> Studies > Engineering degree

Production Systems Scheduling and Optimization - 4GUL09D5

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Number of hours

    • Lectures : 18.0
    • Tutorials : 18.0
    • Laboratory works : -
    • Projects : -
    • Internship : -
    • Written tests : -
    ECTS : 3.0
  • Officials : Pierre LEMAIRE

Goals

  • 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


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)

Prerequisites


Operations Research, Probabilities

Tests

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

Calendar

The course exists in the following branches:

  • Curriculum - Engineer student Master SCM - Semester 8
see the course schedule for 2019-2020

Additional Information

Course ID : 4GUL09D5
Course language(s): FR

You can find this course among all other courses.

Bibliography

  • M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer, 2012.
  • P. Brucker, Scheduling Algorithms, Springer, 2007.
  • G. Ausiello et al., Complexity and Approximation, Springer, 1999.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

Date of update June 5, 2015

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes