Alexandre Dolgui 1

Optimisation des machines etdes lignes d’usinage

Alexandre Dolgui Ecole des Mines de Saint Etienne, France

Nikolay Guschinsky, Genrikh LevinAcadémie des Sciences de Biélorussie

Projet INTAS 00-217

Alexandre Dolgui 2

Plan

Descrition du problème

Modèle des contraintes

Approches possibles pour l’optimisation

Aproche de la théorie de graphes

Conclusions

Alexandre Dolgui 3

Situation du problème

• Conception préliminaire (structuration)

Nouveau produit Nouveau système deproductionConception du

système deproduction (ousa resturaction)

- postes de travail- équipements

- outils ...

un ensembled'opérations,contraintes

technologiques

Alexandre Dolgui 4

Machines d’usinage

Alexandre Dolgui 5

Têtes d’usinage

Alexandre Dolgui 6

Têtes d’usinage

sj=220 si=150 tête d’usinage Opération i Opération j li=45 lj=60

Alexandre Dolgui 7

Station de travail (machine d’usinage)

Plusieurs têtes d’usinage sur la même stationLes têtes sont actionnées simultanément

Part

tête 1

tête 2

tête 3

Machine

Alexandre Dolgui 8

Lignes de transfert

Alexandre Dolgui 9

Lignes de transfert

Tête d’usinage . . . . . .

Chargement Station Dechargement

Production de masse, lignes automatisées, usinage mécanique

Alexandre Dolgui 10

Décisions de la conception

Simultanement:

Choix des têtes d’usinage (partitionner l’ensembled’opérations en blocs)

Regrouper les têtes par station (conception des stations)

L’objectif est de minimiser le coût de la ligne (machine)tout en assurant une productivité voulue

Alexandre Dolgui 11

Optimization

Line: stations and their spindles

Database of technologies

New product

Decision making person

Decision constraints

CAD

Past decisionfor designed lines

competences

Decision

Possible spindlesand compatibility

constraints

Optimal solutionfor given decision

constraints

Operations and technological constraints

Algorithme de la conception

Alexandre Dolgui 12

a

hd

c jb

g

f

ie k l

M1 M2 M3

20 6 5

21 15

5

46 16

8

35

15

10

676866

Simple Assembly Line Balancing Problem

Alexandre Dolgui 13

Méthodes pour le SALBP

Méthodes

Exactes Heuristiques

Programmation dynamique

Branch-and-Bound

FABLE(Johnson 1988)

EUREKA(Hoffmann 1992)

COMSOAL(Arcus 1966)

RPW(Kilbridge et Wester 1961)

Alexandre Dolgui 14

Les données du problème

- L’ensemble N de toutes les opérations à réaliser pour un produit

- L’ensemble B de toutes les têtes d’usinage possibles

- Les contraintes de precedence sur l’ensemble d’opérations

- Les contraintes obligeant de mettre certaines opérations ensemble sur

la même station

- Les contraintes interdisant de mettre certaines têtes d’usinage

ensemble sur la même station

- Le coût de chaque tête d’usinage possible et les opérations qu’elle

peur réaliser (outils)

- Le coût relatif d’une station

Alexandre Dolgui 15

Fonction objectif

Minimiser le coût

Sous les contraintes suivantes :

contrantes de precedence

de compatibilité des opérations

de compatibilité des têtes d’usinage

.

Alexandre Dolgui 16

a

hd

c jb

g

f

ie k l

M1 M2 M3

20 6 5

21 15

5

46 16

8

35

15

10

463521

35

21 6

46

15

Equilibrage des lignes de transfert (TLBP)

Alexandre Dolgui 17

Nouveau problème de line balancing différent de SALBP, car :

• Chaque opération peut être présente dans plusieurs blocs de B (plusieurs

têtes d’usinage peuvent la faire) et on ne sais pas en avance lequel est

meilleur ;

• Dans l’ensemble B il y a des blocs qui sont en conflit ;

• Les opérations appartenant au même bloc et à la même station sont

exécutées simultanément ;

• Le coût de la ligne ne dépend pas uniquement du nombre de stations

