Equilibrage et Placement de Mobiliers dans une ligne dassemblage Michel GOURGAND Nathalie GRANGEON Patrice LECLAIRE Sylvie NORRE LIMOS UMR CNRS 6158

Equilibrage et Equilibrage et Placement de MobiliersPlacement de Mobiliersdans une ligne d’assemblagedans une ligne d’assemblage

Michel GOURGANDNathalie GRANGEONPatrice LECLAIRESylvie NORRE

LIMOS UMR CNRS 6158

Plan

1. Problématique

2. Etat de l’art

3. Proposition d’heuristiques

Perspectives

2

Plan

1. Problématique

2. Etat de l’art


Perspectives

3

1 Problématique» Ligne d’assemblage

4

1 Problématique » Définitions

5

Ligne d’assemblage : ensemble de pas pas : ensemble de postes de travail poste de travail : ensemble d’opérateurs

Séquence de véhicules : ensemble de véhicules à assembler type de véhicule : ensemble d’opérations reliées par des contraintes de

précédence opération : {durée, outils fixes, outils déplaçables, pièces}

Equilibrage affectation des opérations aux postes de travail qui respecte les

contraintes.

1 Problématique» Contraintes

6

temps de cycle

1 2 3 4

opérations pour les véhicules de type 1 affectées au poste

temps

type de véhicule

C1 Contrainte sur le temps de cycle


7


C2 Contrainte sur le temps opérateur

temps opérateur

toutes les opérations affectées à tous les véhicules de type 3à assemblerpendant une journée

1

2

3

4

temps

opérateur


8



C3 Contrainte sur les longueurs des pas de travail

étagère

colis

emballage

obstacle pièce x pour tous les véhicules de type 1

pièce y pour tous les véhicules de type 1 et 2

longueur du pas


9




C4 Contrainte de hauteur de travail

Hauteur de travail : toit, bas de caisse fenêtre


10




C4 Contrainte de hauteur de travail

C5 Contrainte de précédence entre opérations

Soient deux opérations i1 et i2.

Si i1 i2, alors :

soit i1 et i2 sont affectées au même poste,

soit i1 est affectée à un poste en amont de i2 sur la ligne.

1 Problématique» Problème du rééquilibrage

Tous les mois, la séquence de véhicules à produire peut être modifiée.

11

ajout de nouveaux types de véhicules modification du nombre de véhicules par type

mois m

mois m+1

liste de véhicules à assembler

nouvelle liste de véhicules à assembler


L’ajout de nouvelles opérations peut entraîner la violation de : C1 : dépassement du temps de cycle, C2 : dépassement du temps opérateur, C3 : dépassement de l’espace de stockage, C4 : non respect de la hauteur de travail d’un poste, C5 : non respect des contraintes de précédence.

12

Objectif adapter l’équilibrage du mois m à la séquence de véhicules du

mois m+1, en déplaçant un minimum d’opérations, de manière à

• respecter l’ensemble des contraintes,• minimiser le nombre de postes de travail,• lisser la charge des postes de travail.

1 Problématique» Historique

13

2002 2003 2004 2005 2006 …

Problème de rééquilibrage

Problème de placement de mobiliers en bord de ligne

CorinneBoutevin

PatriceLeclaire

14

Travaux de [Boutevin 2003] Heuristiques dédiées

FLBFeasible Load Based

Admissibilité d’un équilibrage

MLBMaximum Load Based

Amélioration d’un équilibrage

en réduisant le nombre de postes de travail

SLBSmoothed Load Based

Amélioration d’un équilibrage

en lissant la charge de travail des opérateurs


15

Travaux de [Leclaire 2006] Modification des heuristiques pour

• prendre en compte la contrainte de hauteur• prendre en compte de façon moins pessimiste la contrainte sur les longueurs des pas de

travail• essayer de réduire le nombre d’opérations déplacées

Implémentation des méthodes dans une interface homme / machine


16

Travaux en cours Apport de nouvelles données pour définir de façon plus précise

les bords de ligne.

Placement de mobiliers en bord de ligne.

Demande de prise en compte du déplacement de l’opérateur dans le problème de rééquilibrage.

IHM proposant des méthodes d’optimisation

1 Problématique» Problème du placement de mobiliers en bord de ligne

1 Problématique» Bord de ligne

L’ensemble des outils et pièces nécessaires à un opérateur est stocké en bord de ligne. Ce stockage doit pouvoir se faire dans l’espace disponible en bord de ligne.

17

étagère

colis

outil fixe

emballage

