Ordonnancement

● Gestion et planification d'un projet

– décomposable en travaux et tâches
– avec des ressources
– avec des contraintes horaires (durées)
– avec des contraintes de précédence/simultannéité
entre tâches

● Ordonnancement :
– calendrier de débuts de tâches
– allocation de ressources
L.L. - Graphes 1
 Contraintes d'antériorité – s'habiller

– pantalon slip chemise

chaussettes
– veste
– chaussures chaussures
– chaussettes ? veste
pantalon
– slip
chapeau cravate
– cravate
– chemise
– bonnet
● Antériorité sur certaines tâches
– graphe
L.L. - Graphes 2
 Ordonnancement d'ateliers

● Un ensemble de jobs à realiser. Chacun d'entre eux

est composé d'un ensemble de taches
● Classification des ordonnancements d'atelier suivant
les contraintes de précédence entre les taches qui
composent un job

Pour chaque job :

tâches
openshop
indépendantes
ordre identique
flowshop
sur les tâches
ordre différents
jobshop
sur les tâches

L.L. - Graphes 3
 Contraintes de précédence (1)
● Openshop: tâches du job indépendantes

(c) CC-BY-SA-2.5 wikipédia.org

L.L. - Graphes (c) CC-BY-SA-2.5 wikipédia.org 4
 Contraintes de précédence (2)

– Flowshop : même ordre sur toutes les tâches des

différents jobs

(c) CC-BY-SA-2.5 wikipédia.org

L.L. - Graphes 5
 Contraintes de précédence (3)

– Jobshop : ordre des tâches différent suivant le job

L.L. - Graphes (c) CC-BY-SA-2.5 wikipédia.org 6

 Contraintes de temps

● Chaque tâche a
– une durée
– éventuellement des contraintes d'antériorité
– éventuellement une plage temporelle de
réalisation
● L'ordonnancement cherche à optimiser
– une durée totale (makespan)
– un respect de dates au plus tard
– une minimisation de coût
– ...
L.L. - Graphes 7
 Formulation du problème (1)

● Un ensemble T = {T1, T2, ..., Tn} de tâches à réaliser

– pi : durée de Ti
– ri : date de début au plus tôt d'exécution pour Ti
– di : date de fin au plus tard d'exécution pour Ti
– ti : date de début effectif d'exécution pour Ti
– ci : date de fin effective d'exécution pour Ti
– Wik : coût associé à Ti sur machine k
– Pik : temps d'exécution associé à Ti sur machine k

L.L. - Graphes 8
 Formulation du problème (2)
● Pour chaque tâche Ti il faut que
– pi = ci – ti
– r i ≤ ti ≤ ci ≤ di
● Si des contraintes de ressources sur des machines
existent : Pik = ci – ti (∞ si Ti non éxécutable sur k)
● Si des contraintes d'antériorité (ou de terminaison
partielle aij) existent entre Ti et Tj : ti +aij.pi <= tj

● Optimiser le coût total (suivant ∑Wik ) ou la durée

totale en fonction des contraintes
L.L. - Graphes 9
 Représentation du problème
Diagrammes de Gantt
● Visualisation d'une solution
– A = {T1, T2, T3, T4, T5}
– Avec les durées p1=6, p2=3, p3=4, p4=5, p5=5,
– Et utilisant respectivement 8, 7, 10, 10, 4 et 4,
1, 3, 2, 3 unités de ressources 1 et 2
tâches Diagramme quantité Diagramme
T1 tâchestemps ressources ressources
20
T2 R1 temps
15
T3
T4 10
R2
T5 5

3 6 8 10 13 15 temps 3 6 8 10 13 15 temps
L.L. - Graphes 10
 Gantt pour Jobshop
● Pour visualiser une solution
– J1 = {(M1,2), (M2, 1), (M4, 2)}
Données du
– J2 = {(M2,2), (M3, 1), (M4, 1)} problème
jobshop
– J3 = {(M3, 1), (M4, 2)}
– J4 = {(M1,1), (M2, 1), (M3, 2)}

Diagramme
machinestemps
d'une solution

L.L. - Graphes 11
 Résolution dans les cas simples
● Pour chaque tâche
– durée
– contraintes d'antériorité

● Trouver un ordonnancement des tâches avec une

date d'exécution pour chacune d'entre elles

● Tâches critiques : ne peut être retardées sans

reporter la fin du projet

L.L. - Graphes 12
 Représentation par graphes

