1

Structuration et choix d’équipements des lignes de production : approches

mono et multicritère

Structuration et choix d’équipements des lignes de production : approches

mono et multicritère

Lina MAKDESSIAN

Co-directeurs : Alexandre DOLGUI et Farouk YALAOUI

Institut des Sciences et de Technologies de l’information de Troyes (ISTIT)

Équipe OSI - Université de Technologie de Troyes (UTT)

2

Plan de la présentation

Plan de la présentation

Introduction générale

Partie I : Équilibrage de la ligne de production

et choix d’équipements – Analyse Monocritère

Partie II : Équilibrage de la ligne de

production et choix d’équipements – Analyse

Multicritères

Conclusions et perspectives

3

Lignes de production Lignes de production

Caractéristiques

1- Temps opératoire

2- Temps de cycle

3- Équipements et main d’oeuvreTypes :

• Lignes d’usinage

• Lignes d’assemblage

Introduction générale (1)

Introduction générale (1)

4

Conception des lignes de

production Conception des lignes de

production

Nouveau produits Nouveau système de production

Concevoir

Opérations, compatibilité,

relations de précédence,…

Stations de travail, machines,

ressources,…

Introduction générale (2)

Introduction générale (2)

5

Équilibrage de lignes d’assemblage

Équilibrage de lignes d’assemblage

Première formulation : Salveson 1955

État de l’art : Baybars1986 ; Gosh et

Gagnon 1989 ; Scholl 1999

Classification des problèmes ALB : Erel et

Sarin, 1998 (Produits, temps opératoire)

Introduction générale

Introduction générale

6

ProblématiqueProblématique

Les Données :

Le produit à fabriquer

La cadence objectif de la ligne

Les équipements disponibles

L’objectif :

Partitionner les opérations en stations

Choisir les équipements adéquats

Introduction générale (3)

Introduction générale (3)

7

Spécificités des liges étudiéesSpécificités des liges étudiées

Stations en séquence

Plusieurs équipements travaillant en parallèle

Les opérations du même équipement s’exécutent simultanément

Bloc d’opérations

Introduction générale (4)

Introduction générale (4)

8

Calcul des tempsCalcul des temps

Temps d’une station = temps maximal de ses équipements (un de ses Blocs)

Temps d’un équipement = temps maximal de ses opérations

Temps de fonctionnement de l’outil demandant le plus de temps

Introduction générale (5)

Introduction générale (5)

9

Plan de la présentation

Plan de la présentation

Structuration une ligne de production et choix d’équipement

Analyse MulticritèreAnalyse Monocritère

Méthodes approchéesMéthode exacte

10

Partie IPartie I

La ligne de production étudiée

Travaux antérieurs

Méthodes de résolution

Exemple d’application

Résultats des tests

11

Ligne d’usinageLigne d’usinage

Tête d’usinage

Mécanisme de transfert

Un outil

Une pièce

Station de chargeme

nt

Station de travail

Station de déchargement

12

Données et contraintesDonnées et contraintes

Un produit = graphe de précédence G (N, E)

Plusieurs types d’équipements avec leurs

coûts (investissement) et les temps

opératoires

Les contraintes :

Incompatibilité équipement – équipement

Incompatibilité équipement – opération

Incompatibilité opération – opération

13

Travaux antérieursTravaux

antérieursChoix d’équipements

Bukchin et Tzur (2000)

Bukchin et Rubinovitz (2003)

Graves et Redfield (1988)

Structuration des lignes avec des blocs

séquentiels

Dolgui et al. 1999, 2000, 2001, 2002a

Bratcu et al. 2002, 2003, Dolgui et al., 2002b

Finel 2004.

14

Méthodes proposéesMéthodes proposées

Méthode exacte : PSE

Méthodes approchées Heuristique : H.A.B Algorithme génétique AG

15

Méthode exacte (1)Méthode exacte (1)

Méthode exacte : PSERacine

(1)

Assignation Operation candidate-type d’équipement

(2) Choix d’un noeud à

Min BI(3) Une seule opération à la fois

(4) Noeud dominé

