Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

2.2.6 Heuristique H6

Cette heuristique suit presque le même principe de l'heuristique H1, sauf qu'un contrôle sur la date de disponibilitéet la durée opératoire sur la machine commune s'effectue pour la construction de la première machine virtuelle qu'on utilisera pour l'ordre de Johnson, ce contrôle s'effectue de la manière suivante :

_j

ai + r si ri ~ a

av i = V 1 = i = n

a sinon

La deuxième machine virtuelle est définie par :

bv i = bi + q V 1 = i = n

Présentation des méthodes de résolution 34

les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.8.

Exemple Soit l'exemple décrit dans le Tableau 2.1, les durées opératoires sur les machines virtuelles sont données dans le Tableau 2.7

Tableau 2.7 - Machines virtuelles pour l'instance 2.1, H6

Jobs	Mv1	Mv2
J1	12	6
J2	12	14
J3	8	11
J4	15	7
J5	11	12

Maintenant on peut appliquer l'algorithme de Johson en considérant le problème F2 || Cmax, on obtient l'ordonnancement suivant :

SH6 = < J3J5J2J4J1 -

Le makespan de cette solution est Cmax(SH6) = 33.

2.2.7 Heuristique H7

Cette heuristique est une variante de l'heuristique H5, elle suit le même principe: ordonnancer à chaque itération les jobs disponibles selon l'ordre de Johnson, mais en prenant seulement compte des durées opératoires sur la machine commune en ignorant les dates de disponibilité, les durées opératoires sur la deuxième machine virtuelle est la somme des bi et qi.

La configuration des deux machines est donc la suivante :

av i = ai V 1 < i < n

bv i = bi + qi V 1 < i < n

Exemple Soit l'exemple décrit dans le tableau 2.1 :

Jobs	ri	ai	bi	qi
J1	8	4	2	4
J2	6	6	4	10
J3	2	5	9	2
J4	9	6	3	4
J5	9	2	11	1

Présentation des méthodes de résolution 35

Tableau 2.8 - Machines virtuelles pour l'instance 2.1, H7

Jobs a^v_i b^v_i

J1 4 6

J2 6 14

J3 5 11

J4 6 7

J5 2 12

L'application de l'heuristique H7 donne :

SH7 =< J3J2J5J1J4 >

Le makespan de cette solution est Cmax(SH7) = 32.

Le Tableau 2.9 résume les sept heuristiques proposées. Tableau 2.9 - Résumédes heuristiques proposées

Heuristique	Principe	Paramètres
H1	Johnson	a^vi = ri + ai b^vi = bi + qi
H2	Johnson	a^vi = ri b^vi = ai + bi + qi
H3	Palmer	Palmeri = (ri + ai) - (bi + qi)
H4	Palmer	Palmeri = (ri + ai) - bi
H5	Potts	a^vi = ri + ai b^vi = bi
H6	Johnson	az = r ai + ri si ri > ai l ai sinon b^vi = bi + qi
H7	Potts	a^vi = ai b^vi = bi + qi
Johnson	-	a^vi = ai b^vi = bi
Palmer	-	Palmeri = ai - bi
NEH	-	a^vi = ai b^vi = bi

Présentation des méthodes de résolution 36