Optimisation du coûtdes lignes de transfert reconfigurables

– approche par programmation linéaire –

Antoneta Iuliana BRATCU

– stagiaire post-doc sous la direction d’Alexandre DOLGUI –

Présentation G2I / 26.05.2005 – 1 / 15

Sommaire

Positionnement du sujet

Description du problème – notations

Agrégation des contraintes. Formulation comme programme linéaire

Pré-traitement : réduction du modèle, bornes

Discussion sur un exemple

Conclusion et perspectives

Présentation G2I / 26.05.2005 – 2 / 15

Positionnement du sujet

tête d’outil multifonctionnel : bloc – exécution parallèle des opérations

Lignes de transfert…

… reconfigurables :

utilisées dans l’usinage (production de masse)

grande productivité

investissements importants

l’optimisation initiale est justifiée

… mais la ligne manque de flexibilité

exécution sérielle des blocs dans chaque station

plusieurs stations en série

concevoir dès début la ligne de sorte à minimiser son coût pour toute une famille de produits

Présentation G2I / 26.05.2005 – 3 / 15

Description du problème – notations

Présentation G2I / 26.05.2005 – 4 / 15

La ligne doit usiner :

Ni – opérations

Gi – graphe de précédence

Tci – temps de cycle

p produits – pour chaque i=1,2…p

avec un ensemble de blocs (têtes d’outils) connu :

B – pour chaque r=1,2…| B |Cbr – coût

tbr – temps opératoire

en sachant en plus :

Cs0 – coût (fixe) d’une nouvelle station

m0 – nombre maximal de stations

n0 – nombre maximal de blocs par station

sous les contraintes…

… de précédence – Dori

… de temps

… d’exclusion – Dbs

… d’inclusion – osiD

Combien de stations, y

et quelle affectation des blocs aux stations, xrk =

sinon,0station la à assignéest bloc le si ,1 kr

faut-il avoir afin de minimiser le coût total de la ligne : Cs0·y +

B

1 1

0

r

m

krCb ·xrk ?

Agrégation des contraintes

agrégation des contraintes de précédence

– superposition des p graphes de précédence individuels, Gi graphe G’

– puisqu’il peut y avoir des précédences contraires dans les différents G i, G’ peut contenir des circuits,

– … et les nœuds de chaque tel circuit sont agglutinés pour former une seule macro-opération G orienté acyclique

agrégation des contraintes d’inclusion

agrégation des contraintes d’exclusion

– chaque élément de chaque qui contient seulement des parties d’une macro-opération est étendu avec les opérations manquantes

osiD

– les ensembles ayant des intersections non vides sont réunisosiD

– les blocs qui ne peuvent exécuter que des parties de macro-opérations sont éliminés,…

– … donc les éléments de Dbs qui les contiennent seront aussi éliminés

Présentation G2I / 26.05.2005 – 5 / 15

– … alors le sens stricte de la notion de précédence doit être relâché

p

ii

1 NN

p

i

osiDDos

1

Dbs

Formulation comme programme linéaire.

Présentation G2I / 26.05.2005 – 6 / 15

m* – une borne inférieure du nombre de stations

– pour chaque bloc r, l’intervalle K(r) = [head(r), tail(r)], head(r) est la station la plus tôt tail(r) est la station la plus tard où le bloc r peut être assigné

La famille Fs = {F1,…Fv} de paires de blocs ayant des opérations communes Fs est un sous-ensemble de blocs alternatifs

(seulement un bloc de chaque paire de Fs peut être utilisé dans une décision)

vqqF

,...2,1F0 = B\ – l’ensemble de blocs qui sûrement apparaissent dans une décision

DtDos

bloc Br wrt=|BrDt|

Wt = {BrB | wrt>0}

Ut = {BrB | itBr},

avec it une opération fixée

de l’ensemble DtDos

– pour chaque bloc rM(r) – les opérations prédécesseurs des opérations de Br,

qui n’appartiennent pas à Br

H(r) = {BtB | BtM(r)≠}

H={BrB | M(r)}

Paramètres additionnels

BtH(r)

Br H

htr=|BtM(r)|

R* – une borne supérieure de l’ensemble des blocs à affecter à la dernière station