mais aussi du nombre et du coût des têtes d’usinage (blocs) utilisées

Alexandre Dolgui 18

Ordre partiel

j

i<=ji avant j

Contraintes decompatibilité

graphe oriénté

k l p

les opérations k, l et p doiventêtre executées sur la même

station

i

une collection desensembles (graphes non

orientés)

Constraintes

Alexandre Dolgui 19

il faut mettre sur la mêmestation

op1 op2

impossible de mettre sur la mêmestation

op3

op4

Exemples des contraintes de compatibilité

Alexandre Dolgui 20

Méthodes pour le TLBP

Méthodes

Exactes Heuristiques

MIP Court cheminBasée sur COMSOAL Génétiques

Alexandre Dolgui 21

Approche de plus court chemin

Graphes de contraintes Graphe de décisions

Alexandre Dolgui 22

Un sommet du nouveau graphe

sommet U Uk

r

n

jrjk

r

Nv1 1= =

= représente l’état de la pièce fabriquée

après son usinage par toutes les têtes d’usinage de la station k.

Alexandre Dolgui 23

Un exemple

1

2

5

Block number 1 2 3 4 5 6 7 8 Block operations 1 4,5 4 5 1,4 2 3 1,2 Block cost 210 224 211 212 221 211 210 223

m0=3, n0=4, C1=380, D s={(3,5)}, and sD ={(1,7), (5,7), (8,7)}

Alexandre Dolgui 24

Un exemple

1

2

4

1,4

1,2

4,2

1,2,3,5

1,2,4 1,2,3,4,5∅

590601

801

591

591

603

801

812814

1012

802

591

601

802590

591

603801

591590

591

591

812814

1013

590

802

591

Alexandre Dolgui 25

Un exemple

(603, ∞, ∞)

1,2

603 814

∅ 1,2,3,4,5 (∞,1417, ∞)

812 802 1,2,4 (812, ∞, ∞)

Alexandre Dolgui 26

Résultats de tests

p(Gr)=0.1, p( sG )=0.05 |N|=25, |B|<=75

|N|=50, |B|<=150

|N|=75, * |B|<=225

|N|=100, ** |B|<=300

Minimal number of blocks 65 138 211 270 Maximal number of blocks 73 148 222 288 Average number of blocks 69 144 216 280 Minimal number of V 37 352 1970 4323 Maximal number of V 1421 5635 19492 87010 Average number of V 388 2027 10232 34522 Minimal number of D 81 1342 12681 13458 Maximal number of D 12743 48744 264827 634821 Average number of D 2544 14464 125713 196990 Minimal running time 0.02” 0.25” 3.7” 9.1” Maximal running time 2.1” 11.8” 101.7” 899.6” Average running time 0.36” 3.2” 41.0” 214.9”

Alexandre Dolgui 27

Résultats de tests

p(Gr)=0.15, p( sG )=0.05 |N|=25, |B|<=75

|N|=50, |B|<=150

|N|=75, |B|<=225

|N|=100, |B|<=300

Minimal number of blocks 62 133 210 237 Maximal number of blocks 73 148 220 279 Average number of blocks 69 142 215 269 Minimal number of V 48 438 489 1471 Maximal number of V 1341 1479 7811 7800 Average number of V 268 758 2997 3769 Minimal number of D 97 1526 1399 3428 Maximal number of D 7957 8162 88983 37222 Average number of D 1324 3830 25164 13481 Minimal running time 0.02” 0.4” 0.6” 2.0” Maximal running time 1.0” 1.5” 26.5” 35.8” Average running time 0.16” 0.8” 7.6” 13.2”

Alexandre Dolgui 28

Conclusions

Nous avons mis en évidence un nouveau problèmed’équilibrage des lignes de production.

Nous avons proposé une nouvelle méthode qui se base sur la recherche de chemin plus court dans un graph spécialement construit à partir des contraintes duproblème.

Les solutions obtenues sont optimale et le temps de calcul est acceptable.

Plus nous avons des contraintes mieux c’est (la taille du graphe diminue)