Ordonnancement : entre théorie et applications

Christophe RAPINE
Laboratoire LGIPM, université de Lorraine

Ecole des Jeunes Chercheurs du GDR-RO

1
Ordonnancement : entre théorie et applications
 Qu’est-ce que l’ordonnancement ?

Organiser la réalisation d’un ensemble de

tâches
⇒ Planification dans le temps
⇒ En respectant des contraintes
⇒ Pour optimiser un critère (finir le plus vite
possible, en faire le plus possible avant
une date limite, sans trop de retard, . . .)

2
Ordonnancement : entre théorie et applications
 Trois ingrédients fondamentaux

• Des activités à réaliser

• Des ressources pour les réaliser
• Le temps

Qui fait Quoi et Quand ?

3
Ordonnancement : entre théorie et applications
 Terminologie

Données d’un problème d’ordonnancement

Un problème d’ordonnancement est défini par
• Un ensemble de ressources
hommes, machines, camions, budget . . .
• Un ensemble d’activités nécessitant ces ressources
taches d’un projet, produits à usiner, commandes à livrer, . . .
• Un ensemble de contraintes à respecter
capacités des ressources, précédences entre les tâches. . .
• Un objectif
finir au plus vite, minimiser les retards, . . .

4
Ordonnancement : entre théorie et applications
 Décisions attendues

Problème d’ordonnancement
Il faut décider :
• De l’allocation des ressources aux activités
• Du séquencement des activités sur chaque
ressource → date de début des activités

5
Ordonnancement : entre théorie et applications
 Visualisation d’un ordonnancement

Diagramme de Gantt
Représentation ressources/temps de l’ordonnancement
Nommé d’après Henry Gantt (1861-1919)

6
Ordonnancement : entre théorie et applications
 Les domaines de l’ordonnancement

• Production,
• Gestion de projets,
• Logistique, transport
• Emplois du temps, gestion des ressources humaines, hôpitaux
• Informatique, . . .

7
Ordonnancement : entre théorie et applications
 Exemple du menuisier

Un menuisier doit réaliser 4 commandes

à livrer dans temps de travail
1 table 4 jours 2 jours
6 chaises 6 jours 5 jours
1 vaisselier 7 jours 2 jours
1 commode 5 jours 4 jours

• Minimiser le plus grand retard

• Minimiser le nombre de commandes en
retard

→ Ordonnancement sur une ressource

8
Ordonnancement : entre théorie et applications
Exemple : Ordonnancement en transport routier

• Des clients à livrer en direct depuis

un entrepot
• Une flotte de camions à disposition
• Comment effectuer les livraisons ...

9
Ordonnancement : entre théorie et applications
 Exemple : Ordonnancement en transport routier

Livraison à effectuer dans la journée

durée A/R + Chargement fenêtre de livraison
client 1 90 mn 6h - 8h30
client 2 80 mn 7h - 8h
client 3 70 mn 7h - 9h
client 4 120mn 7h30 - 9h30
... ... ...

• Livrer toutes les commandes à l’heure

• Minimiser les pénalités de retard/avance

→ Ordonnancement sur machines parallèles

10
Ordonnancement : entre théorie et applications
 Gestion de quais de déchargement

• Porte-containers/cargos à décharger
• Des quais avec des équipements et des longueurs différentes
• Comment gérer le plan d’ammarrage ?
• Pour maximiser le débit du port, minimiser les temps
d’attente des cargos, obtenir un ammarrage équitable

→ Ordonnancement multi-ressource : RCPSP

11
Ordonnancement : entre théorie et applications
 Ordonnancement d’atelier

• Atelier de montage/Ligne de
production
• Les produits passent d’un poste à
un autre : jobs avec un ensemble
d’opérations à réaliser
• Machines spécifiques (dédiées)
pour réaliser les opérations
• Allocation fixée des ressources aux
opérations

→ Ordonnancement sur machines en série : flowshop/jobshop

12
Ordonnancement : entre théorie et applications
Vocabulaire

