Probl mes dordonnancement sur
plusieurs machines
Niveau : 4 me ann e G nie Industriel
Rihab MECHMECH
2021-2022
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Introduction et probl matique
" On dispose de m machines pour effectuer n t ches.
" Les probl mes dordonnancement plusieurs machines consid rent plus quune ressource
(ex: machine). Le but de ces probl mes est doptimiser le crit res 5 choisis 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.
" Ces probl mes consistent optimiser laffectation des t ches sur les machines, ainsi que la
s quence relative chaque machine.
" Les ressources peuvent tre identiques ou diff rentes.
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Rappel
5 |5 |5
Probl mes machines parall les :
Dans ce cas, on dispose dun ensemble de machines pour r aliser les travaux. Les travaux
se composent dune seule op ration et un travail exige une seule machine. Toute t che peut
tre ex cut e indiff remment sur une des machines mises en parall le. Lordonnancement
seffectue en deux phases : la premi re phase consiste affecter les travaux aux machines et
la deuxi me phase consiste tablir la s quence de r alisation sur chaque machine.
5 |5 |5
On distingue trois types de machines:
Machines identiques 5C5Z : la dur e dex cution est la m me pour les toutes les machines
et pour toutes les t ches.
Machines uniformes 5D5Z : chaque machine a une vitesse dex cution propre et constante.
"5Y5N 5Q5b5_ 5R 5Q25R5e 5P5b5a5V5\5[ 5c5V5a5R5`5`5R 5Q5R 5a5_5N5V5a5R5Z5R5[5a 5Q5R 5Y5N 5Z5N5P5V5[5R" est le m me pour
Le rapport
tous les travaux dune m me machine.
Machines ind pendantes 5E5Z : la vitesse dex cution est diff rente pour chaque machine
et pour chaque travail.
5C5Z||565Z5N5e
Pour le probl me 5C5Z||565Z5N5e , on cherche affecter les n t ches sur les m machines et
s quencer les t ches sur chaque machine.
" Un probl me m machines IDENTIQUES
" Objectif: minimiser 565Z5N5e
" Toutes les t ches sont disponibles linstant t = 0
1
3
2
4
3
7
4
2
5
3
6
5
5V
5]5V
6
M2
5
565Z5N5e = 16
0 3 8
M1
1
2
3
4
0 3 7 14 16
Comment avoir lordonnancement optimal ?
R gle suivre :
Un ordonnancement est optimal pour 5C5Z||565Z5N5e si et seulement si les t ches sont
rang es dans lordre d croissant de 5w5 (LPT: Longest Processing Time) :
" Une fois une machine disponible, affecter la t che ayant le plus long temps
d ex cution.
" La garantie de performance:
565Z5N5e(5?5C5G)
565Z5N5e (5B5C5G)
d
4
3
1
35Z
Comment avoir lordonnancement optimal ?
R gle suivre :
Un ordonnancement est optimal pour 5C5Z||565Z5N5e si et seulement si
rang es dans lordre croissant de 5w5 (LPT: Longest Processing Time).
les t ches sont
5V
5]5V
1
3
2
4
3
7
4
2
5
3
6
5
M2
6
2
5
4
565Z5N5e = 13
Publicité
0 5 9 11 13
M1
3
1
0 7 10
M me exemple pour 3 machines // 5C3||565Z5N5e :
1
3
2
4
3
7
4
2
5
3
6
5
5V
5]5V
5
M3
2
0 4 7
M2
6
1
0 5 8
M1
3
4
0 7 9
565Z5N5e = 9
5C5Z|5]5_5Z5]|565Z5N5e
Pour le probl me 5C5Z|5]5_5Z5]|565Z5N5e , la solution optimale est obtenue avec lalgorithme de Mac
Naughton (1959).
565Z5N5e e max
5V
5C5V
5Z
, max(5C5V)
Elle repr sente la borne inf rieure pour le probl me 5C5Z||565Z5N5e
Et la solution optimale pour 5C5Z|5]5_5Z5]|565Z5N5e
Comment avoir lordonnancement optimal ?
Algorithme de Mac Naughton :
On d finit:
5@ = 5Z5N5e 5Z5N5e5V 5C5V,
5V
5C5V
5Z
1. Mettre les t ches sur la premi re machine, selon un ordre quelconque et sans
consid rer la pr emption.
2. D couper la s quence au niveau de M et placer les t ches en aval de M sur la
machine suivante. Terminer lordonnancement des t ches non affect es sur cette
machine.
3. R p ter l tape 2 jusqu ce que toutes les t ches soient ordonnanc es.
5V
5]5V
5
M3
1
3
2
4
3
7
4
2
5
3
6
5
5@ = 5Z5N5e 5Z5N5e5V 5C5V,
5V
5C5V
5Z
= 5Z5N5e 7,8 = 8
6
0 3 8
M2
3
4
0 6 8
M1
1
2
3
0 3 7 8
Exemple 1 :
Exemple 2 :
5C5Z|| 565V
Comment avoir lordonnancement optimal ?
" Pour le probl me 1|| 565V, la SPT donne la solution optimale.
" Pour le probl me 5C5Z|| 565V , on appliquera la SPT g n ralis e qui consiste :
" Ordonnancer les t ches selon la r gle SPT.
" Affecter la premi re t che de la liste non r alis e la premi re machine disponible.
" NB: on souligne que la r gle SPT g n ralis e nest pas la seule qui optimise 5C5Z|| 565V.
5V
5]5V
1
3
2
4
3
7
4
2
M3
5
6
5
5
3
3
5C5Z|| 565V
SPT : 4-1-5-2-6-3
565V=32
0 3 10
M2
1
6
0 3 8
M1
4
2
0 2 6
Exemple :
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
5 |5 |5
Probl mes dateliers Flow Shop (56 = 5m) :
Cest un atelier s quentiel, lin aire ou aussi dit cheminement unique o les tapes de
transformation sont identiques pour tous les produits fabriqu s . Chaque Job est constitu
Publicité
dun ensemble de t ches qui doivent sex cuter sur les m mes machines dans le m me
ordre et une seule fois.
" m machines en s rie : ligne de production
" La gamme op ratoire des jobs est une chaine
" Chaque job est compos de m op rations ex cut es une la suite de lautre sur les m
machines
Pr liminaires
" On souligne que les s quences de passage des t ches sur les machines peuvent diff rer
dune machine une autre.
" Dans le cas o le changement de s quence nest pas permis : Flow shop de permutation.
un ordonnancement est dit de permutation si la s quence (lordre dex cution) des jobs
est la m me sur toutes les machines
" Une dominance est une propri t v rifi e par au moins une solution optimale.
"
les ordonnancements de permutation sont dominants pour les probl mes F2//Cmax et
F2//Ci
les ordonnancements de permutation sont dominants pour le probl me F3//Cmax.
"
" Les ordonnancements de permutation ne sont plus dominants sur 4 machines.
592||565Z5N5e
Pour le probl me 592||565Z5N5e , on cherche trouver la s quence optimale des t ches sur chaque
machine( par cons quent laffectation des t ches).
" Un probl me 2 machines en s rie.
" Objectif: minimiser 565Z5N5e
Exemple : dans un atelier, les produits passent successivement sur une machine outil M1 et
un poste de finition M2
5V
5]5V1
5]5V2
1
3
2
2
4
3
3
7
5
4
2
7
5
3
4
6
5
2
5@1 = 5@2
M2
1
2
3
4
5
6
0 3 5 7 10 14 19 26 29
31
M1
1
2
3
4
5
6
0 3 7 14 16 19 24
5V
5]5V1
5]5V2
1
3
2
2
4
3
3
7
5
4
2
7
5
3
4
6
5
2
Est-ce lordonnancement optimal ?
565Z5N5e = 31
Comment avoir lordonnancement optimal ?
R gle suivre :Algortihme de Johnson pour 5m5 ||5j5 5 5
" Former deux ensembles :
" S1 : tous les travaux tels que pi1 < pi2
" S2: tous les travaux tels que pi1 > pi2
" Les travaux ayant : pi1 = pi2 peuvent tre dans S1 ou S1
" Ordonnancer les t ches :
" S1 selon lordre croissant de pi1 (r gle SPT)
" S2 selon lordre d croissant de pi2 (r gle LPT)
" Cet ordonnancement est not SPT(1)-LPT(2)
" Remarque : Plusieurs ordonnancements peuvent tre g n r s
Algortihme de Johnson
5V
5]5V1
5]5V2
1
3
2
2
4
3
3
7
5
4
2
7
5
3
4
6
5
2
" S1 : tous les travaux tels que pi1 < pi2: 4-5
" S2: tous les travaux tels que pi1 > pi2 :1-2-3-6
" S1 selon Pi1 croissant (SPT): 4-5
" S2: selon lordre d croissant de Pi2 (r gle LPT) : 3-2-1-6
" Ordonnancement optimal : 4-5- 3-2-1-6
5@1 = 5@2
M2
4
5
3
2
1
6
0 2 9 13 18 21 24 26
M1
4
5
3
2
1
6
0 2 5 12 16 19 24
5V
Publicité
5]5V1
5]5V2
1
3
2
2
4
3
3
7
5
4
2
7
5
3
4
6
5
2
565Z5N5e = 26
593||565Z5N5e
Pour le probl me 593||565Z5N5e , on cherche trouver la s quence optimale des t ches sur chaque
machine( par cons quent laffectation des t ches).
" Un probl me 3 machines en s rie.
" Objectif: minimiser 565Z5N5e
Le probl me 5m5 ||5j5 5 5 est un probl me NP-difficile. Toutefois, dans le cas o la
deuxi me machine est domin e soit par la premi re machine soit par la troisi me
machine, autrement dit, le (min Pi1e max Pi2) ou (min Pi3e max Pi2), le probl me peut
tre r solu.
Comment avoir lordonnancement optimal ?
R gle suivre :Algorithme de Johnson pour 5m5 ||5j5 5 5
" Cr er deux machines fictives M1 et M2 dont les dur es dex cution suivantes :
" Appliquer lalgorithme de Johnson pour avoir une s quence optimale.
Pi1 = Pi1 + Pi2 et Pi2 =Pi2 + Pi3
593||565Z5N5e
5V
5]5V1
5]5V2
5]5V3
1
6
2
5
2
4
3
5
3
7
1
7
4
3
2
6
5
3
3
5
6
5
2
4
" S1 : tous les travaux tels que pi1 < pi2: 2-4-5
" S2: tous les travaux tels que pi1 > pi2 :1-3-6
1
5V
5]25V1 8
5]25V2
7
2
7
8
3
8
8
4
5
8
5
6
8
6
7
6
" S1 selon Pi1 croissant (SPT): 4-5-2
" S2: selon lordre d croissant de Pi2 (r gle LPT) : 3-1-6
" Ordonnancement optimal : 4-5-2-3-1-6
M3
M2
4
5
2
3
1
6
0 5 10 15 20 27 32
36
4
5
2
3
1
6
0 3 5 6 9 10 13 17 18 23 25 28 30
M1
4
5
2
3
1
6
0 3 6 10 17 23 28
5V
5]5V1
5]5V2
5]5V3
1
6
2
5
2
4
3
5
3
7
1
7
4
3
2
6
5
3
3
5
6
5
2
4
565Z5N5e = 36
595Z||565Z5N5e
Publicité
Pour le probl me 595Z||565Z5N5e , on cherche trouver la s quence optimale des t ches sur
chaque machine( par cons quent laffectation des t ches).
" Un probl me m machines en s rie.
" Objectif: minimiser 565Z5N5e
" m >= 3 probl me NP difficile (cas g n ral)
Heuristique CDS (Campbell, Dudek et Smith (1970) pour 5m5 ||5j5 5 5
" G n rer m-1 solutions en appliquant lalgorithme de Johnson sur (m-1)
sous probl mes deux machines fictives. La premi re regroupe les k
premi res machines, la deuxi me regroupe les k derni res machines, k
varie de 1 m-1. Les temps op ratoires de chaque t che i (i = 1...n), sur
ces deux machines fictives sont donn es par :
" Retenir la meilleure des m-1 solutions (plus faible Cmax)
Application:
Soit le probl me 3 machines et 5 t ches, dont les temps op ratoires sont donn es par le tableau ci-dessous :
1
5V
5]5V1 10
5]5V2
5
2
7
6
5]5V3
3
11
3
14
3
7
4
6
9
2
5
4
7
13
k varie de 1 m-1 k varie entre 1 et 2.
1
5V
5]5V1 10
5]5V2
5
2
7
6
5]5V3
3
11
1
5V
5]15V1 10
5]15V2
3
2
7
11
3
14
3
7
3
14
7
4
6
9
2
4
6
2
5
4
7
13
5
4
13
K=1:
m-1 solutions 2 solutions
K=2:
3
2
4
1
5
5V
5]25V1 15 13 17 15 11
5]25V2
17 10 11 20
8
Lordonnancement obtenu en appliquant lalgorithme de Johnson est 5-2-3-1-4
La s quence optimale est 5-2-4-3-1 et l'ensemble des t ches sera termin au bout de 49.
Le meilleur ordonnancement parmi ces deux solutions est 5-2-4-3-1 avec une date
d'ach vement de 49
Application
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s
Rappel
Probl mes dateliers Job Shop (56 = 5q) :
R gle suivre :Algorithme de Jackson pour 5r5 ||5j5 5 5
5=5Z||565Z5N5e
" Le probl me 5=5Z||565Z5N5e est NP-difficile pour m e 3
" Le probl me 5=2||565Z5N5e est polynomial : algorithme de Jackson
1. Soit A lensemble des t ches utilisant les machines 1 puis 2, rang es
selon la r gle de Johnson
2. Soit B lensemble des t ches utilisant les machines 2 puis 1, rang es
selon la r gle de Johnson
3. Soit C lensemble des t ches utilisant uniquement la machine 1, rang es
dans nimporte quel ordre
4. Soit D lensemble des t ches utilisant uniquement la machine 2, rang es
dans nimporte quel ordre
" Faire passer sur la machine 1 :A, puis C, puis B.
" Faire passer sur la machine 2 : B, puis D, puis A
5=2||565Z5N5e
5=2||565Z5N5e
Plan du cours
1
2
3
4
5
6
Introduction et probl matique g n rale
Machines parall les
Flow shop
Job shop
Exemples : R solution avec Lekin et Cplex
Travaux dirig s