1.4.1 Problèmes de flow shop avec prise en compte
des dates de disponibilitéet des délais de livraison
Le problème que nous considérons
Fm+1 T = in,
ri, qi Cmax
est une généralisation du problème de flow shop à
une machine 1 ri, qi
Cmax et ce dernier est
équivalent à 1 ri
Lmax [71].
Selon deux revues proposées par Nowicki et al.
[56] et Grabowski et al.[30], ces problèmes ont
reçu une considérable attention depuis les années 70. Bien
que Lenstra et al. [50] ont montréque le problème 1
ri, qi Cmaxest
NP-difficile au sens fort, il existe des algorithmes polynomial pour certains
cas particuliers [49].
Les méthodes énumératives pour
résoudre les problèmes 1 ri, qi
Cmax et 1 ri
Lmax ont
étéétudiés dans [30, 8, 3, 52]. Les tests ont mis
l'accent sur l'algorithme de Carlier [8] qui s'est avéréle plus
prometteur notamment pour les grandes tailles des problèmes (il a
réussi à résoudre des problèmes de tailles allant
jusqu'à10.000 jobs).
Grabowski [30] a proposéune PSE pour le problème
1 ri Lmax basésur
la notion des blocs de jobs, il affirme que son approche a réussi
à résoudre les problèmes F2 ri
Lmax et F ri
Lmax.
Problèmes d'ordonnancement 16
L'auteur a proposéune règle permettant d'avoir un
ordonnancement op-
Cmax. Ce résultat a
étéamélioréavec un rapport de5
4. Dans ce contexte, Hall et Shmoys [35] ont
proposéun algorithme avec un rapport d'approximation de 4
3. Ils ont également proposédeux
schémas d'approximation. D'autres algorithmes approximatifs pour ce
même problème ont étéétudiés dans [56,
64, 60, 45, 8].
1.4.2 Méthodes heuristiques
Les méthodes heuristique sont les plus utilisées
pour la majoritédes problèmes d'ordonnancement, et elles semblent
être la seule approche de résolution des problèmes de
grande taille. Les travaux sont nombreux, nous ne rappelons ici que ceux qui
ont influencénos travaux, en commençant par Johnson [40], Palmer
1965 [59], Campbell et al. 1970 [7], Nawaz et al. 1983 [55]
et Potts 1985 [60].
+ Heuristique de Johnson [40]
S. M Johnson présentait en 1954 un papier qui a
traitéles problèmes de flow shop à deux machines ayant
pour objectif la minimisation du makespan F2 || Cmax et celui
à trois machines F3 || Cmax. Cet article est
probablement le plus citédans la littérature.
Algorithme 1.1: Algorithme de Johnson
début
Soient, 81 et 82 deux séquences
partielles.
-, Étape 1 :
81 = Ø et 82 =
Ø
-, Étape 2 :
Chercher dans J le job Ji0 tel que
:
ai0 = min{ai, bi} ou bi0 = min{ai,
bi}
i?J i?J
-, Étape 3 :
si ai0 = min{ai, bi}
alors
i?J
Placer Ji0 à la fin de 81
si bi0 = min{ai, bi}
alors
i?J
Placer Ji0 au début de 82
si J =? Ø alors
Aller à l'étape 2
retourner solution optimale en
concaténant 81 et 82.
Problèmes d'ordonnancement 17
timal, elle peut être décrite comme suit : soient
ai et bi les durées opératoires respectivement
pour la première et la deuxième machine, si pour deux job i
et j on a min(ai, bj) min(aj, bi) alors il
existe une solution optimale oùle job i précède
j.
L'Algorithme 1.1 formulépar Carlier et al. [9]
illustre cette règle.
Selon Conway et al. [14], cet article a pousséla
communautédes chercheurs en ordonnancement à accepter le makespan
comme critère d'optimi-sation. La complexitéde l'algorithme de
Johnson est de O(nlogn).
+ Heuristique de Palmer [59]
Cette heuristique a étéaussi proposéparmi
les premières heuristiques développées pour le Fm
|| Cmax, elle est une extension de la règle SPT
(Shortest Processing Time) dans la mesure oùles jobs sont
classés dans l'ordre croissant de leur tendance à avoir des temps
opératoires plus long à la fin de la séquence
d'opération.
Cette heuristique consiste à calculer pour chaque job
un indice comme suit :
f(i) = ?n (m -
2j + 1).Pij Vi E {1,...,n} j=1
Les jobs seront ensuite ordonnancés selon l'ordre
croissant de leurs indices. La complexitéde cette heuristique et de
O(nlogn + n.m).
+ Heuristique NEH [55]
Nawaz et al. ont proposéune heuristique de
construction pour le Fm || Cmax. L'idée
consiste à construire itérativement une solution complète
en cherchant à chaque fois d'insérer un job non
ordonnancéau meilleur emplacement dans une séquence partielle.
Cette heuristique a une complexitéde O(m x
n2).
De nombreux chercheurs notamment Taillard [66] et Framinan et
al. [20] ont confirméla supérioritéde cette heuristique
(pour plus de détails veuillez consulter [43]).
On peut illustrer cette procédure comme elle a
étéprésentée par M. Nawaz par les étapes de
l'Algorithme 1.2.
Problèmes d'ordonnancement 18
Algorithme 1.2: Heuristique NEH
?m Pij j=1
Étape O
Pour chaque jobs j calculer : Ti =
Étapes
Ordonnancer les jobs selon l'ordre décroissant de
Ti
'Etape ?
Prendre les deux premiers jobs de la liste triée à
l'étape 2 et trouver la meilleur séquence en calculant le
makespan des deux séquence
possibles. Ne pas changer l'ordre relatif des deux jobs dans le
reste de
la procédure.
Soit j = 3; Étape O
Prendre le job de la jeme position de la
liste générée à l'étape 2 et
trouver la meilleure séquence en l'insérant dans
toutes les positions possibles de la séquence partielle obtenue à
l'étape précédente sans changer l'ordre des jobs
déjàfixés. 'Etape @
Si j = n alors Arrêter la
procédure, sinon retourner à l'étape 4.
+ Heuristique de Potts [60]
C. N. Potts [60] présente des heuristiques pour le
problème F2 ri Cmax dont l'heuristique RJ qui
est une combinaison des heuristiques suivantes : L'heuristique R qui
consiste à ordonnancer les jobs selon l'ordre croissant des ri
et l'heuristique J pour ordonnancer selon l'ordre de Johnson.
L'euristique RJ consiste à ordonnancer les jobs selon l'ordre
croissant des ri puis chaque fois oùun job est disponible on
l'injecte dans la séquence en appliquant l'ordre de Johnson,
l'Algorithme 1.3 décrit cette heuristique.
L'auteur a aussi proposéune heuristique appelée
RJ' qui consiste àexécuter
l'heuristique RJ en mettant à jour la date de
disponibilitéri àchaque itération.
Grabowzki [26] affirme qu'il a testécette heuristique et
qu'elle fournit des résultats spectaculaires, ainsi elle a
donné238 solutions optimales pour 240 problèmes testés.
Problèmes d'ordonnancement 19
Algorithme 1.3: Heuristique RJ de
Potts
Étape O
Soit S : l'ensemble des jobs, K = 0
Trouver T = min{ri}
iES
Étape ?
Trouver : S' = {j j E S, ri < T, ai
< bi}
S?= {j j E S, ri < T, ai >
bi}
si S' =? 0
alors
Trouver le job i E S' avec az le
plus faible possible
si S' = 0
alors
Trouver le job i E S?avec bz le plus
grand possible
Étape ?
K +- K + 1;
Ordonnancer i à la position K ;
T +- T + az ;
S +- S - {i};
Étape O
si S = 0
alors
Arrêter l'algorithme
sinon
T = max{T, min{ri}};
iES
Aller à l'étape (c) ;
| 