13
Ordonnancement : entre théorie et applications
 Types de Ressources

Ressource
Une ressource est un moyen matériel (machine, homme, argent)
nécessaire pour exécuter les tâches.
Une ressource peut être
• à capacité limitée
par exemple au plus une tâche peut l’utiliser à chaque
instant : ressource unitaire
• renouvelable
rendue après son utilisation (outil, main dœuvre, machine, . . .)
• non renouvelable
son utilisation consomme la ressource (budget)

14
Ordonnancement : entre théorie et applications
 Activité

Activité
Une activité (ou tâche) est une opération élémentaire dont la
réalisation nécessite un certain nombre d’unités de temps (durée de
la tâche) et d’unités de chaque ressources.

Notations
• Un ensemble de n tâches à ordonnancer, numérotées de 1 à n
• La durée de la tâche i est pi
• A déterminer : la date de début ti de la tâche i, ou sa date de
fin Ci .

15
Ordonnancement : entre théorie et applications
 Contraintes

Contraintes
Spécifient quels sont les ordonnancements réalisables, ce qu’il est
possible de faire (en respectant les capacités physiques, les
engagements contractuels, les objectifs commerciaux, etc).

Types de contraintes :
1 Contraintes potentielles (ou de potentiels)
2 Contraintes disjonctives
3 Contraintes cumulatives

16
Ordonnancement : entre théorie et applications
 Contraintes Potentielles

Formes générales
Si i et j sont 2 tâches, containtes ti − tj ≥ aij

• Date de disponibilité : i ne peut débuter avant une certaine

date ri (livraison de matière première, . . .)
• Date butoir : j doit être terminée avant une certaine date d̃i
• Contrainte d’antériorité (précédence) : i doit attendre que j
soit achevée pour débuter.

17
Ordonnancement : entre théorie et applications
 Contraintes Disjonctives

Définition
Deux tâches i et j sont en disjonction si elles ne peuvent être
exécutées simultanément.

• Leurs intervals d’exécution doivent être disjoints

• Contrainte ti − tj ≥ pj ou tj − ti ≥ pi
⇒ Cas de 2 tâches demandant une même ressource unitaire pour
s’exécuter.

18
Ordonnancement : entre théorie et applications
 Contraintes Cumulatives

• Généralisation des contraintes disjonctives à des ressources

non unitaire
• Généralement chaque ressource k à une capacité ak (t)
• A chaque instant t, l’ensemble des activitées exécutées ne doit
pas requérir plus que la capacité ak (t) de la ressource k.
• Par exemple, la consommation électrique ne peut dépasser à
tout instant la puissance disponible

19
Ordonnancement : entre théorie et applications
 Notation 3 champs

Notation α|β|γ
• α Description des ressources
nombre de ressources, type de ressource : {1, P3, F 2, . . .}
• β Caractéristique des tâches
précédences, date d’arrivée, . . .
• γ Critère à optimiser
Exprimé en fonction de la date de fin Ci des tâches
On considère que les tâches et leurs caractéristiques sont connues
lors de l’ordonnancement
→ problèmes off-line
Problèmes très souvent NP-difficiles (Complexity results for
scheduling problems)
[Link]

20
Ordonnancement : entre théorie et applications
 Ordonnancement sur une ressource

Une seule ressource unitaire

• une machine qui doit réaliser un ensemble de tâches

Séquencement
Il faut décider :
• l’ordre d’exécution des tâches sur la ressource

21
Ordonnancement : entre théorie et applications
 Problème 1||Cmax

Makespan Cmax
• Objectif : minimiser la durée totale de
l’ordonnancement
• Cmax = maxi Ci

• 4 tâches à ordonnancer

A B C D
pi 5 2 1 3

• Toute séquence est optimale !

• Minimiser le makespan devient NP-difficile sur machine
parallèle (P2||Cmax )

22
Ordonnancement : entre théorie et applications
 P
Problème 1|| Ci

P
Total flow time Ci
• Objectif : minimiser la date de fin
moyenne des tâches
• attente moyenne des clients dans une file
• stocks d’encours devant la ressource

