Introduction

Agencement d’équipements 1

Problème de placement : agencement d'équipements dans une usine de montage automobile

(facility layout)


Introduction

• Présentation du contexte industriel : le montage automobile

• Etat de l'art sur le problème d'agencement d'équipements

• Description du modèle PPC (Programmation Par Contraintes)

• Premiers résultats et constatations • directions que l'on peut (va) suivre pour

améliorer le modèle


Contexte industriel / Fabrication d'un véhicule

• 4 étapes: • emboutissage • tôlerie schema de fabrication d'un

véhicule • Peinture • assemblage


Contexte industriel / Assemblage

• graphe de montage schéma d'un graphe• les tronçons de montage • les magasins et l’approvisionnement


Contexte industriel / Assemblage / Tronçon de montage

schéma de tronçon • défini par :

– un temps de cycle – nombre et caractéristiques de pas de chaîne – nombre et caractéristiques des postes de travail – les pièces montées sur le véhicule


Contexte industriel / Assemblage / Approvisionnement

• pièces stockées dans des magasins • différents types d'approvisionnement

– par car à fourche – par train de bases roulantes

• magasins peuvent stocker des pièces pour plusieurs tronçons différents

besoin d'un réseau d'allées pour le réapprovisionnement


Contexte industriel / Description d'un atelier

• Contient les tronçons de fabrication et les magasins

• On retrouve :– des flux de productions (principal : trajet de la caisse

et secondaire : trajet des module de préparation )– des flux d'approvisionnement dans notre atelier


Problématique

• Plusieurs cas possibles d'atelier: – à construire – atelier existant vide – atelier existant avec des zones fixées

