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

1.4.4 Bornes inférieures et PSE

1.4.4.1 Bornes inférieures

Les bornes inférieures proviennent dans la plupart des cas des ordonnancement partiels [10]. Pour le problème F2 ri _Cmax, Tadei et al. [65] proposent cinq bornes inférieures applicables après la division de l'ensemble des jobs en deux sous ensembles de séquences partielles, un sous ensemble des jobs qui ont étédéjàordonnancés et un sous ensemble des jobs à ordonnancer. Ces bornes sont particulièrement utiles pour l'élaboration de PSE performante.

Problèmes d'ordonnancement 22

Dridi et al. [15] se sont inspiréde Oguz et al. pour proposer des bornes inférieures pour le problème _Fm+1 T = m _Cmax, nous ne décrivons ici que les bornes inférieures qui nous seront utiles par la suite.

Soit la première borne donnée par :

?BIDHH0 = JiEJ

ai + min JiEJ

bi

L'auteur affirme que si on considère chaque type k E {1, ... , m} séparément alors forcément la somme de ses durées opératoires sur la machine dédiée avec _minJiEk ai est inférieure à la valeur de makespan optimale. Soit BI0k = minJiEk ai + _>JiETk bi la borne inférieure qu'on vient de décrire, la borne BIDHH1 est donc la suivante :

BIDHH1 = max{ max (BI0_k); BI0; max(ai + bi)}

1<k<m JiEJ

La borne _BIDHH2 est donnée par :

BIDHH2 = E 1<k<m

min JiETk

( ? ai + min bi) ^1<k<mJiETk0

La troisième borne proposée dans [34] repose sur l'ordre de Johnson, elle consiste à créer k sous problèmes (k = {1, ... , m}) à deux machines (la machine M_c et une machine dédiée MK à chaque sous problème notéP^k), l'application de la règle de Johnson fournisse pour chaque sous problème Pk une valeur de makespan notéC^Joh

max(Pk), la borne _BIDHH3 est donc la

suivante :

BIDHH3 = max {C^Joh

max(P k)}

1<k<m

Carlier et Rebai [10] ont proposédes bornes inférieures pour la résolution du problème F_m ri, qi _Cmax, ces bornes ont étéobtenues à l'aide de l'algo-rithme de Johnson et celui de Jackson.

La première borne est obtenue par l'application du JPS (Jackson's preemptive schedule) en considérant le problème F_m ri, qi _Cmax, elle s'écrit comme suit, soient I l'ensemble de tous les jobs et k C I un ordonnancement partiel

LBCR1 = max(min jEk

rj,M+i jEk

pj,M + min qj,M) V M = 1, ... ,m (1.3) jEk

Une autre borne _LBCR2 est obtenue en appliquant l'ordre de Johnson sur deux machines consécutives M et M + 1, elle s'écrit comme suit :

LBCR1 = max(min

iEJ

ri_,M+Johnson(J, M, M+1)+min _iEJqi,M+1) V M = 1, ... , m-1

(1.4)

OùJohnson(J, M, M + 1) représente la valeur de makespan de l'ensemble des jobs J sur les deux machines M et M + 1.

Problèmes d'ordonnancement 23