23
Ordonnancement : entre théorie et applications
 Quai de déchargement

Une grande entreprise de métallurgie possède un site en bord de

mer. L’approvisionnement en matière première (minerais, charbon)
s’effectue par voie maritime.
• Le quai de déchargement du site ne
peut acceuillir qu’un seul navire à
la fois.
• Les autres navires doivent attendre
en mer.
• un jour d’attente d’un navire est
facturé 5000 euros
• Comment gérer le plan
d’ammarrage ?

24
Ordonnancement : entre théorie et applications
 P
Problème 1|| Ci

• 4 tâches à ordonnancer

A B C D
pi 5 2 1 3
P
• Séquence σ = ABCD valeur Ci = 31

A B C D
temps

5
P7 8 11
• Séquence σ0 = CBDA valeur Ci = 21 optimal ?

C B D A
temps

1 3 6 11

25
Ordonnancement : entre théorie et applications
 Comment prouver l’optimalité d’une politique ?

Argument d’échange
• On considère 2 taches successives
• On cherche à quelle condition un échange améliore
l’ordonnancement

Cj + Ci = D + pj + F
j i

Cj Ci Ci0 + Cj0 = D + pi + F
D F
i j

C’ i C’ j
26
Ordonnancement : entre théorie et applications
 Dominance

Definition (Dominance)
Une propriété D est une dominance si pour toute solution π,
il existe une solution π 0 au moins aussi bonne que π et vérifiant la
propriété D.

Propriété D
Solutions
réalisables

Solutions
optimales

27
Ordonnancement : entre théorie et applications
 P
Problème 1|| Ci

Dominance
Deux tâches successives sont ordonnancées dans l’ordre des temps
opératoires croissants

si i et j se succèdent, alors pi ≤ pj

i j

temps

28
Ordonnancement : entre théorie et applications
 Règle SPT

SPT
La règle SPT (Shortest Processing Time) séquençantPles tâches
par durée opératoire croissante est optimale pour 1|| Ci

• Il doit exister une séquence optimale vérifiant la dominance

• Seule la séquence SPT vérifie la dominance

29
Ordonnancement : entre théorie et applications
 Stretch

Dans la file d’attente aux caisses d’un supermarché, nous sommes

naturellement plus disposer à patienter si l’on a acheté un gros
caddie plutôt que si l’on a trois articles dans la main.
• Le temps d’attente “acceptable”
est proportionnel au temps de
service
• Le stretch d’une tâche est défini
comme son temps dans le système
divisé par sa durée
• Si = Ci /pi
P
Comment minimiser le stretch moyen d’une file d’attente i Si ?

30
Ordonnancement : entre théorie et applications
 P
Problème 1|| wi Ci

On peut généraliser la règle SPT en présence de poids wi > 0

associés à chaque tâche
• coût financier (stockage)
• importance, criticité de la tâche (attente client)
Exemple de 5 tâches à ordonnancer sur une ressource :

A B C D E
pi 1 2 4 5 6
wi 2 1 3 5 4

wSPT
La règle wSPT séquençant
P les tâches par ratio pi /wi croissant est
optimale pour 1|| wi Ci

31
Ordonnancement : entre théorie et applications
 Quai de déchargement (suite)

Tous les navires n’arrivent pas en même temps sur le site !

• Le planning d’arrivée des bateaux

est connu sur une période
relativement longue.
• Date ri (release date)
d’arrivée/disponibilité de la tâche i
⇒ Des temps d’inactivité (idle time) peuvent apparaı̂tre sur la
ressource

32
Ordonnancement : entre théorie et applications
 Ordonnancement semi-actif

Definition
Un ordonnancement est semi-actif si il n’est pas possible d’avancer
l’exécution des tâches sans remettre en cause l’ordre d’exécution

⇒ Séquence calée à gauche

Les ordonnancements semi-actif sont dominants pour les critères

réguliers. . . mais pas nécessairement optimaux

