Aller au menu Aller au contenu
Une formation ambitieuse
Ecole de référence pour la formation d'ingénieurs en génie industriel
Une formation ambitieuse

> Formation > Cursus ingénieur

UE Optimisation globale et applications en ordonnancement - 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
  • Volumes horaires

    • CM : 18.0
    • TD : 18.0
    • TP : -
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 3.0
  • Responsables : Pierre LEMAIRE

Objectifs

  • L'élève connaîtra le formalisme de la théorie de l'ordonnancement et saura reconnaître lorsqu'un problème peut-être traité dans ce cadre ; il connaîtra également les techniques et outils de base (heuristiques de liste, preuve par argument d'échange, PLNE, programmation dynamique, théorie de la complexité).
  • L'élève connaîtra les principes de la programmation par contraintes et sera capable de modéliser et résoudre un problème d'optimisation donné dans ce cadre.

Contenu

La problématique de l'ordonnancement est d'utiliser au mieux les ressources dont on dispose (machines, camions, énergie, budget) afin de réaliser un ensemble d'activités (représentant des ordres de production, des transports à effectuer, les étapes d'un projet) en les planifiant dans le temps. Le domaine de l'ordonnancement est donc très vaste : comment finir au plus vite, en limitant les retards, en minimisant les encours, etc. Les ressources sont généralement en nombre et capacité limités, les contraintes nombreuses (respect des délais, précédences entre tâches, etc), ce qui fait des problèmes d'ordonnancement des problèmes combinatoires souvent très difficiles à résoudre en pratique.

.

Le cours présente les outils de modélisation et de résolution pour l'ordonnancement déterministe (quand tout est connu à l'avance). En plus de la théorie de l'ordonnancement proprement dite, le cours permet de découvrir la théorie de la complexité, qui permet de caractériser la difficulté intrinsèque d'un problème, et présenter différentes techniques pour obtenir des solutions aux problèmes qui se posent dans le monde industriel. En particulier le cours introduit les bases de la programmation par contraintes (PPC), qui s'avère un outil de modélisation et de résolution puissant pour les problèmes d'ordonnancement. Enfin, le rôle de l'ordonnancement au sein de l'entreprise et les particularités de l'ordonnancement en milieu industriel seront abordés.

.
Contenu détaillé indicatif :

  • Ordonnancement déterministe
    • Exemples, définition et formalisme
    • Problèmes classiques de l'ordonnancement : séquencement sur une machine selon différents critères ; ordonnancement sur plusieurs machines (affectation des ressources, machines en parallèles, lignes de production et problèmes d'atelier)
    • Complexité de problèmes
    • Méthodes de résolutions (heuristiques, approximations, PLNE,...)
  • Programmation par contraintes
    • Formalisme et modélisation en PPC
    • Algorithme de propagation : arc et noeud consistence.
  • TP et Projet

Prérequis

  • Programmation linéaire, programmation linéaire en nombres entiers
  • Recherche opérationnelle (graphes, programmation dynamique)
  • Informatique (programmation, langage Java)

Contrôles des connaissances

E1 : examen écrit (ordonnancement)
P1 : étude de cas (ordonnancement)
E2 : examen écrit (programmation par contraintes)
P2 : étude de cas et travaux pratiques (programmation par contraintes)

S2 : examen session 2 (oral ou écrit)

N1 = note finale session 1
N2 = note finale session 2

Le jury peut décider le passage en année supérieure sous réserve de validation différée de cette UE. Cette décision reste exceptionnelle ; le jury est souverain pour chaque étudiant.

N1 = 0,34*E1 + 0,16*P1 + 0,34*E2 + 0,16*P2
N2 = S2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Ingénieur ICL - Semestre 8
cf. l'emploi du temps 2019/2020

Informations complémentaires

Code de l'enseignement : 4GUL09D5
Langue(s) d'enseignement : FR

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

  • 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

mise à jour le 5 juin 2015

Programmes pédagogiques

2019-2020 Cursus ingénieur
1ère année présentation
Semestre 5 - Semestre 6
Filière ICL présentation
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10
Filière IdP présentation
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10

2019-2020 Cursus ingénieur par apprentissage
Filière IPID présentation
Semestre 5 - Semestre 6
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10

Contacts

Responsables pédagogiques
Directeur des études Yannick Frein
Responsable année 1 Pierre David
Responsable filière ICL
Hadrien Cambazard
Responsable filière IdP Guillaume Thomann
Responsables apprentissage filière IPID
Nicolas Catusse
Olivier Boissin


Service scolarité
Responsable Laure Jouffray
Gestionnaire 1ère année
Valérie Demicheli
Gestionnaire 2ème année
Myriam Reinbold
Gestionnaire 3ème année
Hélène Lemaire
Relations entreprises / apprentissage
Christine Ancey
Gestionnaire apprentissage 2ème année
Sylvie Malandrino

Echanges internationaux
Nadia Dehemchi
Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes