Bases de l’ordonnancement

MPRO Master Parisien de Recherche Opérationnelle

Page officielle du cours

Equipe pédagogique:

Safia Kedad-Sidhoum (responsable)
Christophe Picouleau

Plan du cours

Séance 1 : Safia Kedad-Sidhoum
- Introduction à la théorie de l'ordonnancement: Définitions et Notations standards, Typologie
- Critères réguliers. Algorithmes polynomiaux pour les problèmes à une machine : Somme des dates de fin (Règle de Smith)

Séance 2 : Safia Kedad-Sidhoum
- Critères réguliers. Algorithmes polynomiaux pour les problèmes à une machine : Retard algébrique maximal.
- Critères réguliers. Méthode exacte pour le problème à une machine minimisant le retard algébrique maximal avec dates de disponibilité des tâches.
Exercice: minimisation du coût maximal.

Séance 3 : Safia Kedad-Sidhoum
- Critères réguliers. Algorithmes polynomiaux pour les problèmes à une machine : Minimisation du coût maximal (correction).
- Critères irréguliers: Problèmes juste-à-temps : minimisation de la déviation totale autour d’une date d’échéance commune sur une machine.

Séance 4 : Safia Kedad-Sidhoum
- Critères irréguliers: Problèmes juste-à-temps sur une machine : minimisation de la déviation totale autour d’une date d’échéance commune restrictive et dates d’échéance quelconques.

Séance 5 : Safia Kedad-Sidhoum
- Ordonnancement à machines parallèles. Version annotée.
Exercice: machines parallèles identiques et tâches non indépendantes. Notes du corrigé.
- Introduction à l'ordonnancement multi-agent. Version annotée.

Séances 6 et 7 : Christophe Picouleau
- Ordonnancement avec délais de communication

Ressources