établi

longueur du pas

Légende

obstacle

18

étagère

colis

obstacle

emballage

établi

Légende

outil fixe


19

étagère

colis

obstacle

emballage

établi

outil fixe


Les pièces sont stockées : dans des colis pièce volumineuse dans des étagères pièce peu volumineuse

Les outils peuvent être : conservés par l’opérateur outil léger stockés dans un établi outil encombrant fixés au sol outil lourd

20

1 Problématique» Types de mobiliers

Les différents types de mobiliers à placer sont : établi étagère colis

mobilier de dimension extensiblecomprenant 3 niveaux de stockage pouvant contenir des pièces

1 Problématique» Problème de placement en bord de ligne

Le déplacement d’un opérateur pour se munir des pièces et outils nécessaires à la réalisation des opérations n’est pas négligeable.

Ce déplacement n’apportant pas de valeur ajoutée doit être minimisé. Le placement du mobilier en bord de ligne permet de réduire ces

déplacements.

21

Objectif minimiser le temps total de déplacement de l’opérateur, en proposant un placement des mobiliers, ainsi qu’un placement des

pièces dans les étagères, de manière à

• respecter l’ensemble des contraintes d’équilibrage,• tenir compte des obstacles et mobiliers non déplaçables,• placer les pièces et outils dans les mobiliers adéquats.

Plan

1. Problématique

2. Etat de l’art


Perspectives

22

Installation

Réarrangement

Rééquilibrage

Séquencement global

Séquencement court-terme

SéquencementSéquencement

EquilibrageEquilibrage

2-5 ans

6 mois – 2 ans

1 mois – 1 an

1 semaine – 1 mois

journée

Horizon de planificationHorizon de planification

2 Etat de l’art» Horizons de planification

[Scholl 1999]23

2 Etat de l’art» Problèmes théoriques d’équilibrage

SALBP : Single Assembly Line Balancing Problem ligne en série, temps de cycle identiques pour chaque poste, précédence entre opérations, un seul type de produit, pas de restriction d’affectation, durée des opérations déterministe.

MALBP : Multi-Model Assembly Line Balancing Problem plusieurs types de produits

GALBP : Generalized Assembly Line Balancing Problem contraintes moins usuelles :

• groupement d’opérations,• incompatibilités,• obligations, …

[Baybars 1986]24

2 Etat de l’art» Problème de rééquilibrage

Définition : modification de l’affectation des opérations au poste pour prendre en

compte des modifications des paramètres d’entrée d’une ligne. de manière à

• respecter l’ensemble des contraintes,• minimiser le nombre d’opérations déplacées.

25

Problème peu abordé dans la littérature [Gamberini et al 2005] : proposition d’heuristiques multicritères [Sculli 1979] : proposition de modèles pour la gestion dynamique d’une ligne d’assemblage [Sculli 1984] : proposition d’une heuristique

Nombreux logiciels dédiés [Dolgui 2005] PLM Process Planning (Delmia) ERGOPlan (DELTA)

2 Etat de l’art» Problème théorique de placement de mobiliers

SRFLP : Single Row Facility Layout Problem trouver un arrangement optimal de n mobiliers de tailles différentes li (i=1..n) rangés en ligne selon une direction

donnée de manière à minimiser la somme pondérée des distances entre toutes les paires de mobiliers (distance prise entre leurs

centroïdes) en tenant compte de l’intensité du trafic cij entre les paires de mobiliers (i,j)

26

Etat de l’art en cours …

Ce modèle ne prend pas en compte : des étagères de taille modulable, le déplacement entre le véhicule et le bord de ligne, le déplacement à vitesse constante du véhicule.

aspects industriels

Plan

1. Problématique

2. Etat de l’art


Perspectives

27

3 Proposition d’heuristiques» Méthode de résolution

28

Rééquilibrage

Placementdu mobilier Calcul des

déplacements

vérification des contraintes

Placementdes pièces

dans les étagères

3 Proposition d’heuristiques» Placement de mobiliers en bord de ligne

29

Données en entrée : type et taille de stockage nécessaire pour les éléments ensemble des éléments à placer pour chaque opération

Permettent de déterminer : un ordre sur les opérations une liste des éléments (pièces et outils) à placer un placement des mobiliers un placement des éléments à l’intérieur des étagères les déplacements de l’opérateur entre le véhicule et le bord de ligne

De nouvelles données sur les emballages des pièces et des types de mobiliers de stockage pour ces pièces et les outils nous amènent à appréhender le bord de ligne de façon plus précise.