● 2 représentations
– Potentiel  tâches
MPM : Méthode Potentiels Metra
tâches sur les sommets, potentiels sur les arcs
(B Roy – superstructures du France)

– Potentiel  étapes
PERT : Program Evaluation and Review Technique
tâches sur les arcs, potentiels sur les sommets
(US Navy pour les 6000 constructeurs missiles
Polaris - 1950)

L.L. - Graphes 13
 Méthode MPM
● Méthode Potentiels Metra

– tâches sur les sommets (Ti)

– contraintes temporelles sur les arcs (ti : durée de Ti)
90
Ti Tj

– précédences entre tâches

– deux tâches fictives de début et fin

– tout sommet sans prédecesseur est relié à début (0)

– tout sommet sans successeur est relié à fin
L.L. - Graphes 14
 Représentation MPM
Exemple - repas
Tâches
● T1 : menu (30 min) ● T5 : mettre la table (10
min)
● T2 : achats (90 min)
● T6 : épluchage (30 min)
● T3 : apéritif (30 min)
● T7 : cuisiner (30 min)
● T4 : ménage (10 min)
● T8 : servir (10 min)
Contraintes
● Menu en premier ● Achats avant épluchage
● Servir après cuisiner ● Apéritif avant servir
● Ménage avant table
● Eplucher avant cuisiner

L.L. - Graphes 15
 Représentation MPM
Exemple - repas
Contraintes
● Menu (T1) en premier ● Achats avant épluchage
● Servir après cuisiner ● Apéritif avant servir
● Ménage avant table
● Eplucher avant cuisiner

T2
30 T5
30

T1 T6 ● T1 sert de tâche initiale

30 3030 Pas de tâche finale
30 30
●

T4
T3
T7

T8
L.L. - Graphes 16
 Représentation MPM
Exemple - repas
Contraintes
● Menu en premier ● Achats avant épluchage
● Servir (T8) après cuisiner ● Apéritif avant servir
(T7)
● Ménage avant table
● Eplucher avant
T2cuisiner
30 T5 ● Tâche finale
30 ● Tous reliés à fin
● Durée de T8
T1 T6
30 3030
30
T4
T3
fin
10
T7
L.L. - Graphes 30 T8 17
 Représentation MPM
Exemple - repas
Contraintes
● Menu en premier ● Achats avant épluchage
● Servir après cuisiner ● Apéritif avant servir
● Ménage (T4) avant table (T5)
● Eplucher avant cuisiner
● Tous reliés à fin
au fur et à
T2 mesure
30

T1 T6 T5
30 3030 10 10 fin
30
T4
T3
10
T7
L.L. - Graphes 30 T8 18
 Représentation MPM
Exemple - repas
Contraintes
● Menu en premier ● Achats avant épluchage
● Servir après cuisiner ● Apéritif avant servir
● Ménage avant table
● Eplucher (T6) avant
cuisiner (T7)
T3
30 T4
T1 30 10 T5
10 fin
30 30 T8 10
30
T6 30 T7
T2
L.L. - Graphes 19
 Représentation MPM
Exemple - repas
Contraintes
● Menu en premier ● Achats (T2) avant
● Servir après cuisiner épluchage (T6)
● Ménage avant table ● Apéritif avant servir
● Eplucher avant cuisiner

T3
30 T4
T1 30 10 T5
10 fin
30 T8 10
30
90 T6 30 T7
T2
L.L. - Graphes 20
 Représentation MPM
Exemple - repas
Contraintes
● Menu en premier ● Achats avant épluchage
● Servir après cuisiner ● Apéritif (T3) avant servir
● Ménage avant table (T8)
● Graphe final
● Eplucher avant cuisiner sans redondances

T4
T1 30 10 T5
30 T3 10 fin
30
30 10
T8
T6 30 T7 30
T2 90

L.L. - Graphes 21
 Représentation MPM
Calcul des dates
● Sommets : tâches Ti avec :
tâche
– des dates au plus tôt ti Au plus tôt Au plus tard
ti t'i
– et dates au plus tard t'i

● Une étape début, une étape fin de projet

● Le but de l'algorithme calcDates est de calculer les
dates au plus tôt/au plus tard pour chaque tâche :
● Marge totale : t'i – ti
● Marge libre : min Tj  (Ti)
tj - (ti + di)
– Identifier les chemins critiques : marge totale
nulle
L.L. - Graphes 22
 Représentation MPM
