View
19
Download
2
Category
Preview:
Citation preview
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 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 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 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)
Recommended