33
Ordonnancement : entre théorie et applications
 Algorithme de Liste

Algorithme de Liste
• Priorité sur les taches : liste L
• Séquencement glouton des tâches
Si la ressource est libre, séquencer la première tâche disponible
de la liste

• Principe glouton : ne pas laisser la ressource inoccupée si des

taches sont disponibles
• La liste sert à arbitrer lorsque plusieurs tâches sont disponibles
en même temps

34
Ordonnancement : entre théorie et applications
 Algorithme de Liste

Propriété
Les algorithmes de liste construisent des ordonnancements
semi-actifs

Selon le problème d’ordonnancement :

• Toutes les listes conduisent à un ordonnancement optimal
• Il existe des listes conduisant à l’optimal
• Aucune liste ne permet d’être optimal sur toutes les instances
Listes optimales
P
1|| Ci liste SPT
1|ri |Cmax ∀ liste L

35
Ordonnancement : entre théorie et applications
 Optimalité pour 1|ri |Cmax

Montrons que tout algorithme de liste L minimise le makespan. Le

makespan Cmax (L) est imposée par la dernière tâche, l.
Elle ne commence pas plus tôt car :
• soit elle n’est pas disponible avant
• soit la ressource est occuppée avant

Bloc
Dans un ordonnancement, on appelle bloc une suite (maximale) de
tâches sans temps mort.
C
max

k l

36
Ordonnancement : entre théorie et applications
 Optimalité pour 1|ri |Cmax

Propriété
Dans un ordonnancement semi-actif, la première tâche d’un bloc
est exécutée à sa date de disponibilité (ou à l’instant 0).
C
max

k l

• La durée de l’ordonnancement est Cmax (L) = rk + p(B)

• Borne inférieure : l’ordonnancement optimal a une durée

∗
Cmax ≥ min ri + p(S) ∀S ensemble de tâches
i∈S

37
Ordonnancement : entre théorie et applications
 Optimalité pour 1|ri |Cmax

Propriété
Dans un ordonnancement obtenu par un algorithme de liste,
aucune tâche d’un bloc n’est disponible avant le début du bloc.
C
max

k l

ri ≥ rk pour toute tâche i du dernier block

• Il suffit d’écrire la borne inférieure pour S = B, le dernier bloc
∗
• On en déduit que Cmax ≥ rk + p(B) = Cmax (L)

38
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci

A B C D
pi 5 2 1 3
ri 0 9 1 8
P
• Liste SPT CBDA valeur Ci = 35 Quelle que soit la liste !

A C D B

temps
5 6 8 11 13
P
• Séquence CABD valeur Ci = 33

C A D B

temps
1 2 7 8 11 13
39
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci

Dans la séquence optimale, il peut être nécessaire de laisser la

ressource inoccuppée même si des tâches sont disponibles

• Tout algorithme de liste peut être arbitrairement mauvais

• Par exemple si on doit ordonnancer 1 tâche très longue
immédiatement disponible, et des tâches très courtes qui
arrivent juste après.

40
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci

Propriété
P
Le problème 1|ri | Ci est NP-difficile (au sens fort)

Il n’existe pas de règle ”simple” pour trouver l’optimum

• Algorithme exacte d’énumération (Branch & Bound)
• Heuristiques, Algorithmes d’approximation

41
Ordonnancement : entre théorie et applications
 Borne inférieure ?

Comment obtenir une borne inférieure ?

• Résoudre à l’optimum une relaxation du problème,
• Suppression des précédences, des dates de disponibilité,
• Ajouter des ressources additionnelles, augmenter la vitesse,
• Autoriser la préemption, . . .

42
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci

5 tâches à ordonnancer :
A B C D E
pi 10 4 1 1 2
ri 0 2 4 6 8

Quelle borne inférieure ?

• Infinité de ressources ?
• Sans date de disponibilité ?

43
Ordonnancement : entre théorie et applications
 Préemption

Définition
La préemption est la possibilité d’interrompre l’exécution d’une
tâche pour la reprendre ultérieurement.