(5)SOLUTION

16

Méthode exacte (2)Méthode exacte (2)

Borne inférieure :Relaxation des contraintes d’incompatibilité :•opération-opération•équipement-équipement

Règle de dominance :β1 =β2 et C(S1)>C(S2)

β1<β2 et C(S1)=C(S2)

Le coût de la solution S2

Le cardinal des opérations

assignées à S2

17

Méthode approchée (H.A.B)

Méthode approchée (H.A.B)

Heuristique basée sur l’énumération H.A.B

Racine

Assignements des operations

SOLUTION Réalisable

(2) Le choix aléatoire d’un nœud

(1) Le choix du nœud le moins cher

18

Algorithme génétique (1)

Algorithme génétique (1)

Individu 1

Individu 2

.

.

.IndividuNbpop

Gène 1 Gène 2 ... … Gène N

Coût1

Coût 2

.

.

.

Coût Nbpop

Gène = Le numéro de station L’opération L’équipement

Population Initiale : COMSOAL

19

Algorithme génétique (2)

Algorithme génétique (2)

La sélection : (Goldberg 1999, Prins 2004) Tournoi binaire

Le croisement : OX, LOX

La réparation : station par station

La mutation :

Probabilité faible, par une recherche locale ou recuit simulé

20

Algorithme génétique (3)Algorithme

génétique (3)L’insertion : (Prins, 2004)

Les conditions d’arrêt : un nombre donné d’itérations

un nombre donné d’échecs

un temps d’exécution donné.

Les paramètres :taille de la population =100

taux de mutation < 0.01

nombre d’itérations = 20000

nombre d’échecs = 5000

temps de calcul = 30 minutes

21

Exemple (contraintes)

Exemple (contraintes)

12

4

98

7

6

5

E1 E2 E3

1000 555.556

555.556

1 47 40 47

2 * 25 29

3 41 * *

4 47 * 44

5 25 * *

6 9 2 *

7 33 * *

8 7 1 4

9 42 * 36

10

7 7 *

Les équipements 2 et 3 ne sont pas compatibles : 60% Le temps de cycle est de 50 unités de temps

3

10

22

Exemple (solution)Exemple (solution)

Bloc 1E2

(1,10)

Station 1Station 1

Ts=40

Bloc1E1

(4,5,6,7)

Bloc 2E3(2)

Station 2Station 2

Ts=47

Station 3Station 3

Bloc 1E1

(3,8)

Ts=41

Station 4Station 4

Bloc 1E3(9)

Ts=36

Le coût total est de 3667 unitésLa solution optimale a été obtenue en 2,072 sec.

23

Tests numériques Tests numériques

Nombre d’opérations : 7, 10, 15, 50, 100, 150 et 200

Nombre d’équipements : 3, 5 , 10, 15, 20 et 30

Temps de cycle : 50 unités de temps

Le coût d’équipement : le plus performant Cmax est le

plus cher :

Compatibilité:Compatibilité: 60% et 80%

j),C,Cn

