Embed Size (px)
Citation preview
GPA750 – Ordonnancement des systèmes de production
aéronautique
Cours # 4
Problème avec plusieurs machines
• Machines en parallèles
• Complexité des problèmes avec plusieurs machines.
• Environnement et Organisation (Atelier mono-gamme vs Multigammes)
• Représentation réseau d’un calendrier
Machines ParallèlesMin Fmoy
• n commandes• m machines en parallèles• Toutes les commandes sont disponibles au temps
t=0• Algorithme pour minimiser le temps de passage
moyen (Min Fmoy ) :– Ordonner les commandes selon SPT;– Prendre les commandes une à la fois et les assigner sur
la machine ayant le plus petit temps total d’opération.
Exemple de SPT
• Exemple
– Séquence SPT : 6-10-3-7-9-1-8-2-5-4
j 1 2 3 4 5 6 7 8 9 10pj 5 6 3 8 7 2 3 5 4 2
Fmoy = 8.1Cmax = 18
Machines Parallèles : Min Cmax et Temps de passage moyen (Fmoy )
• Heuristique pour minimiser Cmax :– Ordonner les commandes selon LPT;– Prendre les commandes une à la fois et les assigner sur la
machine ayant le plus petit temps total d’opération.
• Pour minimiser Cmax et Temps de passage moyen (Fmoy)– Renverser les séquences sur les machines de sorte que l’on a
une séquence SPT.• Exemple…• Ne garantit pas l’optimalité• Qualité de la solution
–
( ) 4 1
( ) 3 3Max
opt
C LPT
C OPT m
Exemple : Min Cmax et temps de passage moyen
Étape 1: LPT
Étape 2: SPT
Cmax = 16
Fmoy = 8.1
Machines Parallèles : Réduire T
• Heuristique 1: Min Tmax
– Ordonner les commandes selon EDD;– Prendre les commandes une à la fois et les assigner sur
la machine ayant le plus petit temps total d’opération.
• Heuristique 2 : Réduire T– Ordonner les commandes selon SLACK (Marge);
• dj-pj
– Prendre les commandes une à la fois et les assigner sur la machine ayant le plus petit temps total d’opération.
• Exemples• Ne garantit pas l’optimalité
Exemple pour Réduire T
Heuristique 1: EDD
Heuristique 2: SLACK
Tmoy = 0.6 Tmax = 43 commandes en retard
Tmoy = 1.3, Tmax = 5, 6 commandes en retard
Machines Parallèles :Min le nombre de commandes en retard
• Etape 1: Appliquer l’algorithme EDD pour les machines parallèles.
• Étape 2: Pour chaque machine, appliquer l’algorithme de Moore pour minimiser le nombre de commandes en retard sur une machine.
• Exemple…
• Ne garantit pas l’optimalité
Sommaire
Problèmes avec une machine où toutes les commandes sont disponibles au temps 0 Objectif Algorithme Observations 1 Min Fmoy SPT Calendrier optimal 2 Min Temps total pondéré WSPT Calendrier optimal 3 Min Lmax EDD Calendrier optimal
4 Min nbre de commandes en retard Algorithme de Moore Calendrier optimal
5
Min Temps de passage moyen avec chaînes de préséance SPT modifié Calendrier optimal
6
Min Max j { γj(Cj) } avec contraintes de préséance Algorithme de Lawler Calendrier optimal
7 Min J
j
T Min SLACK en premier Ne garanti pas l’optimalité
Problèmes avec machines en parallèles Objectif 1 Minimiser Fmoy SPT Calendrier optimal 2 Min Cmax LPT Ne garanti pas l’optimalité
3 Min Cmax et Fmoy LPT et ensuite SPT sur les machines Ne garanti pas l’optimalité
4 Min Tmax EDD Ne garanti pas l’optimalité
Complexité des problèmes• Procédures simples qui donnent la solution optimale pour certains
problèmes.• Solutions approximatives pour d’autres…
– Peut-on trouver la solution optimale?• Oui mais…
• Deux classes de Problèmes – P vs NP
• ‘faciles’ vs ‘difficiles’ – P: On peut trouver une solution dans un temps polynomial
• Exemple: règle de Johnson.– NP: Algorithme avec temps de résolution exponentiel
• Exemple: énumération complète ou implicite. – Note : P est un sous-ensemble de la classe NP
• Donc la plupart des problèmes avec plus de 3 machines font partie de la classe NP .
Complexité des algorithmes et des temps de résolution
Une opération = 1 micro seconde
Complexité
Types d’environnementsAtelier Mono-gamme Atelier Multi-gamme
Atelier Monogamme(Flowshop)
• Pour une mesure de performance régulière, il suffit de considérer les calendriers avec la même séquence sur les machines M1 et M2
– Preuve: Faire k avant i sur m1
– Ne change pas les temps de début sur m2
• Il suffit de considérer les calendriers ayant les mêmes séquences sur les machines Mm-1 et Mm afin de minimiser Fmax
– Preuve: Faire i avant k sur Mm
– ne change pas Fmax
• Donc, en pratique, on considère des séquences de permutation seulement dans les ateliers monogammes.
Atelier MonogammeAvec encours
• Séquence de permutation• J1, …, Jn
– Formules pour calcul des temps de finition• Pij – temps d’opération de la commande j sur la machine i
– Temps de finition de la première commande sur la machine 1» Eq (1);
– Temps de finition de la kième commande sur la machine 1:» Eq (2)
– Temps de finition de la kième commande sur la machine i» Eq (3)
»
, 1 , 11
i,Jk 1,1
, 1, , 1 ,
, 1,..., (1)
C , k = 1,...,n (2)
max( , ) i=2,...,m; k=2,...,n (3)
i
i J i Jh
k
Jkh
i Jk i Jk i Jk i Jk
C P i m
P
C C C P
Représentation réseau
Cmax = Plus long chemin dans le réseauExemple
Atelier MonogammePas d’encours
• Pas d’encours entre les machines• Blocage des machines
– Représentation réseau• Ajouter les nœuds (0,Jk), k=1,...,n• Les autres nœuds (i, Jk), i=1,…,m, k=1,…,n• le nœud (i, Jk), représente le temps de départ de la commande k sur
la machine i• Le nœud (i, Jk) a deux arcs sortant:
– (i+1, Jk) avec comme valeur Pi+1,Jk – (i-1, Jk+1) avec une valeur de Zero
– Note : Un problème avec encours limité peut être converti en un problème avec zéro encours.
• Ajouter le nombre de machines nécessaires avec des temps d’opération de zéro.
Atelier MonogammePas d’encours
• Soit Dij le temps où la commande j quitte la machine i
• Di,J1 = h=1i Ph,J1
• Di,Jk = max(Di-1,Jk + Pi,Jk , Di+1,Jk-1 )
• Dm,Jk = Dm-1,Jk + Pm,Jk
•
Exemple – Sans encours
Atelier MonogammePas d’encours
• Cas spécial 1:– Deux machines sans encours
• Peut être converti en un cas spécial du problème de commis voyageur
• Cas Spécial 2: – Pas de temps d’attente entre deux opérations
de la même commande– Solution…
• Plus tard
Atelier Multigamme
J1
J2
J3
J4
Représentation d’une séquence réalisable:• Fixer les arcs sur les machines de sorte qu’il n’y ait pas de cycle