• Dans certaines situations (usinage d’une pièce, service) la

préemption n’est pas envisageable, ou alors à un coût très
élevé
• Dans d’autres cas, elle peut entrainer des temps
supplémentaires (réglages, context swap, reprise partielle)

44
Ordonnancement : entre théorie et applications
 P
Problème 1|ri , pmtn| Ci

5 tâches à ordonnancer pour minimiser la date moyenne de fin :

A B C D E
pi 10 4 1 1 2
ri 0 2 4 6 8

Avec la préemption, le problème devient “facile” :

SRPT
La règle SRPT (Shortest Remaining Processing Time)
ordonnançant à chaque instant la tâche disponible
P de plus petit
temps restant est optimale pour 1|ri , pmtn| Ci

45
Ordonnancement : entre théorie et applications
 SRPT : Exemple

5 tâches à ordonnancer :
A B C D E
pi 10 4 1 1 2 D

ri 0 2 4 6 8 C E

P 0 2 4 6 8 10
Algorithme SRPT, i Ci (SRPT ) = 48

46
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci : Approximation

Algorithme de Phillips Stein & Wein

preempt
Ordonnancer les taches dans l’ordre de leur date de fin Ci
dans l’ordonnancement SRPT préemptif

Ordonnancement SRPT, z̄ ∗ = 48
C DB E A

5 7 8 11 18

47
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci : Approximation

• Ordonnancement SRPT, z̄ ∗ = 48
• Ordonnancement PSW : CDBEA, z = 59

C DB E A

5 7 8 11 18

5 7 11 13 23

48
Ordonnancement : entre théorie et applications
 P
Problème 1|ri | Ci : Approximation

Algorithme de Stein
L’algorithme de Phillips Stein & Wein a une garantie 2

Preuve
preempt
Pour toutes les tâches, CiPSW ≤ 2Ci

Remarque
La garantie 2 est a priori. On peut sur chaque instance regarder la
garantie a posteriori on se comparant à la relaxation préemptive.

CiPSW /OPT ≤ 59/48 ' 1, 23

X

49
Ordonnancement : entre théorie et applications
 Exemple du menuisier

Un menuisier doit réaliser 4 commandes

à livrer dans temps de travail
1 table 4 jours 2 jours
6 chaises 6 jours 5 jours
1 vaisselier 7 jours 2 jours
1 commode 5 jours 4 jours

• Minimiser le plus grand retard

50
Ordonnancement : entre théorie et applications
 Date échue

• Chaque tâches doit être idéalement

terminée à une date donnée, au delà
de laquelle elle est considérée en retard
• Date échue di (due date)
• On veut bien sûr éviter le retard des
taches. . .

51
Ordonnancement : entre théorie et applications
 Les indicateurs de retard

Pour un ordonnancement fixé et une tâche i :

• Tardiness Ti = max{Ci − di , 0}
retard de la tâche i par rapport à sa date échue
• Lateness Li = Ci − di retard algébrique
• Ui , indicatrice de retard

Ti

di Ci

52
Ordonnancement : entre théorie et applications
 Critères classiques de retard

A partir des retards individuels des tâches, on peut construire des

mesures globales de retard pour l’ordonnancement :
• Tmax = maxi Ti , le plus grand retard
P
• Ti retard total, ou moyen
P
• i Ui nombre de tâches en retard
• Lmax = maxi Li , le plus grand retard algébrique
On peut bien sûr pondérer ces critères

53
Ordonnancement : entre théorie et applications
 Problème 1||Tmax

• Objectif : minimiser le plus grand retard maxi Ti

A B C D
pi 5 2 1 3
di 8 7 3 6

• Séquence σ = ABCD valeur Tmax = 5

A B C D
temps

5 7 8 11

54
Ordonnancement : entre théorie et applications
 Règle EDD

EDD
La règle EDD (Earliest Due Date) séquençant les tâches par date
échue croissante est optimale pour 1||Tmax

Remarque. Règle très naturelle : plus urgent d’abord.