Calcul des dates
● Marge libre : min Tj  (Ti) tj - (ti + di)
Temps maximal dont la tâche peut être retardée ou
allongée sans retarder la fin du projet,
indépendamment des autres tâches (10 pour T1)
(sans impact possible sur les tâches)
T1 0 10 T3 20
0 20 5
d 0 T2 20 f
30
0 30
T4
● Marge totale : t'i – ti
Temps maximal dont la tâche peut être retardée ou
allongée sans retarder la fin du projet (15 pour T1)
(impact possible sur le début des autres tâches)
L.L. - Graphes 23
 Représentation MPM
Calcul des dates
● 2 passes :
– Calcul des dates au plus tôt ti
– Puis des dates au plus tard t'i
● Tri topologique des sommets

T4
T1 30 10
T5
30 10
T3 fin
30 30
30 10
T8
T6 30 T7 30
T2 90

N0 N1 N2 N3 N4 N5
L.L. - Graphes 24
 Représentation MPM
Calcul des dates au plus tôt
● Date ti à laquelle peut commencer l'exécution d'une
tâche
– Tri topologique, et ti=0 au niveau N0
– Pour chaque niveau, à partir du niveau N1
● Pour tous les sommets à ce niveau
ti = max Tj  préds(Ti)
tj + d j

30 T7 50
T1 T8
30
0 30 30 150
T2 90 T6
30 120
L.L. - Graphes N0 N1 N2 N3 25
 Représentation MPM
Calcul des dates au plus tard
● Date ti' à laquelle peut commencer l'exécution d'une
tâche sans retarder les tâches suivantes
– Pour chaque niveau, par ordre décroissant à partir
du dernier
● Pour tous les sommets à ce niveau
ti' = min Tj  succs(Ti)
t j' - d i

+tôt
30 T7 50 +tard
T1 T8
30
0 100 30 150
0 30
90 T6 150
T2
30 120
30 120
L.L. - Graphes N0 N1 N2 N3 26
 Représentation MPM
Chemin critique
● Dates ti et ti' identiques : tâches ne pouvant être
retarder sans sans retarder l'ensemble du projet

+tôt
=
30 T7 50
T1 T8 +tard
30
0 100 30 150
0 30
90 T6 150 T
T2
30 120 Tâches
30 120
N0 N1 N2 N3 critiques

L.L. - Graphes 27
 Représentation MPM
Calcul des dates
● T1 : menu ● T5 : mettre la table
● T2 : achats ● T6 : épluchage
● T3 : apéritif ● T7 : cuisiner
30 40
● T4 : ménage ● T8 : servir 170 180
T4 10 T5
0 30 30 150 10
0 T3
30 30
T1 T8 10 fin
30 T7 30
180 190
30 150 180 190
30 150
T6
90
T2 120
L.L. - Graphes 30 30 120 28
 Représentation PERT
potentiels  étapes
● Sommets : étapes
étape
– Les arcs représentent
Au plus tôt Au plus tard
les tâches ti t'i

● Une étape début, une étape fin de projet