30

Hypothèses Les opérations les plus fréquentes sont réalisées en « début de pas » Les éléments les plus utilisés sont placés le plus à gauche possible

Le type de mobilier « étagère » est le seul type dont la taille peut être modulée(taille bornée)

Méthodes de placementinspirées de méthodesdédiées au Bin-Packing


31

Principe général de l’heuristique (pour chaque poste)

Déterminer la liste des opérations Pour chaque opération faire

• Déterminer la liste des éléments à placer• Pour chaque élément faire

• Suivant le type de stockage de l’élément,Affecter l’élément dans un mobilier (hors étagère)ou

Placer l’élément dans une étagèreSi le type de mobilier n’existe pas alors Créer un nouveau mobilier le plus à gauche possible

Sinon Agrandir une étagère déjà existante suivant une règlesuivant une règle

Fin Si• Fin Suivant

• Fin Pour Fin Pour


32

Les éléments sont placés de gauche à droite dans la limite de la place disponible sur le bord de ligne (prise en compte des obstacles)

boîte 1 boîte 2

Bin Packing Gestion des étagères

Boîte Zone de stockage entre les obstacles

Objet Mobilier

Placement de mobilier (1/2)


33

S’il ne reste plus de place sur le bord de ligne courant, placer les éléments sur le bord de ligne d’en face.

S’il ne reste plus de place sur le bord de ligne d’en face, placer les éléments sur le pas suivant.

Placement de mobilier (2/2)


34

Création des étagères (1/3)


Boîte Etagère

Objet Elément à placer

Heuristique 1 : Basée sur le principe de l’heuristique Next-Fit placement dans l’étagère courante agrandissement de l’étagère courante si nécessaire et si possible, sinon création d’une nouvelle étagère

étagèrecourante


35


Heuristique 2 : Basée sur le principe de l’heuristique Best-Fit les éléments sont placés dans l’étagère contenant le plus de place agrandissement de l’étagère si nécessaire et si possible s’il ne reste plus de place, création d’une étagère supplémentaire


36


Heuristique 3 : identique à l’heuristique 2 possibilité de déplacer certains mobiliers pour pouvoir agrandir une étagère


37

Placement des éléments à l’intérieur d’une étagère


Boîte Niveau d’une étagère

Objet Elément à placer

Principe de placement : basé sur le principe de l’heuristique Best-Fit les éléments sont placés dans le niveau possédant

le plus de place libreen les calant à gauche

s’il ne reste plus de place,voir les règles de créationdes étagères.

boîte 3

boîte 2

boîte 1

3 Proposition d’heuristiques» Calcul du déplacement de l’opérateur

38

11

22

33

» 11Déplacement entre le véhicule et le premier mobilier

» 22Déplacement entre lesdifférents mobiliers

» 33Retour au véhicule


39

11

Soit bbkk, k=1..mk=1..m, la position du kk-ème élément associé à l’opération courante.

Soit xx la position de l’opérateur au début du calcul.

Soit dd la distance entre le véhicule et le bord de ligne.

axe des abscisses

axe des ordonnées

(0,0)

(b1,d)d

(x,0)

Le déplacement 11 vaut :

D1 = (x - b1)² + d²

22


D2 = (bk+1 - bk)k = 1

m - 1


40

Pendant le déplacement de l’opérateur à vitesse vvOO le véhicule s’est déplacé à la vitesse vvVV.

Soit r = vr = vOO / v / vVV.

Le point de rencontre a pour abscisse

d

xV =axe des abscisses(0,0) (xV,0)

(xO,d)

xO + xO² - (1-r)(xO²+d²)

2(1-r)

D3 = (x + (D1 + D2) + xV - bm)² - d²

33


vV

vO

déplacement du véhicule pendant la prise des pièces

déplacement du véhicule jusqu’au point de rencontre

Perspectives

41

Les heuristiques permettent d’obtenir une première solution satisfaisante.

Ces méthodes ont été implémentées dans une IHM proposant de modifier l’équilibrage et le placement en bord de ligne.

Nos perspectives : Améliorer les solutions obtenues par les heuristiques grâce à une métaheuristique à base de recuit simulé, … Intégrer la phase de placement de mobilier dans les heuristiques de rééquilibrage. Proposer un modèle mathématique pour le problème de placement

Documents

Equilibrage et Placement de Mobiliers dans une ligne dassemblage Michel GOURGAND Nathalie GRANGEON Patrice LECLAIRE Sylvie NORRE LIMOS UMR CNRS 6158