Nicolas Ferrary Résolution dun problème dagencement déquipements par Programmation Par Contraintes 1 Résolution dun problème dagencement déquipements dateliers

Résolution d’un problème d’agencement d’équipements par Programmation Par Contraintes 1

Nicolas Ferrary

Résolution d’un problème d’agencement d’équipements

d’ateliers de montage automobile par

Programmation Par Contraintes

Nicolas Ferrary, Mémoire DEA Sous la direction de

Dominique Feillet et Philippe Michelon


Nicolas Ferrary

Plan

• Contexte industriel• Etat de l’art• Problème et modélisation• Résolution• Résultats• Conclusion et perspectives


Nicolas FerraryContexte industriel

Fabrication d'un véhicule • Placement les éléments de la chaîne de

montage et les magasins dans l’atelier de montage

• 4 étapes : emboutissage, tôlerie, peinture, assemblage

• Processus de montage– Graphe de montage

moteur 1

moteur 3

sellerie 2 sellerie 4

Sous caisse

mécanique 3sellerie 6mécanique 1

poste de conduite

mécanique 4sellerie 8

porte


Nicolas FerraryContexte industriel

Description de l’atelier • La caisse se déplace dans l’atelier grâce à un

convoyeur sur la chaîne principale

• Il possède une entrée et une sortie

• Nous allons trouver l’ensemble des tronçons présents dans le graphe de montage dans l’atelier

• Manutention dans l’atelier :– Des magasins alimentent en pièces les tronçons avec une

flotte de véhicules de manutention sur un réseau d’allées– L’approvisionnement se fait à partir d’un graphe de

manutention


Nicolas Ferrary

Le problème Atelier

Bx

ByEntrée

Sortie

1

5

2 3

7 4

6

2

3

1


Nicolas Ferrary

Etat de l'art

• Problématique générale de l’agencement d’équipements (facility layout) :

Positionner des zones dans un espace défini de manière à minimiser les flux, les encombrements, …

Exemple : agencement d’aéroports, d’hôpitaux, …

• Evaluation d'un agencement, 2 points de vue de modélisation: – « relationship chart » Max z = Σ Σ rijxij

rij : score d'adjacence entre la zone i et la zone j

xij : binaire 1 si i et j adjacents 0 sinon

– « from-to chart » Min z = Σ Σ fijcijdij fij : flux entre la zone i et j ; dij : distance entre i et j

cij : coût en unité de flux et de distance entre i et j


Nicolas Ferrary

Etat de l'art

• Représentation graphique – Discrète (ensemble des positions déterminé par une

grille)– Continue (infinité de solution)

• Optimisation d’un agencement :– Représentation topologique– Représentation par graphe d’adjacence– Représentation par arbres de découpes– Problème d’affectation quadratique – Programmation Linéaire en Nombres Entiers (PLNE)


Nicolas FerraryEtat de l'artSynthèse

• Beaucoup de travaux dans la littérature

• Pas de travaux avec de la Programmation par Contraintes

• Travaux présentés sont :– soit très génériques ne prennent pas en compte

certains aspects de notre problème– soit très spécifiques ils sont difficiles à réutiliser dans

d'autres contextes que celui spécifié


Nicolas Ferrary

Définition du problème

• Positionner les zones (tronçons et magasins) de manière à minimiser les coûts (investissement et fonctionnement) en :– suivant le graphe de montage et de manutention– gérant l’entrée et la sortie de la chaîne sur l’atelier– créant un réseau d’allées pour l’approvisionnement– diminuant le nombres de coudes de la chaîne principale

• Tronçons : forme rectangulaire, une entrée et une sortie à l’opposée sur les largeurs et donc 4 orientations (, , ,)

• Magasins : carrés, pas d’entrées ni de sorties donc pas d’orientations


Nicolas Ferrary

Spécificités du modèle

• Modélisation avec la Programmation Par Contrainte• Evaluation : «from-to» chart• Représentation graphique discrète• Gestion du réseau d’allées avec un rajout d’une demi-allée pour chacune des zones

• Calcul des distances par la méthode Manhattan : permet de prendre en compte le réseau d’allées

surface représentant la zone


Nicolas Ferrary

Données du problème

• Bx, By : longueur et largeur de l’atelier

• xe,ye : abscisse et ordonnée de l’entrée de l’atelier

• xs,ys : abscisse et ordonnée de la sortie de l’atelier

• M : ensemble des magasins • T : ensemble des tronçons

• Li, li : longueur et largeur de chaque tronçon et magasin (Li=li)

• aij : les positions d'arrivées du tronçon i sur le tronçon j (entrée, centre ou sortie)

• fij : flux entre 2 zones

• cij : coût unitaire en unité de flux et de distance entre 2 zones


Nicolas Ferrary

Variables du modèle

• xi, yi : (≥ 0) : abscisse et ordonnée du centre de chaque zone

• hi, vi : {Li, li} : taille horizontale et verticale de la zone i

• eih, ei

v : {-1, 0, 1} : entrée du tronçon i en abscisse et ordonnée (-1 si inférieure au centre, 0 si égale et 1 si supérieur)

• Distances : en fonction des autres variables mais différentes en fonction du flux (production ou manutention)– Distance de manutention (centre magasin i et centre tronçon j)

dij = |xi - xj| + |yi - yj| – Distance de production

dij = |(xi - eihhi/2) - (xj - aijej

hhj/2)| +

|(yi - eivvi/2) - (yj - aijej

vvj/2)|


Nicolas Ferrary

Fonction objectif

• Manutention : flux Magasins - Tronçons • Production : flux Tronçons - Tronçons

– L : indice du dernier ronçon de la chaîne d montage

– dls = |(xl - elh.hl/2) -xs| + |(yl - el

v.vl/2) – ys|

Min z = Σ Σ fijcijdij + Σ Σ fijcijdij + flsclsdls iM jT iT jT


Nicolas Ferrary

Contraintes

• Positionnement dans l'atelier– hi/2 ≤ xi ≤ Bx-hi/2 et vi/2 ≤ yi ≤ By-vi/2 (i M T)

• Dimensions et orientation des tronçons– si la longueur est verticale alors largeur horizontale et vice et

versa :hi + vi = Li + li (i T)

– orientation verticale ou horizontale : eih=0 <=> ei

v!=0 (i T)

– entrée du coté de la largeur : eih!=0 hi=Li et ei

v!=0 vi=Li (i T)

• Non superposition des zones– si superposition horizontale alors non superposition verticale :

|xi-xj| < (hi+hj)/2 |yi-yj| ≥ (vi+vj)/2

– si superposition verticale alors non superposition horizontale


Nicolas Ferrary

Approches de résolution

• Modèle présenté testé est peu efficace en terme de pertinence des solutions et en temps d’exécution partage de la résolution du problème en 3 sous problèmes:– Placement de la chaîne principale

Car coûts très élevés pour un écart entre 2 tronçons par rapport au reste des autres coûts de production et manutention

– Placement des chaînes secondaires– Placement des magasins

Nous gardons l’ensemble des solutions optimales pour la chaîne principale, puis nous gardons les meilleurs couples chaîne principale-chaîne secondaires

Le placement des magasins se fait après avoir placer tous les tronçons car il peuvent alimenter des tronçons de la chaîne principale et aussi des chaînes secondaires


Nicolas Ferrary

Placement de la chaîne principale

• Ajout de contrainte pour diminuer le nombre de possibilités :– Borne sur l’écart entre 2 tronçons :

dij li/2 + lj/2+ i,j T (chaîne principale et successifs)dls (écart entre le dernier et la sortie de l’atelier)

avec l : indice du dernier tronçon et s : sortie de l’atelier

– Collage du premier tronçon à l’entrée de l’atelier– Si les tronçons i et j ont le même sens et sont successifs,

alors ils seront collés (dij = 0)

– Si les tronçons i et j sont perpendiculaires, alors la sortie de i aura soit la même abscisse soit la même ordonnée que la position d’arrivée (entrée, centre ou sortie) de i sur j

– Arrêt de la recherche si la solution courante a plus de coudes que la meilleure solution déjà trouvée


Nicolas Ferrary

Placement de la chaîne principale

• L’ordre des variables dans notre arbre suit l’ordre des tronçons dans la chaîne principale, avec pour chacun des tronçons les variables d’orientation en premier et abscisse et ordonnée ensuite