● Même but de calcul du chemin critique et de
détermination de la durée totale du projet que avec
MPM (date de l'étape de fin)

L.L. - Graphes 29
 Représentation PERT
Tâches
étape
● Arcs : tâches
Au plus tôt Au plus tard
– nom ti t'i
– durée
Ti 90 Tj 50
● Tâches successives

● Tâches simultannées Ti 90

Tj 50
● Taches fictives Tk 60
Ti 90
Ti précède Tq
L.L. - Graphes
Tj 50 Tq 10 30
 Représentations MPM et PERT
Exemple - travaux
MPM
parquet
6
fin
début
Salle de
5
Carrelage 2
bain sdb
3 3

électricité 3 peinture

PERT Parquet 6

Sdb 5 carrelage 2
d f

électricité 3 peinture 3
220

L.L. - Graphes 31
 Représentation PERT
Exemple - repas
● T1 : menu (30 min) ● T5 : mettre la table (10
min)
● T2 : achats (90 min)
● T6 : épluchage (30 min)
● T3 : apéritif (30 min)
● T7 : cuisiner (60 min)
● T4 : ménage (10 min)
● T8 : servir (10 min)

début C
0 0 150210
T3 30
T1 30

A T2 90 B F T7 30 G
T8 10
30 30 120120 150150 180180
T6 30
fin
T4 10 190190
D T5 10 E
40 200 50 210
L.L. - Graphes D'après wikipedia.org 32
 Représentation Jobshop
graphe disjonctif
● Exemple :
● J1 = {a=(M1,2), b=(M2, 1), c=(M4, 2)}
● J2 = {d=(M2,2), e=(M3, 1), f=(M4, 1)}
● J3 = {g=(M3, 1), h=(M4, 2)} Contraintes de
précédence des
● J4 = {i=(M1,1), j=(M2, 1), k=(M3, 2)} taches

a b c J1

d e f J2
0
1
g h J3

i j k J4
L.L. - Graphes 33
 Représentation Jobshop
graphe disjonctif
● M1 : J1 J4
● M2 : J2 J1 J4 Contraintes
d’exclusivité
● M3 : J3 J2 J4 Des machines
M4 : J3 J2 J1
cliques
●

M1 M2 M3 M4
a b c

d e f
0
1
g h

i j k
L.L. - Graphes 34
 Représentation Jobshop
graphe disjonctif
● Une solution:
Choisir une direction
– M1 : J1 J4
Pour les arêtes
– M2 : J2 J 1 J4
PAS DE CYCLE
– M3 : J 3 J 2 J 4
– M4 : J3 J 2 J 1

M1 M2 M3 M4

L.L. - Graphes 35
 Représentation Jobshop
graphe disjonctif
● J1 = {a=(M1,2), b=(M2, 1), c=(M4, 2)} Appliquer les
algorithmes de
● J2 = {d=(M2,2), e=(M3, 1), f=(M4, 1)} calcul des dates
● J3 = {g=(M3, 1), h=(M4, 2)}
Jobshop: choix des
● J4 = {i=(M1,1), j=(M2, 1), k=(M3, 2)} arêtes qui minimise
la date finale
M1 M2 M3 M4
2 1
a b c
2
0 2 1 2 1
2 2
0 d e f
0 1 1 11
0 g h
2 1
0 2
1 1
i j k 2
L.L. - Graphes 36
 Recherche dans les arbres de jeu
● Jeux visés :
– Jeux à deux joueurs
– Sans hasard (≠ dés)
– Complètement informés (≠ cartes)

Jeux de stratégie (échecs, dames, othello…)

... à la main

... par ordinateur

Deeper Blue bat Kasparov en

1997
L.L. - Graphes 37
 Recherche dans les arbres de jeu
● Représentation du problème
arbre de jeu

● Recherche d’une stratégie gagnante

● recherche exhaustive

● recherche heuristique

● Recherche du meilleur coup à jouer

● algorithmes min-max

● Alpha-beta
?

● Profondeur de l'arbre ?
L.L. - Graphes 38
 Arbres de jeu
● Arbre tel que :

● La racine = état initial du jeu

● Un arc = un coup possible
● Un nœud = un état possible du jeu
● Une feuille = une fin de partie possible
(victoire d’un des joueurs ou nul)

L.L. - Graphes 39
 Exemple
Le jeu de Gründy
• Principe du jeu
On a une pile de n allumettes. Chaque joueur à son tour
divise une pile en deux piles non égales . Le premier qui
ne peut plus jouer a perdu.

L.L. - Graphes 40
 Exemple
Le jeu de Gründy
• Principe du jeu
On a une pile de n allumettes. Chaque joueur à son tour
divise une pile en deux piles non égales .
Le premier qui ne peut plus jouer a perdu.

Construire l'arbre du jeu ...

L.L. - Graphes 41
 Le jeu de Gründy

• Arbre du jeu pour 6 allumettes

5+1 4+2

3+2+1 4+1+1 3+1+2 Qui gagne

quand ?

2+1+2+1 2+1+1+2

L.L. - Graphes 42
 Stratégie de recherche

• Du point de vue d'un des 2 joueurs, trouver une stratégie

qui permet de gagner à coup sûr.
– Arbre ET/OU
– Stratégie : Sous-graphe gagnant dans l'arbre ET/OU
6

5+1 4+2

3+2+1 4+1+1 3+1+2

2+1+2+1 2+1+1+2
L.L. - Graphes 43
 Arbre ET/OU

• Du point de vue du joueur A, il suffit qu'un coup mène à la

victoire si c'est à lui de jouer : il le choisira
Noeud OU

6
A joue
OU
5+1 4+2

B joue ET ET

3+2+1 4+1+1 3+1+2

OU OU
A joue

2+1+2+1 2+1+1+2
L.L. - Graphes 44
 Arbre ET/OU

• Du point de vue du joueur A, il faut que tous les coups

mènent à la victoire quand c'est à B de jouer.
Noeud ET

6
A joue
OU
5+1 4+2

B joue ET ET

3+2+1 4+1+1 3+1+2

OU OU
A joue

2+1+2+1 2+1+1+2
L.L. - Graphes 45