bornes

Présentation G2I / 26.05.2005 – 7 / 15

Formulation comme programme linéaire

Minimiser Cs0·y +

R

1 1

0

r

m

krCb ·xrk sous les contraintes :

0)(

F ,1

rxrKk

rk

vqxqFr rKk

rk ,...2,1 ,1)(

NNR

r rKk

rkr xB)(

||

)( , ,)()( ),(

rKkrxrMxh rkrHt kstKs

tstr

H

ttt Us

tUs

sktWr

rkrt sKkDosDxDxw

)( , ,

tt Ds

ttDr

rk sKkDbsDDx

)( , ,1

00)}(|{

,...2,1 , mknxtKktr

rk R

*)}(|{

,,...2,1 , mkpiTcxt itKktrrkr

R

y kxrk, rR*, kK(r),

km*

exécution de chaque opération de l’ensemble agrégé, N,dans une seule station,

aussi bien par des blocs qui n’ont pas d’intersections (de F0), que par les autres blocs (de Fs)

exécution de toutes les opérations de N

respect des contraintes de précédence agrégées (décrites par le graphe de précédence « total », G)

respect des contraintes d’inclusion agrégées, Dos

respect des contraintes d’exclusion agrégées, Dbs

contrainte du nombre maximal de blocs par station

contrainte sur le nombre de stations

respect des temps de cycle de tous les produits

Présentation G2I / 26.05.2005 – 8 / 15

Pré-traitement : réduction du modèle

… portant sur l’ensemble de blocs, après l’agrégation des contraintes et l’élimination des blocs ne pouvant exécuter que des parties de macro-opérations

1. Identifier les « circuits » de blocs a).

i j Bx

u v Bw

q s Bz

k l By

i Br j

k l Bt

a) b)

« Briser » chaque tel circuit en éliminant le plus coûteux bloc de par son coût par opération.

2. En particulier, si 2 blocs forment une « boucle » b), alors ils seront traités comme des blocs alternatifs.

3. Éliminer tout bloc pour lequel il n’existe pas un sous-ensemble de blocs B’, tel que :

– les opérations de B’ donnent l’ensemble total, N,– |B’| m0n0,

– tous les blocs de B’ sont mutuellement disjoints.

Présentation G2I / 26.05.2005 – 9 / 15

Pré-traitement : calcul des bornes

algorithme A

décrit dans un travail antérieur

graphe de précédence agrégé, G

contraintes d’inclusion agrégées, Dos

matrice des distances

sinon,0excluents' qui blocs despar faites être seulement peuvent opérations les si ,2

d(i,j) =

q–(i), i=1,2,…|N|

algorithme A

graphe inversé, Ginv

Dos

matrice dq+(i), i=1,2,…|N|

c) k+/–(i) = [q+/–(i)/n0], i=1,2,…|N|

Calcul de m*

Calcul de K(r), pour chaque bloc r.

Calcul de R*.

a)

b)

head(r) = max{k–(i) | i Br}

tail(r) = min{k+(i) | i Br}

d)

b) Notons par head_min le minimum des heads des blocs ayant le tail égal à tail_max.

a) tail_max max{tail(r)| Br B}.

c) R* est formé des blocs qui ont le tail strictement supérieur à head_min.

: m* = max{k–(i)| i N}

Un exemple de petite taille – données d’entrée

Présentation G2I / 26.05.2005 – 10 / 15

N1={1,2,3,4,5,6,7,8,9,10}, |N1|=10

N2={1,2,3,4,5,6,7,8,9,10,11,12}, |N2|=12

N3={1,2,5,7,8,9,10,11,12,13}, |N3|=10

13,12,11,10,9,8,7,6,5,4,3,2,11

p

iiNN |N|=13

p = 3 produits

1

6

3

2

7

8

4

9 10

5

G1

1

6

3

4

2

8

9

5 10

11

G2

7

12 1

13

5

12

8

2

9

10

11

G3

7

contraintes de précédence

osos DD

osD

1211

10,9 ,8,71

osos DD

osD

2221

12,10,9 ,8,72

osos DD

osD

3231

10,9 ,8,73 13,3ossD

contraintes d’inclusion

Présentation G2I / 26.05.2005 – 11 / 15

