Upload
nicolette-tardy
View
122
Download
0
Embed Size (px)
Citation preview
Ligne d’Assemblage
Professeur Amar Ramudhin, ing. Ph.D
Introduction
• Une ligne d’assemblage consiste en un nombre de station en série
• Types de ligne d’assemblage– Ligne dédiée à une famille de produit
• Un modèle à la fois sur la ligne– Ligne multi-modèles:
• Plusieurs produits en même temps sur la ligne– Chaîne de montage synchronisée (Paced assembly line)
• à vitesse constante, c.à.d chaque travaille C unité de temps• Le système de manutention va envoyer le produit à la station
suivante même si l’opération n’est pas complétée…• Le temps de cycle C doit être ajusté pour tenir compte des
variabilités des temps d’opérations– Chaîne de montage non synchronisée (Unpaced assembly
system)• Durée de tâches variables
Exemple
Ligne d’assemblageEncoursIntroduction Des Pièces
Ligne d’assemblage Flexible
m1
m2
mn
m1
m2
mn
m1
m2
mn
….
• Plusieurs stations en parallèle à chaque étape• Les commandes sont assignées à une station en fonction des besoins de la tâche et de l’encours aux stations• Système de manutention automatisée
Formulation Mathématique• Taux de Production: P unité par période• Temps de Cycle C= 1/P• Note: si on a m lignes en parallèle alors
– C=m/P• Contrainte de Préséance:
– IP = {(u,v) : tâche u doit immédiatement précéder v}• Restrictions de zonage
– ZS = ensemble de tâches qui doivent être assignées à la même station– ZD = ensemble de tâches qui ne peuvent être assignées à la même
station• Variable binaire Xik
– Prend la valeur 1 si la tâche i est assignée à la station k• Soit K le nombre maximale de station dans la ligne• Afin de minimiser le temps mort sur les stations on va forcer les tâches dans
les stations ayant les numéros les plus bas• Soit cik, le coût d’assigner la tâche i dans la station k. La structure de cik est
telle que:– Ncik ≤ ci,k+1, pour k=1,…K-1
Modèle de Programmation Mathématique
1 1
N
ii=1
K
k=1
h
j=1
K
k=1
1)
.
2) t k=1,...,K
3) =1 i=1,...,N
4) h=1,...,K et (u,v) IP
5) = 1 (u,v) ZS
N K
ik iki k
ik
ik
vb uj
uk vk
Min c X
s à
X C
X
X X
X X
6) 1 k=1,...,K et (u,v) ZD
7) 0,1uh uh
ij
X X
X
Temps de Cycle
Contraintes
Assignation des tâches
Contrainte de préséance
Contraintes de Zonage
Modèle de Programmation Mathématique
• Contrainte de préséance– Exemple: 3 stations;– la tâche 2 doit précéder la tâche 3
• X31 ≤ X21
• X32 ≤ X21 + X22
• X33 ≤ X21 + X22 + X23
• Contrainte de zonage 5) est non linéaire– Agréger les tâches qui doivent être faites à une même station en
une super tâche– Élimine la contrainte 5)
• Nombre min de station:– ┌ T/C ┐
– Où T = ∑ti
Solutions Heuristiques
• En pratique on veut trouver une solution à un des problèmes suivants:– Étant donné un temps de cycle trouver le
nombre minimum de station (ou de personnes) sachant pour chaque tâche son temps d’opération, ses préséances et les restrictions de zonage
– Étant donné un nombre de station, trouver le temps de cycle minimal
Notations
• C – temps de cycle
• Sk – ensemble de tâches assignées à la station k=1,…,M
• ti – temps d’opération de la tâche i, i=1,…,N
• T – temps total disponible pour la séquence d’assemblage requis
• Q – La quantité requise– C = T/Q
• Restrictions:– 1 ≤ M ≤ N : Moins de
stations que de tâches– ti ≤ C
• Efficacité de la ligne:
• Efficacité de la station k
1
100N
ii
t
CM
100k
jj S
t
C
Algorithme de Helgeson-Birnie (HB)
• Assigner les opérations aux stations selon leurs poids de ‘positionnement’ en considérant les contraintes de préséance, de zonage et de temps.
• Poids de positionnement d’une tâche i:– Somme des temps de i et de toutes les
tâches qui succèdent i– e.g.
1
2
4
3
55
13 3
5 2
poids tâche 1 = 5+13+3+5+2 = 28
Autres règles
• On peut utiliser les règles suivantes au lieu du poids de positionnement dans l’assignation des opérations au stations:– + grand nombre des successeurs d’un nœud;– + grand nombre de successeurs immédiats; – + grand poids des successeurs immédiats;
• On peut combiner des règles:– Exemple:
• + grand poids en premier. Si égalité choisir l’opération ayant le plus grand temps d’opération
Exemple
Temps de Cycle: 21
Exemple: Résolution à l’aide de la procédure de HB
- Temps de cycle :21
- Nbre min de station : 105/21 = 5
- Efficacité de la ligne: (105)/(6*21) = .833
- Éfficacité de la 6ième station 2/21 = .095
Exemple avec Temps de Cycle de 22
• Station 1– Operations: 1 – 3- 4- 2– Temps total: 21
• Station 2– Operations: 5-7-6– Temps total: 21
• Station 3– Operations: 8-9-11-12-
10-15– Temps total: 22
• Station 4– Operations: 13-16-17– Temps total: 21
• Station 5– Operations: 18-21-14-
20-19– Temps total: 20
• Éfficacité ?
Approche par Région
• Le problème avec l’approche précédente– une tâche ayant un poids élevé peut s’avérer
moins critique qu’une tâche ayant beaucoup plus de successeurs mais avec des temps d’opérations moindre
• Approche par région tends à corriger cette situation
Approche par Région1. Développer le réseau de préséance2. Assignation des régions de préséance:
• Redessiner le réseau en assignant les tâches aux régions de préséance les plus éloignés
3. Dans une région lister les tâches en ordre décroissant des durées• Laisse les petites tâches pour la fin
4. Assigner les tâches en suivant les règles suivantes (en considérant les autres contraintes de zonages, etc.)
• Les tâches des régions les plus à gauche en premier• À l’intérieur d’une région, la plus grande tâche en premier
5. À la fin d’une assignation pour une station, décider si l’utilisation est acceptable
• Si non parmi l’ensemble des tâches qui reste dont les prédécesseurs ont été assignés,
• trouver le sous-ensemble des tâches dont les prédécesseurs sont dans des régions plus à gauche que les tâches assignées. Inter changer les tâches et déterminer s’il y a augmentation de l’utilisation.
• Si oui la nouvelle assignation est finale
Ligne d’assemblage mixte
• Lorsque différents produits sont assemblés sur une même ligne on peut assumer qu’il y a une grande similarité entre les produits– Plusieurs tâches communes
• Construire le réseau combiné
Produit 1
Produit 2
Réseau combiné
4 3
Résultat avec le réseau Combiné
• En appliquant l’algorithme de HB avec C=10 sur le réseau combiné on a le résultat suivant:
1,4,57
8,97
66
2,39
10,7,1110
tâchestemps
11
8,97 0
2,39
7,115
tâchestemps
1,4,57
93
66
34
10,7,1110
tâchestemps
Produit 1: Efficacité: (22*100)/(5*10) = 44%
Produit 2: Efficacité: (30*100)/(5*10) = 60%
Efficacité: (39*100)/(5*10) = 78%
Procédure améliorée
• En réalité, il y a seulement un produit différent par poste– Donc diminution de l’efficacité
• Solution logique
• Accumuler les temps des tâches assignées par produits séparément
Station tâche ti Cumul ti ti Cumul tiI 1 1 1 1 1
4 0 1 1 25 0 1 5 78 4 5 0 79 3 8 3 10
II 6 0 0 6 62 5 5 0 63 4 9 4 10
III 10 0 0 5 57 2 2 2 7
11 3 5 3 10
Produit 1 Produit 2
tâche 1 4 5 8 6 9 2 3 10 7 11Poids depositionnement 39 17 16 15 11 11 10 9 8 5 3
Autre méthode pour ligne multi-modèle
• Posons
où est la proportion du modèle j à produire
• Utiliser le temps moyen pour construire la ligne.
• Soit– dj : demande du modèle j– Demande totale: D=j dj– T: Horizon de planification– : temps de l’opération i du modèle j
j
ijji twt
jw
ijt
Lissage et Ordonnancement des modèles d’une ligne mixte
• Le temps de cycle minimal est:– Où
est l’ensemble de tâches assignées à la station k
• Le temps d’introduction idéal pour la nième unité du modèle j est
• On peut trouver la séquence mixte en fusionnant les temps de début des séquences individuelles en une seule séquence non avec des temps de début non-décroissant.
• Les unités de production sont introduites dans la chaîne à chaque c unité de temps.
kSiik tc maxmin
kS
jnj d
TnS
)1(
jnj d
TnS
)1(
Exemple• T = 4 heures (240 mins)
• 3 modèles de voitures:– 10 sedan (S)– 6 hachback (H)– 4 station wagon (W)
• Total de 20 voitures
• C = 240/20 = 12 minutes
• Temps d’introduction en considérant les modèles séparément:– Sedan: 240/10 : à chaque 24 minutes
• Temps d’entrée: 0,24,48,72,96,120,144,168,192,216– Hachback: 240/6 : à chaque 40 minutes
• Temps d’entrée: 0,40,80,120,160,200– Station wagon: 240/4 : à chaque 60 minues
• Temps d’entrée: 0,60,120,180
Résultat
• Combiner les 3 vecteurs en un vecteur – en donnant priorité au modèle ayant la plus
grande demande (en cas d’égalité)• S: 0,24,48,72,96,120,144,168,192,216• H: 0,40,80,120,160,200• W: 0,60,120,180
• Séquence résultants:– S-H-W-S-H-S-W-S-H-S-S-H-W-S-H-S-W-S-
W-S
Temps Stochastique
• ti est normalement distribué avec moyenne μti et variance V(ti)
• De la loi centré réduite on a:– t = μt + z(σt)
• Donc pour une station, avec une probabilité α, la valeur du temps t est
1/ 2
1 1
( )n n
i ii i
t t z V t
Exemple avec α=99.4%
• α=99.4% et donc z=2.5
Tâches en ordre décroissant de positionnement: B – A – C – D – E – F - G
Solution Déterministe
Station tâches ti cumul tiI B 5 5
A 3 8E 2 10
II C 6 6D 4 10
III F 4 4G 3 7
3 Stations
Solution Stochastique
Station tâches tiCumul
ti ViI B 5 5 2 1.4 8.5
II A 3 3 1 1 5.5E 2 5 0 1 7.5
III C 6 6 2 1.4 9.5
IV D 4 4 1 1 6.5G 3 7 0 1 9.5
V F 4 4 1 1 6.5
1/ 2(2.5)i it V 1/ 2
iV
5 Stations