Ce qui est remarquable : ne dépend pas des temps de process

55
Ordonnancement : entre théorie et applications
 Contraintes de précédence

Contraintes inhérentes aux activités à réaliser :

• On ne peut plus commencer par n’importe quelle tâche
• Certaines tâches doivent attendre la terminaison d’autres
tâches pour pouvoir débuter
• Précédence i → j : la tâche j ne peut commencer avant la fin
de i.

i j

56
Ordonnancement : entre théorie et applications
 Contraintes de précédence

On décrit l’ensemble des précédences par un graphe

• nœuds : tâches à réaliser
• arc : précédences i → j entre tâches
• le graphe doit être acyclique

Précédences
C
A→C
A
E
A→D
B→D
B
C →E
D

57
Ordonnancement : entre théorie et applications
 Algorithme de Lawler

• Plutôt que de passer en revue les différents critères que nous

connaissons
• Nous allons voir un algorithme, proposé par Lawler, optimal
pour toute une classe de critères
• Ce sont les critères qui sont bottleneck et régulier

58
Ordonnancement : entre théorie et applications
 Critères Réguliers

Critère Régulier
Un critère f est régulier si il est croissant avec les dates Ci

Si la date de fin de chaque tâche augmente, alors la valeur du

critère pour l’ordonnancement augmente

Ci (π) ≥ Ci (π 0 ) ∀ tâche i ⇒ f (π) ≥ f (π 0 )

Pour un critère régulier, on est incité à finir au plus tôt chaque

tâche, c-à-dire à ne pas laisser inutilement la machine inoccupée
(idle)

59
Ordonnancement : entre théorie et applications
 Critères Bottleneck

La plupart des critères pour un ordonnancement sont des fonctions

de la mesure individuelle des tâches fi (Ci ). C’est à dire

f (π) = g (f1 (C1 ), . . . , fn (Cn ))

Les critères les plus usuels considère la plus grande des valeurs ou
la somme de ces valeurs.
• fmax (C ) = maxi fi (Ci ) bottleneck
P
• fsum (C ) = i fi (Ci ) sum

Ces critères sont réguliers simplement si la mesure fi pour chaque

tâche i est croissante avec la date de fin Ci

60
Ordonnancement : entre théorie et applications
 Problèmes 1|prec|fmax

Critère bottleneck régulier fmax , par exemple Tmax

Algorithme de Lawler
P
1 Partir de la fin de l’ordonnancement (t = pi )
2 Placer en dernier la tache i sans successeur (non ordonnancé)
qui minimise fi (t)
3 Retrancher pi à t et retourner à l’étape 2 si t > 0

Propriété
L’algorithme de Lawler est optimal pour tout critère régulier fmax
Sa complexité est O(n2 ).

61
Ordonnancement : entre théorie et applications
 Algorithme de Lawler : Exemple

On veut minimiser le plus grand retard (1|prec|Tmax )

A B C D E
C
pi 2 3 1 2 4
A di 8 7 3 6 11
E

• Quelle séquence donne l’algorithme de Lawler ?

• Ordonnancement ACBDE, retard maximal de 2 pour D

62
Ordonnancement : entre théorie et applications
 Lateness

Un autre critère : le retard algébrique (lateness)

• A chaque tâche est associé un temps de latence qi
• Une fois la tâche i traitée par la ressource, il faut attendre un
délai qi avant de pouvoir disposer de la tâche
• Pendant le délai la tâche ne consomme aucune ressource
• La lateness Li de la tâche i est la date :

Li = Ci + qi

pi
qi

0 Ci Li

63
Ordonnancement : entre théorie et applications
 Problème 1||Lmax

Le temps de latence qi peut représenter :

• Un temps de séchage dans un process de
peinture
• Un temps de refroidissement
• Un temps d’acheminement par la poste
d’une commande vers le client
• Temps de post-traitement sur une
machine de capacité infinie.

64
Ordonnancement : entre théorie et applications
 Problème 1|ri |Lmax , latence maximale