Un exemple de petite taille – données d’entréeBloc

rOpérations Temps opératoire,

tbr [u.t.]Coût,

Cbr [u.m.]B1 {1,3,6,13} 9 250

B2 {1,3,13} 8 170

B3 {1,2,7,8} 6 281

B4 {2,5,9} 10 150

B5 {2,5,7,8,11} 9 275

B6 {2,6,9,10} 11 230

B7 {4,6,8,10} 13 211

B8 {4,7,8} 9 160

B9 {4,7,8,9} 10 215

B10 {5,12,13} 6 158

B11 {10,11,12,13} 12 230

B12 {2,5,10,11,12} 11 260

les blocs

contraintes d’exclusion

bsbsbs DDD

bs BBBBBBBD

321

11591761 , ,, ,,, les temps de cycle : Tc1=23 u.t. Tc2=25 u.t. Tc3=21 u.t.

Un exemple de petite taille – pré-traitement

Présentation G2I / 26.05.2005 – 12 / 15

1

6

9

4 3

8

7

a = {2,5}

b = {10,11,12}

G

13

2 macro-opérations

le graphe de précédence agrégé

Blocr

Opérations tbr [u.t.] Cbr

[u.m.]B1 {1,3,6,13} 9 250

B2 {1,3,13} 8 170

B3 {1,2,7,8} 6 281

B4 {2,5,9} 10 150

B5 {2,5,7,8,11} 9 275

B6 {2,6,9,10} 11 230

B7 {4,6,8,10} 13 211

B8 {4,7,8} 9 160

B9 {4,7,8,9} 10 215

B10 {5,12,13} 6 158

B11 {10,11,12,13} 12 230

B12 {2,5,10,11,12} 11 260

a

b

a b

6 B1

1 3 13 B2

9 B9

4 7 8 B8

a 9 B4

a b B12

13 b B11

… l’ensemble de blocs

… « circuits » de blocs

ptosptosptos DDD

ptos bD

321

,9 ,8,7 ,13,3

… les contraintes d’inclusion

… les contraintes d’exclusion

ptbsD

ptbs BBD

1

91,

Présentation G2I / 26.05.2005 – 13 / 15

Un exemple de petite taille – bornes…Bloc head tail m* R*

B1 1 4

2 {1,2,3,4,5,6}B2 1 5B4 2 5B8 2 5B9 2 5B12 2 5

… optimisation Fs={{B1,B2}, {B4,B12}, {B4,B9}, {B8,B9}} F0=

R={1, 2, 4, 8, 9, 12} |Dospt|=nic=3 H={B4, B8, B9, B12}

t

wrt, r R, t=1,2,…nic=3 M(r) H(r) htr, r R, t RW1={B1,B2} W2={B8,B9} W3={B4,B12} B1 B2 B4 B8 B9 B12

B1 2 0 0 0 0 0 0 0 0

B2 2 0 0 0 0 0 0 0 0

B4 0 0 1 {4,7,8} {B8,B9} 0 0 0 3 3 0

B8 0 2 0 {3,6,13} {B1,B2} 3 2 0 0 0 0

B9 0 2 0 {3,6,13} {B1,B2} 3 2 0 0 0 0

B12 0 0 1 {4} {B8,B9} 0 0 0 1 1 0

rt

2 2

Station 1ts =9, Cs =600

B1 {1, 13, 3, 6 }

tb1=9 Cb1=250

B9 {4, 7, 8, 9 }

tb9=10 Cb9=215

B12 {b, a}

tb12=11 Cb12=260

2 2

Station 2ts =21, Cs =825

solution

optimale

Présentation G2I / 26.05.2005 – 14 / 15

Conclusions… lignes de transfert : investissement initial important

– optimisation dans la phase initiale de conception justifiée…

– … encore plus dans le cas d’une famille de produits, assurant la reconfigurabilité à moindres frais

conception des lignes de transfert reconfigurables : agrégation des contraintes

… à faire amélioration des bornes

tests numériques plus amples

couplage avec des heuristiques

… perspectives reformuler le problème en tenant compte des coûts de fonctionnement

Merci de votre attention !

Présentation G2I / 26.05.2005 – 15 / 15