• On prouve la solution optimale avec une première recherche et on trouve toutes les solutions ayant ce résultat dans une deuxième recherche

• On a maintenant l’ensemble des positions possibles pour la chaîne principale, nous pouvons passer au placement des chaînes secondaires


Nicolas Ferrary

Placement des chaînes secondaires

• Nous allons prendre en compte toutes les positions de la chaîne principale une à une

• Pour diminuer la combinatoire de ce problème nous avons rajouté quelques contraintes supplémentaires pour compacter les chaînes secondaires :– Si i et j dans la même chaîne et le même sens alors dij =

0

– Si i et j parallèles alors dij (li+lj)/2

– Si i et j sont perpendiculaire alors dij = li/2 ou dij = lj/2


Nicolas Ferrary

Placement des chaînes secondaires

• Nous avons 2 approches pour l’ordre des variable dans l’arbre de recherche :– Pour ces 2 approches, nous avons l’ordre inverse des

tronçons de chacune des chaînes, et les variables pour chaque tronçon sont comme pour la chaîne principale

– Si une chaîne i se jette dans une chaîne j, elle se trouvera après la chaîne j dans l’ordre des chaînes

1) Les chaînes sont classées par ordre croissant de leur nombre de tronçons

2) Par ordre décroissant

• Nous lançons ces 2 recherches en parallèle sur chacune des positions de la chaîne principale


Nicolas Ferrary

Placement des magasins

• Nous allons travailler avec l’ensemble des meilleures positions des tronçons résultants des 2 approches précédentes

• Ce problème se rapproche d’un problème d’affectation des positions pour les magasins

• Création d’une grille dans l’atelier pour donner des emplacements aux cases des magasins– Le pas de la gille 5 mètres (trop grand nombre de variables

avec un pas de 1 mètre)

• Modèle de résolution en PLNE avec variables binaires xik où xik = 1 si la case pivot du magasin i est en k, 0 sinon


Nicolas Ferrary

Placement des magasins

/ Bx/5By/5 | Min z = ∑ ∑ ∑ fijcijdijkxik | iM jT k=1 | sujet à : | - xik = 0 ( i M, | k une des case du magasin i occupée par un tronçon ou

hors de l’atelier) |< Bx/5By/5 | - ∑ xik = 1 (i M) | k=1 | | - ∑ ∑ xij ≤ 1 (1 ≤ k ≤Bx/5By/5) | iM lL | (où L est l’ensemble des case tel que k soit occupée si le magasin i

est en l) | \ xik {0,1} (i M) (1 ≤ k ≤Bx/5By/5)


Nicolas Ferrary

Résultats

Désignation

atelier

Chaîne principale

Chaînes

secondaires

Magasins

Nb Reso Nb Reso Temps Nb Reso Temps

Bx=120,By=30 T=10,M=2

1 10 0,16 4 0,08

Bx=120,By=50 T=10,M=5

4 22 1,95 8 0,98

Bx=160,By=80 T=15,M=6

14 1 29 1 0,31

Bx=120,By=60 T=15,M=10

5 5 92 1 0,42

Bx=300,By=100 T=21,M=15

6 84 352 2 122

Bx=300,By=100 T=21,M=10

6 84 352 2 78


Nicolas Ferrary

Exemple de résultat

Bx = 120

By = 60Entrée (0,40)

Sortie (120,2

0)

1 2 3 4 5 6

8 7

9 10

11

14

12

15

13

1 8

6

3 4

710

92 5

2 3 4 5 6 7 8 9 101

13 1211 14

15

1 3 6

9

8 10

2 754


Nicolas Ferrary

Conclusion et Perspectives

• La rapidité a été privilégiée pour rendre possible une utilisation de cette résolution en milieu industriel

• Résolution rapide du problème avec des solutions relativement pertinentes vu les solutions obtenues

• Pour le placement des tronçons : – Donner plus de liberté aux tronçons,

• Travail sur le modèle de placement des magasins par :– Recherche locale sur la solution actuelle– Réduction du pas de la grille de l’atelier– Magasins rectangulaires

Documents

Nicolas Ferrary Résolution dun problème dagencement déquipements par Programmation Par Contraintes 1 Résolution dun problème dagencement déquipements dateliers