n(MaxC maxmax

max

jj

2

1

24

Résultats des tests (1)Résultats des tests (1)

PSE : Le nombre de problèmes non résolus devient

de plus en plus important en fonction de la taille

Nous n’avons pas pu améliorer la qualité de PSE

avec une solution initiale

L’influence du faible % de compatibilité sur le

nombre des nœuds générés est important

Des nouvelles bornes et des nouvelles

propriétés de dominance à chercher

25

Résultats des tests (2)

Résultats des tests (2)

Heuristique de branchement : Pour moins de 50

opérations, les résultats sont satisfaisants

Trouver d’autres heuristiques

Algorithme génétique : La qualité des solutions

trouvées est très satisfaisante. Plusieurs cas où

l’optimum est atteint ou, en moyen, à moins de 3,7%

de l’optimum

Améliorations possibles sur l’AG

26

Plan de la présentation

Plan de la présentation

Équilibrage d’une ligne de production et choix d’équipement

(EL-CE)

Analyse MulticritèreAnalyse Monocritère

Choix d’équipements (CE)

EL-CE

Quatre critèresBi-critèrs

NSGA-IIMultistart

27

Analyse MulticritèreAnalyse Multicritère

Plusieurs critères: une solution est de

combiner les critères en un seul

(=>optimisation scalaire)

Mais : Les critères sont de natures différentes

Alors : Généraliser les algorithmes existants

d’optimisation scalaire au cas vectoriel

28

Optimisation vectorielle

Optimisation vectorielle

Comparaison de 2 solutions

➩X2>X1 Ci(X2) ≤ Ci(X1), i

j : Cj(X2) < Cj(X1) «X1 solution dominée»

➩X2X1 Ci(X2) = Ci(X1) i

► L’ensemble des solutions non dominées est

l’ensemble des solutions Pareto optimales

29

Front de ParetoFront de Pareto

f1

f2

Définition graphique du front de Pareto

30

Choix d’équipementsChoix d’équipements

Les données :

Le nombre de stations de travail

Plusieurs équipements sont disponibles

Les opérations sont déjà assignées aux stations

L’objectif :

Choisir et placer dans chaque station le meilleur équipement possible

Ce choix peut demander de prendre en compte deux ou plusieurs critères en même temps (problème multicritère)

31

Problème bi-critère Problème bi-critère

)()(1 xCmxEc(x) Min C ij

1. Le coût d’achat de l’équipement i rapporté à l’année de référence, Eci

2. Le coût annuel de main d’œuvre de l’opérateur j qui travaille sur l’équipement i, Cmi

3. La productivité annuelle de la ligne à maximiser

Max C2(x) = ProdL=Min {Prodi}; iL

► C (x) = {C1 (x), C2 (x)}

32

L’ensemble des solutions

L’ensemble des solutions

.

.

.

.

.

.

.

.

.

...

...

...

.

.

.

11 21 31 m1

12 22 32 m2

1x1 2x2 mxn 3x3

Graphe des solutions possibles, Sysoev et Dolgui 1998

33

Méthodes proposéesMéthodes proposées

Multistart

NSGA-II (Non dominated

Sorting Genetic Algorithm – 2)

34

Solution initialeSolution initiale

1. Un rang k (k ∈ m ) → Un nœud i ∈ k 

(choix avec une probabilité)

2. Compléter aléatoirement en suivant

des arcs

toutes les solutions sont faisables

chaque solution a une clé pour la

différencier des autres

35

Optimisation locale Optimisation locale

36

NSGA-II NSGA-II

(Deb,1999), (Deb et al., 2002) et (Lacomme et al., 2003)

NSGA-II AG (classique)Codage Codage

Population initiale Population initialeReproduction génétique Reproduction

génétiqueTrier la population en

frontsÉvaluer le fitness

Calculer la marges entre les critères

Non

37

Tri non dominéTri non dominé

Deb (1999), Lacomme et al. (2003)

Fronts

f1

f2

front3

front2

front1

38

Distance d’encombrement (marge)

Distance d’encombrement (marge)

f2

X(i-1)

X(i)

X(i+1)

X(1)

f1

X(nr)

f1max

f2min

f1min

f2max

Les marges

39

Calcul des margesCalcul des marges

Pour 2 critères :

1. Trier le front selon la valeur de f1

2. Marge (1) = Marge (nr) = ∞

3. Marge (i)= ((f1 (i+1)-f1 (i) )/ (f1max –f1min)) +

((f2 (i-1)-f2 (i+1)) / (f2max –f2min))

40

Production génétiqueProduction génétique

Sélection des parents (Tournoi binaire)X1, X2

Si Rang(X1) < Rang(X2) P1 X1

Si Rang (X1) = Rang (X2) alors si Marge (X1) > Marge (x2) P1 X1

Renouveler la population

41

Algorithme NSGA-II Algorithme NSGA-II

Initialisation 

RépéterProduction génétique;Tri non dominé ;Calculer la distance d’encombrement ;Renouveler avec une sélection la population ;

Jusqu’à une condition d’arrêt

Phase de la préparation

La boucle coeur

42

Tests numériques Tests numériques

Deux densités de compatibilité :

20% et 100%

Coût d’investissement annuel ∈ [3000, 6000]

Productivité annuelle ∈ [8000, 11500]

7 problèmes de tailles différentes :

{(n, m): (5, 3), (5, 5), (10, 5), (8, 8), (8, 12),

(10, 5), (10,15)}

43

ComparaisonsComparaisons

0

5

10

15

20

25

30

35

40

1er cas 2e cas 3e cas 4e cas 5e cas

1er cas2e cas3e cas4e cas5e cas

GapC<0 et Gap P>=0

GapC>0 et GapP>0

GapC>0, GapP<0

GapC=GapP=0

GapC<0, GapP<0

%

Gaps entre NSGA-II et MS

44

Améliorations de NSGA-II

Améliorations de NSGA-II

NSGA-II hybridé par une Recherche Locale (RL) A : NSGA-II sans RL et NSGA-II avec RL B : NSGA-II sans RL et NSGA-II avec RL sans mutation C : NSGA-II sans RL et NSGA avec RL remplaçant la mutation

Répéter

Production génétique ;

Tri non dominé ;

Assigner la distance plaine ;

Renouveler avec une sélection la population initiale ;

Jusqu’à une condition d’arrêt

Sans ou avec la mutation

45

ComparaisonsComparaisons

0

10

20

30

40

50

60

70

80

1er cas 2e cas 3e cas 4e cas 5e cas

ABC

%

Gaps entre 3 NSGA-II Hybridés par une RL

GapC<0 et GapP>=0

GapC>0 et GapP>0

GapC>0, GapP<0

GapC=GapP

=0

GapC<0, GapP<0

46

Quatre critèresQuatre critères

Min C1 (x),

Max C2 (x)

Min C3(x) =

Min C4(x) = ΔNcL

C(x)= {C1(x), C2(x), C3(x), C4(x)}

NSGA-II est meilleur que Multistart

m

iiSF

1

47

Quelques remarquesQuelques

remarques

Les deux méthodes sont des métaheuristiques

Obtention rapide des solutions

Indépendantes du type de critère à

optimiser

À chaque itération, il y a des solutions

L’utilisateur peut intervenir

Inconvénient : convergence vers l’ensemble

des solution Pareto optimale en probabilité

48

Plan de la présentation

Plan de la présentation

Équilibrage d’une ligne de production et choix d’équipement

(EL-CE)

Analyse MulticritèreAnalyse Monocritère

Choix d’équipements (CE)

EL-CE

Quatre critèresBi-critèrs

NSGA-IIMultistart

NSGA-II

49

Critères et méthode de résolution

Critères et méthode de résolution

Les critères :

C(x)= {C1(x), C2(x), C3(x), C4(x)}

Méthode de résolution : NSGA-II

AG (Partie I) : codage, population,

croisement et réparation

50

Résultats de testsRésultats de tests

0

10

20

30

40

50

60

70

80

+RL> +RL=

CoûtProductivitéSurfacePolyvalance

Gap entre NSGA-II avec RL et sans RL

%

51

Conclusions générales

Conclusions générales

développer et tester un ensemble des méthodes pour structurer une ligne de production

la ligne est conçue pour la fabrication de masse mais peut être étendu à autres lignes

l’affectation des opérations aux postes et le choix un ensemble des équipements

52

PerspectivesPerspectives

Monocritère : exacte et approchéeAméliorer le PSEProposer de nouvelles heuristiquesAméliorer l’AG

Multicritères : grand choix pour le/les décideur(s)Expérimenter des différentes tailles, autres contraintesDévelopper un outil informatique avec une interface conviviale

53

PublicationsPublications

2 Revues Makdessian L., Dolgui A., Yalaoui F., “Minimisation du coût des lignes de transfert”, Journal Européen des Systèmes Automatises JESA, 2005 (en révision), 25 pages. Makdessian L., Dolgui A., Yalaoui F., “Optimisation de la conception des lignes de production – analyse mono et multicritère”(sélectionné pour un numéro spécial de JDS (Journal of Decision Systems)

5 Conférences.