Règle de Jackson
La règle de Jackson séquençant les tâches par qi décroissant est
optimale pour 1||Lmax .

Mauvaise Nouvelle
Le problème 1|ri |Lmax est N P-difficile.

65
Ordonnancement : entre théorie et applications
 En autorisant la préemption

Est-ce que la préemption rend toujours le problème plus facile ?

• Non. En particulier la préemption peut être inutile.
• Dans le cas d’un critère de type bottleneck, on a un résultat
similaire à l’algorithme de Lawler :

Théorème
Le problème 1|ri , pmtn|fmax peut être résolu en temps O(n2 ) pour
tout critère bottleneck régulier fmax

66
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|fmax

Pour un critère régulier avec la préemption :

• Il est dominant de ne pas laisser la ressource inoccuppée si
une tâche est disponible
• L’optimal a la structure de block, obtenu par tout algorithme
de liste
B
k

r(B) C(B)

67
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|fmax

Considérons un bloc de l’optimal :

• Formé de l’ensemble de tâche B
• Finissant à la date t = C (B)

Borne inférieure
Si l est la tâche de B de plus petite valeur fi (t), on a :

OPT (B) ≥ max{ OPT (B\{l}), fl (t) }

68
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|fmax

Idée de l’algorithme :
• On construit un ordonnancement qui réalise la borne
inférieure.
Principe de fonctionnement :
• On traite séparément chaque block B, obtenu par la séquence
des ri croissant (ou tout algorithme de liste)
• Sur le block B, on identifie la tâche l minimisant fi (C (B))
• On détermine récursivement l’ordonnancement optimal pour
les tâches de B\{l}
• On ordonnance préemptivement l en bouchant les trous pour
finir à la date C (B)

69
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|Lmax

• Sur notre exemple :

A B C D E
ri 0 1 2 4 5
pi 4 2 1 2 3
qi 3 2 4 5 6

• On obtient un seul block :

A B C D E
temps

4 7 9 12
• La tâche à retirer est B

70
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|Lmax

A B C D E
ri 0 1 2 4 5
pi 4 2 1 2 3
qi 3 2 4 5 6

• On trouve de nouveau un seul block. On écarte la tâche A

• On obtient 2 block, C et ED
• L’ordonnancement (préemptif) optimal est :

A C A D E D A B
temps

71
Ordonnancement : entre théorie et applications
 Problème 1|ri , pmtn|Lmax

Dans le cas particulier de la lateness maximale, on retrouve la règle

de Jackson, appliquée dynamiquement à chaque arrivée d’une
tâche :

Résultat
Le problème 1|ri , pmtn|Lmax est résolu optimalement en
ordonnançant à chaque instant la tâche disponible de plus grande
latence (règle de Jackson).

72
Ordonnancement : entre théorie et applications
 Exemple du menuisier

Un menuisier doit réaliser une commande pour un salon

• Certaines planches commandées n’ont pas encore été livrées,
• Chaque meuble doit être vernis

livraison planches temps de travail séchage vernis

1 table 1 jour 2 jours 2 jours
6 chaises en stock 5 jours 1 jour
1 vaisselier 6 jours 2 jours 2 jours
1 commode 6 jours 4 jours 3 jours

Quel ordonnancement minimise la date de

livraison de la commande ?

73
Ordonnancement : entre théorie et applications
 Problème 1|| maxi wi Ti

• Un poids wi peut être associé à chaque tâche, traduisant

l’impatience du client pour chaque unité de temps de retard
• On souhaite minimiser le plus grand mécontentement d’un
client, maxi wi Ti
• L’algorithme de Lawler construit la séquence optimale
(bottleneck réguliers)

74
Ordonnancement : entre théorie et applications
 Algorithme de Lawler

On veut minimiser le plus grand retard pondéré pour les 3

commandes suivantes :
tâches A B C
pi 2 3 5
di 8 7 5
wi 4 3 2

• Quelle séquence donne l’algorithme de Lawler ?

• Ordonnancement CBA, retard maximal pondéré de 8.

