Probl mes dordonnancement des
ateliers de type 1|5 |5
Niveau : 4 me ann e G nie Industriel
Rihab MECHMECH
2021-2022
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Probl mes dordonnancement de type 1|5 |5
Mod lisation math matique des probl mes
dordonnancement
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Probl mes dordonnancement de type 1|5 |5
Mod lisation math matique des probl mes
dordonnancement
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Introduction
" Les probl mes dordonnancement de type 1|5 |5 consid rent une seule et unique ressource
(ex: machine). Le but de ces probl mes est doptimiser le crit res 5 choisi tout en respectant
les contraintes 5 impos es.
" La r solution du probl me dordonnancement plusieurs machines peut recourir aux
m thodes de r solution des probl mes dordonnancement une seule machine.
" Pb int ressant: goulot d tranglement.
Objectifs r soudre :
" Minimisation de la dur e totale 565Z5N5e.
" Minimisation des encours 595V ou aussi 5d5V595V.
" Minimisation des retards /p nalit s dues aux retards 5G5V , 5H5V, 5?5Z5N5e, 5G5Z5N5e.
Plan du cours
1
2
3
4
5
Introduction et probl matique g n rale
Probl mes dordonnancement de type 1|5 |5
Mod lisation math matique des probl mes
dordonnancement
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Probl mes tudier
" 1|5_5V|5G5Z5N5e
" 1 || 5G5V
" 1 || 5H5V
Hypoth ses communes implicites:
" Ordre intangible.
" Temps de transport et de lancement nuls.
" Temps op ratoires certains.
" Pas de recouvrement.
" 1||565Z5N5e
" 1|5C5_5R5P|565Z5N5e
" 1|5_5V|565Z5N5e
" 1 || 565V
" 1 || 595V
" 1 || 5d5V565V
" 1|5_5V| 565V
" 1|5_5V, 5]5_5Z5]| 565V
" 1||5?5Z5N5e
1||5j5 5 5
Pour le probl me 1||565Z5N5e , il existe 5[! ordonnancement possibles ayant la m me dur e qui est
gale la somme de 5]5V 5]5V toutes les solutions sont optimales.
" Un probl me 1 seule machine
" Objectif: minimiser le makespan 565Z5N5e
" Toutes les t ches sont disponibles linstant t = 0
565Z5N5e = 16
5V
5]5V
1
3
2
4
3
7
4
2
M1
1
2
3
4
0 3 7 14 16
1|5w5 5 5 |5j5 5 5
il nexiste forc ment pas 5[! ordonnancement possibles.
Pour le probl me 1|5]5_5R5P|565Z5N5e ,
Toutefois, pour les ordonnancements possibles, la dur e est la m me et est gale la somme
de 5]5V ( 5]5V).
" Un probl me 1 seule machine
" Objectif: minimiser le makespan 565Z5N5e tout en respectant la pr c dence des t ches
Supposons quon dispose de 6 t ches pour la fabrication dun produit donn :
" La t che 3 pr c de les t ches 2,4,5.
" La t che 3 doit tre ex cut e apr s la t che 1.
" La t che 5 ne peut tre ex cut e quapr s les t ches 4 et 6.
5V
5]5V
1
3
2
4
3
7
4
2
5
2
6
8
Supposons quon dispose de 6 t ches pour la fabrication dun produit donn :
" La t che 3 pr c de les t ches 2,4,5.
" La t che 3 doit tre ex cut e apr s la t che 1.
" La t che 5 ne peut tre ex cut e quapr s les t ches 4 et 6.
M1
1
1
1
1
3
3
3
3
565Z5N5e = 26
2
2
6
2
6
2
4
6
4
4
4
6
5
5
5
5
" Un probl me 1 seule machine
" Objectif: minimiser le makespan, 565Z5N5e , sous contrainte de disponibilit
1|5 5 |5j5 5 5
5V
5]5V
5_5V
2
1
3
0
2
4
5
3
7
3
4
2
9
3
565Z5N5e = 18
4
M1
1
0 3 5 9 16
18
M1
1
3
Advertisement
4
2
565Z5N5e = 16
0 3 10 12 16
Comment avoir lordonnancement optimal ?
Th or me :
Un ordonnancement est optimal pour5 |5 5 |5j5 5 5 si et seulement si les
t ches sont rang es dans lordre croissant de 5 5 (FIFO).
2
4
5
3
7
3
4
2
9
5V
5]5V
5_5V
1
3
0
3
565Z5N5e = 16
2
4
M1
1
0 3 10 14 16
" Un probl me 1 seule machine
" Objectif: minimiser la somme des encours
" Toutes les t ches sont disponibles linstant t = 0
5 || 5m5
595V = 565V-5_5V 595V = 565V - 5_5V
Donc:
5@5V5[5Z5V5`5R5_ 595V = minimiser 565V pour
le cas sans contraintes 5_5V.
5 || 5m5
1 || 565V
5V
5]5V
2
M1
1
5 || 5j5
1
3
2
4
3
7
4
2
3
565V = 40
4
0 3 7 14 16
M1
4
1
2
3
0 2 5 9
16
Est-ce la valeur optimale ?
565V = 32
5 || 5j5
Lemme :
Un ordonnancement est optimal pour 1 || 565Vsi et seulement si 5]5V d 5]5V+1
SPT : Shortest Processing Time
Un ordonnancement est optimal pour 1 || 565V si et seulement si
t ches sont rang es dans lordre croissant de 5]5V.
les
5 || 5 5 5j5
" Un probl me 1 seule machine
" Objectif: minimiser la somme des encours tout en consid rant des poids ( importance, co ts,
poids des clients, etc.)
" Toutes les t ches sont disponibles linstant t = 0
5V
5]5V
5d5V
1
3
2
2
4
5
3
7
1
4
2
1
5 || 5 5 5j5
" Un probl me 1 seule machine
" Objectif: minimiser la somme des encours tout en consid rant des poids ( importance, co ts,
poids des clients, etc.)
" Toutes les t ches sont disponibles linstant t = 0
" Compar au cas pr c dent, on utilisera la SPT pond r e (Weighted SPT, WSPT).
R gle de Smith : WSPT :
Un ordonnancement est optimal pour 1 || 5d5V565V si et seulement si les
t ches sont rang es dans lordre croissant de 5]5V/5d5V.
5 || 5 5 5j5
5V
5]5V
5d5V
5 5 /5 5
1
3
2
2
4
5
1,5
0,8
3
7
1
7
4
2
1
2
M1
2
1
4
3
0 4 7 9 16
565V = 36
5 |5 5 | 5j5
" Un probl me 1 seule machine
" Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilit des
t ches.
2
4
5
3
7
3
5V
5]5V
5_5V
1
3
0
3
4
2
9
2
565V = 43
4
Lordre croissant de 5 5 :
M1
1
0 3 10 14 16
Lordre 1-2-3-4 :
M1
1
2
3
565V = 51
4
0 3 5 9 16
18
Comment avoir lordonnancement optimal ?
Th or me :
Les probl mes 5 |5 5 | 5 5 5j5 ,5 |5 5 | 5j5 et5 5 5 , 5 5 5 5 5 5 5j5 sont des
probl mes NP-difficile. Toutefois, il est possible de r soudre le probl me :
5 5+5", 5)5+5&5) 55" .
R solution du probl me 5 5+5", 5)5+5&5) 55": SRPT (Shortest Remaining
Processing Time)
Affecter la machine la t che de plus courte dur e sous la condition
suivante : quand une t che arrive, elle pr empte la machine si sa dur e
est plus petite que la dur e r siduelle de la t che en cours.
Advertisement
" Un probl me 1 seule machine
" Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilit des
5 |5 5 , 5 5 5 5 | 5j5
t ches.
M1
5V
5]5V
5_5V
1
3
0
2
4
5
3
7
3
4
2
9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
" Un probl me 1 seule machine
" Objectif: minimiser la somme des temps de traitement tout en respectant la disponibilit des
5 |5 5 , 5 5 5 5 | 5j5
t ches.
M1
1
2
4
5
3
7
3
4
2
9
5V
5]5V
5_5V
1
3
0
3
0 3 5
Seule la t che 3 est
disponible
La t che 2 est d sormais disponible
Temps restant pour la t che 3 est de 5
Temps restant pour la t che 2 est de 4
On interrompe la t che 3 et on
commence la t che 2.
5 |5 5 , 5 5 5 5 | 5j5
On termine la t che 3.
M1
1
3
2
4
3
0 3 5 9 11 16
partir du 9, la t che 4 est disponible.
Temps restant pour la t che 3 est de 5.
Temps restant pour la t che 4 est de 2.
donc je choisi la t che 4.
565V = 44
1||5s5 5 5
" Un probl me 1 seule machine
" Objectif: minimiser le retard.
" 5?5V = 565V 5Q5V : le retard alg brique.
" 5G5V = 5@5N5e (0, 565V 5Q5V ) : le vrai retard.
5V
5]5V
5Q5V
1
3
3
2
4
6
3
7
18
4
2
9
1||5s5 5 5
Th or mes : r gle de Jackson EDD : Earliest Due Date
Un ordonnancement est optimal pour 1 || 5?5Z5N5e si les t ches sont rang es
dans lordre croissant de 5Q5V.
5V
5]5V
5Q5V
565V 5Q5V
1
3
3
0
2
4
6
1
3
7
18
-2
4
2
9
0
M1
1
2
4
3
5?5Z5N5e = 1
0 3 7 9
16
Th or mes : r gle de Jackson EDD : Earliest Due Date
Un ordonnancement est optimal pour 1 ||5s5 5 5 si les t ches sont rang es
dans lordre croissant de 5Q5V.
EDD minimise le plus retard vrai =5{5 5 5
Toutefois, un ordonnancement qui minimise 5{5 5 5 ne minimise forc ment
pas 5s5 5 5 .
1|5 5 |5{5 5 5
" Un probl me 1 seule machine
" Objectif: minimiser le retard maximal sous contraintes de disponibilit .
" 5?5V = 565V 5Q5V.
" 5G5V = 5@5N5e (0, 565V 5Q5V ).
N.B: Les probl mes qui consid rent la fois les contraintes de disponibilit et celles de la date
de fin souhait e (5_5V et 5Q5V ) sont g n ralement difficiles r soudre.
Toutefois, si la pr emption est permise, a facilitera la r solution.
1|5 5 |5{5 5 5
1|5 5 , 5 5 5 5 |5{5 5 5
R solution: EDD modifi e
tout instant, affecter la machine, la pi ce disponible avec 5Q5V minimal.
1|5 5 , 5 5 5 5 |5{5 5 5
5V
5]5V
5Q5V
5_5V
1
3
3
0
2
4
6
5
3
7
18
3
4
2
9
9
M1
1
3
2
4
3
0 3 5 9 11 16
1|5 5 , 5 5 5 5 |5{5 5 5
5V
5]5V
5Q5V
5_5V
565V - 5Q5V
5G5V
1
3
3
0
0
0
2
Advertisement
4
6
5
3
3
3
7
18
3
-2
0
4
2
9
9
2
2
M1
1
3
2
4
3
0 3 5 9 11 16
5G5Z5N5e = 3
" Un probl me 1 seule machine
" Objectif: minimiser la somme des retards.
" 5G5V = 5@5N5e (0, 565V 5Q5V ) (tardiness).
5 || 5{5
5l5k5k, 5{5 = 5 5
M1
2
1
5V
5]5V
5Q5V
565V - 5Q5V (EDD)
565V - 5Q5V (SPT)
1
3
6
1
-1
3
2
4
5
-1
4
4
2
12
4
-10
3
7
9
5
7
4
0 4 7 14 16
SPT, 5{5 = 5 5
M1
4
1
2
3
0 2 5 9 16
Comment avoir lordonnancement optimal ?
Heuristique MDD :
Le probl me 5 || 5{5 est NP-difficile au sens fort.
Donc on propose le recours lheuristique de Baker et Bertrand qui se
base sur la r gle MDD (modified due date) o :
5@57575V 5a = max(5a + 5]5V, 5Q5V)
" 5@57575V 5a est le d lai modifi de la t che 5V la date 5a
" Heuristique 5@57575V 5a
: la date 5a , d s que la machine devient
disponible, on affecte la t che 5V ayant le plus faible 5@57575V 5a
" Un probl me 1 seule machine
" Objectif: minimiser la somme des retards.
" 5G5V = 5@5N5e (0, 565V 5Q5V ).
5 || 5{5
5V
5]5V
5Q5V
1
3
6
2
4
5
3
7
9
4
2
12
5@57575V 5a = max(5a + 5]5V, 5Q5V)
5 || 5{5
t
0
5@57575V
1
6
2
5
3
9
4
12
M1
2
0 4
5@57575V 5a = max(5a + 5]5V, 5Q5V)
t
0
4
5@57575V
5@57575V
5 || 5{5
1
6
7
2
5
--
3
9
11
4
12
12
M1
2
1
0 4 7
5@57575V 5a = max(5a + 5]5V, 5Q5V)
t
0
4
7
5@57575V
5@57575V
5@57575V
5 || 5{5
1
6
7
--
2
5
--
--
3
9
11
14
4
12
12
12
M1
2
1
4
3
0 4 7 9 16
5@57575V 5a = max(5a + 5]5V, 5Q5V)
t
0
4
7
5@57575V
5@57575V
5@57575V
565V-5Q5V
5G5V
Advertisement
5{5 = 8
5 || 5{5
1
6
7
--
1
1
2
5
--
--
-1
0
3
9
11
14
7
7
4
12
12
12
-3
0
M1
2
1
4
3
0 4 7 9 16
Exemple 2 6 5t5k5k 5 || 5{5
" Un probl me 1 seule machine
" Objectif: minimiser le nombre des retards
" 5H5V = 0 si 565V d 5Q5V , 5H5V = 1 sinon.
5 || 5|5
5V
5]5V
5Q5V
565V 5Q5V
5G5V
5H5V
1
3
6
-3
0
0
2
4
5
2
2
1
3
7
9
-3
0
0
4
2
12
7
7
1
5t5k5k, 5|5 = 5
M1
1
2
4
3
0 3 7 9 16
5 || 5|5
Est-ce lordonnancement optimal ?
Algorithme dHodson et Moore :
Le probl me 5 || 5|5 est polynomial qui peut tre r solu par lalgorithme dHodson et
Moore :
1. Ranger les travaux selon la r gle 5l5k5k = 5h
2. D terminer les5j5
3. Soit 5E =
4. Tant quil existe des travaux en retard dans 5h faire :
" soit 5X, la position du premier travail en retard
" soit 5? le plus long travail (en terme de 5 5 ) parmi les 5X premiers (qui pr c dent
le 1er retard)
54 = 54 {5?} et 5E = 5E + {5?}
" Avancer les t ches en aval de 5? (sans modifier lordre 585757)
" d terminer les 5j5
5. Les s quences optimales sont donn es par les l ments de 54 ordonnanc s selon
585757 suivis par les l ments de 5E dans un ordre quelconque.
5 || 5|5
5V
5]5V
5Q5V
565V 5Q5V
5H5V
1
3
6
1
1
2
4
5
-1
0
3
7
9
5
1
4
2
12
4
1
1. Ranger les travaux selon la r gle 5l5k5k 6 5 5 5 5
M1
2
1
3
4
0 4 7 14 16
5 || 5|5
5]5V
5Q5V
5H5V
1
3
6
0
4
2
12
0
2
4
5
1
3
7
9
1
A
Condition darr t :
Pas de retard dans lensemble A
R
M
1
1
4
2
3
0 3 5 9 16
Application :5 || 5|5
Remarques &
Ratio critique
On calcule le ratio du temps de traitement dune t che sur le temps restant avant la date
le plus lev
promise.
(Traitement par ordre d croissant du CR).
la priorit est donn e la commande dont
le ration critique est
5E56 =
5Q5N5a5R 5]5_5\5Z5V5`5R 5a5R5Z5]5` 5Q25\5] 5_5N5a5V5\5[
5a5R5Z5]5` 5Q25\5] 5_5N5a5V5\5[
Remarques &
Le stretch d'une t che est d fini comme son temps dans le syst medivise par sa dur e (le
rapport entre son temps d' coulement et son temps de traitement requis)
Stretch
5F5V =
565V
5]5V