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.1.3 Borne inférieure 3

Le principe consiste à trier les jobs selon l'ordre croissant des dates de disponibilité, puis calculer le makespan de cette séquence en ne prenant compte que des dates de disponibilitéet des durées opératoires sur la machine commune seulement, ainsi on réduit le problème à un atelier 1 ri _Cmax pour lequel l'ordre croissant des ri est optimal. On y ajoute les minimums des durées opératoires sur les machines du deuxième étage et des délais de livraison. Cette borne s'écrit comme suit :

BI3 = C* max(1 ri _Cmax) + min{bi + qi} (2.3)

i?J

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

2.1.4 Borne inférieure 4

Si on considère uniquement les jobs de type k oùk E {1, . . . , m} et en ignorant les paramètres ri et qi, le problème se réduit à un F2 || Cmax avec les machines (M_c, Mk) pour lequel l'ordre de Johnson est optimal.

La borne peut alors s'écrire comme suit :

BI4 = min{ri} + max (C^Joh

max(Mc, Mk)Typek) + min _iEJ {qi} V 1 i n (2.4)

iEJ 1<k<m

OùC^Joh

max (M_c, Mk) est le makespan correspondant à l'ordre de Johnson

pour le problème F2 || Cmax avec les machines (M_c, Mk).

2.1.5 Borne inférieure 5

Le principe est le même que la borne BI2, sauf qu'au lieu de considérer la machine commune M_c, on considère l'une des machines du deuxième étage. Cette borne s'écrit de la façon suivante :

BI5 = min {ri + ai} + max ( bi) + min {qi} (2.5)

iET ypek1<k<miET ypek

Typek

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

Les temps opératoires sur les deux machines virtuelles sont décrit dans le Tableau 2.2.

2.2 Heuristiques

Les heuristiques qu'on a implémentées sont dérivées de certaines heuristiques connues pour le F_m || Cmax et le F2 || Cmax tels que l'heuristique de Potts, NEH, l'heuristique de Palmer et la règle de Johnson.

Nous avons tout d'abord implémentéces dernières heuristiques (Johnson, Palmer, NEH) tels qu'elles sont (sans aucune modification), puis nous avons cherchéà les adapter à notre problème dont la configuration est particulière. On a commencépar tester 15 procédures différentes pour en finir avec sept procédures relativement prometteuses.

2.2.1 Heuristique H1

Cette heuristique consiste à modifier la configuration de notre problème pour qu'on puisse appliquer l'algorithme de Johnson. Le problème doit être écrit sous la forme de F2 || Cmax, ce qui nécessite la création de deux machines virtuelles. Avec le but de prendre en compte les paramètres spécifiques de notre problème à savoir la date de disponibilitéri et la date de livraison qi, les durées opératoires av i et bv i des jobs i J sur ces deux machines virtuelles sont définies comme suit :

av i = ri + ai V 1 < i < n
bv i = bi + qi V 1 < i < n

Une fois les deux machines virtuelles sont crées, on applique l'algorithme de Johnson.

Exemple Soit l'instance suivante :

Tableau 2.1 - Exemple d'instance avec n = 5 et m = 5

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 30

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

Tableau 2.2 - Machines virtuelles pour l'instance 2.1, H1

Jobs av _i bv _i

J1 12 6

J2 12 14

J3 7 11

J4 15 7

J5 11 12

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

SH1 =< J3J5J2J4J1 >.-

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