75
Ordonnancement : entre théorie et applications
 Robustesse : incertitudes sur les poids

• L’impatience d’un client dont la commande est en retard peut

être difficile à évaluer précisément
• On ne connait par avance le poids wi : on sait simplement
qu’il prend sa valeur dans un intervalle [wi− , wi+ ]
• Un scénario S correspond à un ensemble de poids (wiS )i=1,n
• F (π, S) correspond à la valeur objectif de la séquence π sous
le scénario S.
L’ensemble des scénarios possibles S = [w1− , w1+ ] × . . . [wn− , wn+ ]
est infini

76
Ordonnancement : entre théorie et applications
 Regret

Pour une séquence π fixée

• Le regret pour π dans le scénario S est le rapport
F (π, S)/F ∗ (S)
• C’est ce que l’on a perdu en choisissant π plutôt que la
séquence optimale pour le scénario S.
• On ne sait évidemment pas à l’avance quel scénario va se
réaliser. . .
On souhaite trouver une séquence minimisant le plus grand regret
sur tous les scénarios possibles :

F (π, S)
min max
π S∈S F ∗ (S)

77
Ordonnancement : entre théorie et applications
 Robustesse : Exemple

On veut minimiser le plus grand regret pour le retard pondéré :

tâches A B C
pi 2 3 5
di 8 7 5
wi [3, 5] [2, 4] [1, 2]

• Quel est le regret de la séquence CBA ?

• Regret de 2, pour le scénario S = (5, 2, 1).
• Est-ce le scénario de plus grand regret pour la séquence CBA ?

78
Ordonnancement : entre théorie et applications
 Regret maximal d’une séquence

Approche proposée par Averbackh (2000) pour les problèmes de

minimisation combinatoire de type bottleneck

Propriété
Le regret maximal d’une séquence π est réalisé par l’un des n
scénario Sj , dans lequel la tâche j à le plus grand poids possible, et
les autres ont leur plus petit poids possible.

Sj : poids wi = wi− pour i 6= j et wj = wj+

On s’est ramené à un petit ensemble de scénarios à évaluer

79
Ordonnancement : entre théorie et applications
 Regret maximal d’une séquence

tâches A B C
pi 2 3 5
di 8 7 5
wi [3, 5] [2, 4] [1, 2]
On a 3 scénarios à considérer :
1 SA = (5, 2, 1), de valeur optimale 5
2 SB = (3, 4, 1), de valeur optimale 5
3 SC = (3, 2, 2), de valeur optimale 6
Le regret maximale de la séquence CBA est

F (CBA, SA ) F (CBA, SB ) F (CBA, SC ) 10 6 6

max{ , , } = max{ , , }
5 5 6 5 5 6

80
Ordonnancement : entre théorie et applications
 Séquence minimisant le plus grand regret

Théorème
La séquence π ∗ minimisant le plus grand regret est la séquence
optimale pour le scénario S ∗ :

w1+ wi+ wn+

S∗ = ( , . . . , , . . . , )
F ∗ (S1 ) F ∗ (Si ) F ∗ (Sn )

Remarque. Le scénario S ∗ est fictif. Il n’appartient pas

nécessairement à l’ensemble S des scénarios possibles.

81
Ordonnancement : entre théorie et applications
 Exemple

tâches A B C
pi 2 3 5
di 8 7 5
wi [3, 5] [2, 4] [1, 2]

1 Le scénario S ∗ = (5/5, 4/5, 2/6), soit (1, 0.8, 1/3).

2 La solution π ∗ est la séquence BAC , de valeur
F (BAC , S ∗ ) = 5/3
3 C’est la solution robuste. Son regret maximal est 5/3.

82
Ordonnancement : entre théorie et applications
 Conclusion

• Domaine très vaste

• Problèmes souvent NP-difficiles : approches exactes,
algorithmes d’approximation, méta-heuristiques, propagation
de contraintes
• Comment prévoir l’imprévu ? Ordonnancement on-line

83
Ordonnancement : entre théorie et applications