Chérif SADFI - Réunion BERMUDES 6 juin, 2002 n° 1 Influence de la distribution des temps opératoires sur le résultat de lordonnancement Chérif Sadfi Laboratoire

Chérif SADFI - Réunion BERMUDES6 juin, 2002 n° 1

Influence de la distribution des temps opératoires sur le résultat de l’ordonnancement

Chérif Sadfi

Laboratoire Gestion Industrielle, Logistique et Conception

(GILCO)

École Nationale Supérieure de Génie Industriel (ENSGI)

Institut National Polytechnique de Grenoble (INPG)


Plan de la présentation

Présentation du problème

Influence de la distribution des temps opératoires sur le résultat de l’ordonnancement : étude théorique

Influence de la distribution des temps opératoires sur le résultat de l’ordonnancement : étude expérimentale

Conclusion


Problème du flow shop

M1 M2 M3 Mm……………….

ORDO

Ordonnancement des ordres de fabrication

Notation : Fm| |Ci,m

Contrainte du problème :

La préemption n’est pas permise.

Critère d’optimisation : min (Ci)


Présentation du problème Fm| |Ci,m

C[i],j-1 + p[i],j C[i-1],j + p[i],jmax C[i],j-1 , i=1,2,…,n ; j=1,2,..,m

1

1

1

2

2

2

M1

M2

M3

C[i],j =

p[i],j : durée d’exécution du travail en position i sur la machine j

0 5 10 15

temps

3

3

3

4

4

4


Complexité du problème Fm| |Ci,m

Garey, Johnson & Sethi 1976 :

• F2| |Ci,2 : NP-difficile au sens fort

Hoogeveen & Kawaguchi 1998 :

• F2|pi,1 = p1|Ci,2 : NP-difficile au sens fort


Influence des temps opératoires

pi,j

I

p'i,j = pi,j + I'

Ci,m

RR ,*

C'i,m = Ci,m + nnm

2

12

Mieux comprendre l’impact des temps opératoires sur les résultats des méthodes d’approximation

[a,b] [a',b']


Influence des temps opératoires

I

I'

Ci,m(1) Ci,m(2)

C'i,m(1) C'i,m(2)

Ci,m(opt) …

C'i,m(opt) …

Le résultat de comparaison des performances des méthodes d’approximation est conservé sur le nouvel intervalle

Choisir un intervalle approprié pour étudier et évaluer la performance des méthodes d’approximation


Méthodes de résolution

Méthodes d’approximation :

• 2 heuristiques sont proposées (SKP1 et SKP2)

– WCP1, WCP2 et WCP3 [Wang, Chu & Proth 96]

– GS [Gonzalez & Sahni 78]

– RC [Rajendran & Chaudhuri 91]

• 5 heuristiques de la littérature :

Bornes inférieures :

• 1 borne inférieure est proposée (LB)

• 2 bornes inférieures de la littérature (LB1 et LB2) [Ignall & Scharge 65]

LB max{LB1, LB2}


Étude expérimentale

Intervalle d’étude : [0,1]

Les temps opératoires sont générés en utilisant une loi normale ou une loi uniforme dans l’intervalle [0,1].

Transformation affine de paramètres et :

[0,1] [c,d]

[a,b] [0,1]

= d – c et = c

= 1/(b – a) et = – a/(b – a)


Génération d’instances

Ui et Vi (i=1,2,…,n) : nombres générés par une loi uniforme ou par une loi normale dans l’intervalle [0,1]

k1 et k2 : charges relatives sur chaque machine

: la corrélation entre la première et la deuxième opération de chaque travail

iii

ii

UVkp

Ukp

)1(22,

11,

Étude de l’influence des différents paramètres (charges des machines, corrélation entre deux opérations d’un même travail...) sur les résultats des méthodes d’approximation


Fm| |Ci,m : cas particuliers

Ho & Gupta 1995 :

Étude de la complexité du problème sur m machines en considérant le cas d’une série de machines dominantes.

Par définition, une machine Ma domine une machine Mb (qu’on note par Ma > Mb) si :

bini

aini

pp ,,..,1

,,..,1

minmin


Fm| |Ci,m : cas particuliers

Ho & Gupta 1995 :

• Fm|idm|Ci,m : polynomial (ordonnancement par ordre

croissant des pi,n pour un premier travail fixé)

• ddm : decreasing dominant machines : M1 > M2 > … > Mm

• idm : increasing dominant machines : M1 < M2 < …< Mm

• Fm|ddm|Ci,m : polynomial (ordonnancement par ordre

croissant des pi,1)


F2| |Ci,2 : cas particuliers

Hoogeveen & Kawaguchi 1998 :

• F2|pi,2 = p2|Ci,2 : polynomial (ordonnancement par

ordre croissant des pi,1)

• F2|pi,1 pi,2|Ci,2 : polynomial (ordonnancement par

ordre croissant des pi,1)

• F2|pi,1 pi,2|Ci,2 : polynomial (O(n2logn))


Étude expérimentale

Processing times generated as real numbers in [0,1]

-20

0

20

40

60

80

100

0 20 40 60 80

n: number of jobs

be

st

so

luti

on

WCP1

WCP3

SKP1

Processing times generated as integer numbers in [5,100]

-20

0

20

40

60

80

100

0 20 40 60 80

n: number of jobs

bes

t so

luti

on

WCP1

WCP3

SKP1


Influence de l’écart type

0

20

40

60

80

100

0 20 40 60 80 100 120

n : nombre de travaux

Mei

lleu

re s

olu

tio

n (

%) WCP1

WCP2

WCP3

GS

RC

SKP1

SKP2

N(0.5, 0.25) avec k1=1, k2=0.8, =0.75

0

20

40

60

80

100

0 20 40 60 80 100 120


Mei

lleu

re s

olu

tio

n (

%) WCP1

WCP2

WCP3

GS

RC

SKP1

SKP2

N(0.5, 0.5) avec k1=1, k2=0.8, =0.75


Influence de la corrélation entre les temps

0

20

40

60

80

100

0 20 40 60 80 100 120


Mei

lleu

re s

olu

tio

n (

%) WCP1

WCP2

WCP3

GS

RC

SKP1

SKP2

N(0.7, 0.25) avec k1=1, k2=0.8, =0 N(0.7, 0.25) avec k1=1, k2=0.8, =0.75

0

20

40

60

80

100

0 20 40 60 80 100 120


Mei

lleu

re s

olu

tio

n (

%) WCP1

WCP2

WCP3

GS

RC

SKP1

SKP2


Conclusion

Étude du comportement de la fonction objectif et du résultat de l’ordonnancement suite à une variation des temps opératoires

Influence de la distribution des temps opératoires sur les méthodes d’approximation

Documents

Chérif SADFI - Réunion BERMUDES 6 juin, 2002 n° 1 Influence de la distribution des temps opératoires sur le résultat de lordonnancement Chérif Sadfi Laboratoire