1.3.2 Solutions de permutation
Nous allons prouver la non dominance des solutions de permutation
àl'aide de l'instance suivante du F2 ri, qi Cmax
:
Jobs ri ai bi qi
|
j1
|
10
|
3
|
13
|
5
|
|
j2
|
14
|
3
|
1
|
12
|
Pour cette instance on considère les solutions
réalisables suivantes :
1. ð' = -<
j1j2 >- pour les deux
machines (solution de permutation).
2. ð?= -<
j2j1 >- pour les deux
machines (solution de permutation).
3. ð''' = -<
j1j2 >- sur la
machine Mc puis -<
j2j1 >- pour la
machine du second étage.
En calculant les valeurs de makespan pour chacune de ces
solutions on obtient :
-
Cmax(ð') =
39 -
Cmax(ð?) =
39 -
Cmax(ð''')
= 36
On constate que le makespan de la solution du non permutation
Cmax(ð''')
est inférieur aux makespan des deux solutions de permutation, on peut
ainsi conclure quant à la non dominance des solutions de permutation
pour le problème du Flow Shop à deux machines
F2 ri, qi
Cmax, par conséquence, les solutions
de permutation ne sont pas dominantes pour
Fm+1 T
= m,ri,qi Cmax.
Bien qu'elles ne sont pas dominantes, nous avons fait le choix
de travailler avec les solutions de permutation, d'une part pour des raisons de
simplification du problème, et d'autre part car dans l'industrie on
choisit naturellement les solutions de permutation pour leurs facilitéde
mise en oeuvre.
Nous rajoutons finalement que la coexistence des deux
paramètres (date de disponibilitéet délais de livraison)
sont à l'origine de la non dominance des solutions de permutation. En
revanche les solutions de permutation sont dominantes pour les problèmes
F2 ri Cmax et
F2 qi Cmax.
Problèmes d'ordonnancement 15
En ce qui concerne les rapports d'approximation, Potts a
proposéune heuristique avec un rapport d'approximation de 4 3
pour le problème 1 ri
1.4 État de l'art
L'étude d'un problème nécessite une revue
bibliographique des travaux antérieurs portants sur le même
problème étudiéou plus généralement sur le
même axe de recherche.
Bien qu'il existe une importante littérature qui traite
les problèmes de flow shop ( Gupta et Stafford [33] l'estiment à
1200 articles), les papiers traitant le flow shop avec prise en compte des
dates de disponibilitéet des délais de livraison sont rares.
Compte tenu de la particularitéde notre problème
et l'absence -ànotre connaissance- d'articles traitant ce
problème, on va s'intéresser aux travaux qui ont traitédes
problèmes semblables au notre. En effet, la revue des travaux qui ont
traitéle problème de flow shop sériel que ce soit à
deux machine ( F2 Cmax ) ou
à in machine ( Fm
Cmax) ainsi que le flow shop hybride
avec machines dédiées
Fm+1 T = in
Cmax nous sera très utile.
Dans ce qui suit, nous exposerons une revue de
littérature pour ces problèmes.
| 