• Placer dans un atelier les zones de fabrications (tronçons) et les zones de logistiques (magasins) de façon à minimiser les coûts (d'investissements) en tenant compte – des flux de production – des flux d'approvisionnement – de la taille de l'atelier (si elle est définie)


Etat de l'art / Evaluation

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

rij : score d'adjacence entre la zone i et la zone j xij : binaire 1 si i et j adjacents 0 sinon Max z = somme somme rij*xij

– « from-to chart »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 Min z = somme somme fij*cij*dij


Etat de l'art / Représentation graphique

Représentation discrète Représentation continue


Etat de l'art / Optimisation

• Représentation topologique • Représentation par graphes d'adjacences • Représentation par arbre de découpe • Problème d'affectation quadratique • Programme Linéaire en Nombres Entiers


Etat de l'art / Optimisation /Représentation topologique

• adaptées aux approches constructives et recherche locale

• constructive: – SHAPE : glouton qui place le zones en commençant par le

centre– MULTIPLE (représentation discrète) case numérotée

formant une courbe continue dans l'ordre croissant (serpentin) placement des zones dans une séquence de cases continues forme compacte

• recherche locale (améliorations de la solution trouvée par algorithme constructif): – CRAFT échange de zones adjacentes ou de zones de même

taille (en supposant surface fixe et forme libre)


Etat de l'art / Optimisation /Graphes d'adjacences

• approche relationship chart, représentation continue

• graphe dont les nœuds représentent une zone et les arêtes les relations d'adjacences entre les zones

• pas de prise en compte de forme, surface, non-superposition

• nécessité d'arriver à un graphe planaire • algo de construction gloutonnes partir de

triangle voire hexagone


Etat de l'art / Optimisation /Arbre de découpe (slicing tree)

• représentation continue • création d'un "floorplan" c'est-à-dire une

partition du rectangle initial • on peut représenter alors cette solution par un

arbre (binaire) dont chaque nœud correspond a une coupe verticale ou horizontale

• améliorations se font en cherchant un nouvel arbre


Etat de l'art / Optimisation / Problème d'affectation quadratique

• approche from-to chart, représentation discrète

• affecter à chaque zone une et une seule position

fij : flux entre les zones i et jcij : coût entre les zones i et jdlk : distance entre la position l et k xik : 1 si la zone i est dans la position j, 0 sinon Min z =som som som som fij*cij*dlk*xik*xjl


Etat de l'art / Optimisation /PLNE

• approches from-to chart• variables continues représentant:

– abscisse et ordonnée du centre des zones – distance en abscisse et distance en ordonnée entre

les zones – longueur et largeur des zones

• variables binaires : informations sur la localisation respective de zones 2 à 2

• difficile de trouver une solution exacte sauf pour des problèmes de petite taille


Etat de l'art / Synthèse

• Modèles présentés sont très génériques • On trouve une grande quantité de travaux

spécifiques à des problèmes très précis, donc :– ils sont difficiles à réutiliser dans d'autres contextes

que celui spécifié– il y a souvent beaucoup de variables et de

contraintes spécifiques


Définition du modèle PPC

• définition des zones • des relations entre les zones • des données du problème • des variables de décisions • de la fonction objective • des contraintes


Modèle PPC / Définition des zones

• On considère que les zones sont entourées d'une 1/2 allée pour pouvoir créer un réseau d'allées dans l'atelier de façon à éviter des problèmes de congestions dans le trafic

• Différentes zones dans l’atelier :– tronçons de montage– magasins


Modèle PPC / Définition des zones /Tronçons

• Possède une entrée et une sortie • il peut avoir 4 orientations possibles (horizontale

droite-gauche / gauche-droite ou verticale haut-bas / bas-haut)

• chaque tronçon est approvisionné par un seul magasin


Modèle PPC / Définition des zones /Magasins

• Aucune entrées ou sorties spécifiées multitude d'accès

• pas d'orientations • un magasin peut approvisionner plusieurs

tronçons • le nombre total de magasins et la surface de

chacun des magasin sont connus


Modèle PPC / Coûts entre les zones

• modèle basé sur une approche from-to chart et une représentation continue

• tronçon-tronçon : production – coût d'investissement en fonction du flux de

production et de la distance de convoyage (distance entre le premier tronçon et le deuxième tronçon)

• magasin-tronçon : manutention – coût d'investissement du nombre d'engins (en

fonction du flux) et de leur temps de parcours (en fonction de la distance) distance de centre à centre de zone


Modèle PPC / Données du problème

• Toutes les variables sont entières (sauf les flux et les coûts)– Bx, By : longueur et largeur du bâtiment – Li, li : longueur et largeur de chaque tronçon – M : nombre de magasins – T : nombre de tronçons – Ai : aire de chaque magasin – diinf et disup :la distance minimum et maximum (pour chaque

magasin) que peut prendre la longueur d'un magasin – aij : les positions d'arrivées sur la chaîne principale des

chaînes secondaires (entrées, centre ou sortie) – fij : flux entre 2 zones– cij : coût unitaire en unité de flux et de distance entre 2

zones


Modèle PPC / Variables de décisions

• toutes les variables sont entières sauf les distances– xi, yi : (>=0) : abscisse et ordonnée du centre de chaque

zone – hi, vi : {Li, li} : taille du tronçon i en abscisse et ordonnée – hi, vi : [diinf, disup] : taille du magasin i en abscisse et

ordonnée – eih, eiv : {-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)


Modèle PPC / Calcul des distances

• distance de Manhattan pour le calcul (distance = somme des écarts des abscisses et des ordonnées)

• distance de manutention (magasin i et tronçon j) – dij = |xi-xj| + |yi-yj|

• distance de production – dij = |(xi-eih*hi/2)-(xj-aj*ejh*hj/2)| +

|(yi-eiv*vi/2)-(yj-aj*ejv*vj/2)|


Modèle PPC / Fonction objective

• manutention : M*T • production : T*T


Modèle PPC / Contraintes

• Contraintes prises en compte par le modèle :– positionnement dans l'atelier – dimensions des magasins – dimensions et orientation des tronçons – non superposition des zones


Modèle PPC / Contraintes /Positionnement dans l'atelier

hi/2 <= xi <= Bx-hi/2 vi/2 <= yi <= By-vi/2

pour chaque zone i


Modèle PPC / Contraintes /Dimensions des magasins

• hi*vi >= Ai • contrainte pour garder des valeurs entières

aux dimensions du magasin i


Modèle PPC / Contraintes /Dimensions et orientation des

tronçons si longueur verticale alors largeur horizontale et

vice et versa hi + vi = Li + li

orientation verticale ou horizontale eih=0 <=> eiv!=0

entrée du coté de la largeur eih!=0 => hi=Li

entrée du coté de la largeur eiv!=0 => vi=Li


Modèle PPC / Contraintes /Non superposition des zones

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

i et j zone


Premiers résultats

• 20x80 • 10x40• 10x50 • 15x50


Premiers résultats / Synthèse

• Eviter les dimensions impaires pour cela multiplication de la valeur des données par 2 Superposition des flux sur des tronçons


Orientations

• considérer que 2 tronçons se touchent • fixer un tronçon au centre d'un atelier sans

contrainte de taille • accoler les tronçons de la chaîne principale

dans le sens de la longueur de l'atelier

Documents

Introduction