Problemformulierung Unterscheidung zwischen Problemen der

41542/ 42012 - Reihenfolgeplanung – Branch and Bound
Seite 1
Problemformulierung
Unterscheidung zwischen Problemen der
 Reihenfertigung (Flow-Shop-Probleme ) und der
 Werkstattfertigung (Job-Shop-Probleme).
Die Werkstattfertigung unterscheidet sich von der Fließfertigung, dass der Fluss der Werkstücke
nicht gleichgerichtet ist, d.h. die Maschinenfolgen aller Aufträge nicht identisch sind.
Ein Ablaufplan ist dann zulässig, wenn bei Einhaltung der Maschinenfolgen der Aufträge keine
zwei Operationen jemals gleichzeitig auf derselben Maschine stattfinden.
Ein Branch and Bound Verfahren zur Lösung von allgemeinen Flow-Shop-Problemen
 Berechnen eines Branch and Bound Algorithmus mit M = 3 Maschinen
 Verfahren nach Ignall und Schrage S. 39
Für eine gegebene partielle Auftragsfolge  gilt:
t1
der späteste Fertigstellungszeitpunkt für die Aufträge in  auf Maschine M1
t2
der späteste Fertigstellungszeitpunkt für die Aufträge in  auf Maschine M2
t3
der späteste Fertigstellungszeitpunkt für die Aufträge in  auf Maschine M3
Untere Schranke (bound) der Bearbeitungsspanne:
für Maschine M1:
s 1  t 1   p j1  min {p j2  p j3 }  min. Summe; pj1,2,3 ist Zeilensumme
x j
für Maschine M2:
s 2  t 2   p j2  min {p j3 }
(Zeit Maschine), ohne Zeitanteil pjx
s 3  t 3   p j3
für in t berücksichtigter Auftrag
x j 
für Maschine M3:
x j
x j
x j 
Untere Schranke zur minimalen Zykluszeit :
s = max { s1 , s2 , s3 }
Branch and Boud Verfahren von Ignall und Schrage
Schritt 1: Aufspalten des Anfangsknotens des Verzweigungsbaumes entsprechend des zuerst zu
bearbeitenden Auftrags in alternativ partielle Auftragsfolge
Schritt 2: Berechnen der Schranken für die neu entstehenden Knoten
Schritt 3: Zur weiteren Verzweigung - Erzeugung partieller Auftragsfolgen - wählt man jeweils
den im Verzweigungsbaum befindlichen Knoten mit dem niedrigsten Bound aus und
wiederholt Schritt 2
Schritt 4: Das Verfahren endet, wenn ein Endknoten in der letzten Zeile des Verzweigungsbaums
(vollständige Auftragsfolge) erreicht wird, dessen Bound nicht größer ist als der
niedrigste Bound aller im Verzweigungsbaum übrigbleibenden Knoten, die noch
nicht weiter aufgespalten worden bzw. nicht mehr weiter aufspaltbar sind. mit
diesen Endknoten ist eine optimale Auftragsfolge erreicht.
Beispiel KE S. 43
 Melanie Mothes/ Rolf Baumanns
WS 08/09
Seite 1
41542/ 42012 - Reihenfolgeplanung – Branch and Bound
Masch.m Auftr.j
A1
A2
A3
X1
3
4
10
X2
11
1
5
X3
7
9
13
Seite 2
X4
10
12
2
Knoten K1
Zunächst die Ermittlung der t-Werte
t1 = p11 = 3
t2 = p11 + p12 = 3 + 4 = 7
t3 = p11 + p12 + p13 = 3 + 4 + 10 = 17
Dann die Ermittlung der s-Werte (Schrankenwerte)
Exkurs : Was sind die Schranken ?
In unserem Beispiel fragen wir nach der optimalen Reihenfolge von 4 Aufträgen auf
3 Fertigungsstufen (X1 ; X2 ; X3)
 Darstellung der Reihenfolgemöglichkeiten
0
12
123 124
1234
13
14
132 134
142 143
1243 1324
3
nach 4
32
34
321 324
341 342
2
1
1342 1423 1432
21
213 214
2134
23
24
231 234
241 243
2143 2314
2341 2413 2431
31
312 314
3124
3142 3214
3241 3412 3421
Jeder Knoten stellt eine Möglichkeit dar und wir ermitteln mit dem Maximalwert aus dem
jeweiligen s1, s2, s3 die Zykluszeit der entsprechenden Möglichkeit.
Die auf der 1. Seite stehende Formel für die s-Werte (Schrankenwerte) verbal ausgedrückt :
Schranken = Wert t aus Lösungstabelle + Rest der Zeile + min. Spaltensumme unter dem Rest der Zeile
untere Schranken für Knoten K11
s1 = t1 + pj1 + min { pj2 + pj3 } = 3 + ( 11 + 7 + 10 ) + min [(1+5) ; (9+13) ; (12+2)] = 37
s2 = t2 + pj2 + min { pj3 } = 7 + ( 1 + 9 + 12 ) + min [5 ; 13 ; 2] = 31
s3 = t3 + pj3 = 17 + (5 + 13 + 2 ) = 37
S = max {s1 ; s2 ; s3} = 37
 Melanie Mothes/ Rolf Baumanns
WS 08/09
Seite 2
41542/ 42012 - Reihenfolgeplanung – Branch and Bound
Seite 3
s1 = Bearbeitungszeit der Auftragsfolge auf 1. Maschine + Bearbeitungszeit der anderen
Aufträge auf der 1. Maschine + min. Stillstandszeit der 1.Maschine bis alle Aufträge auf 3.
Maschine fertig sind.
s2 = Bearbeitungszeit der Auftragsfolge auf 2. Maschine + Bearbeitungszeit der anderen
Aufträge auf der 2. Maschine + min. Stillstandszeit der 2.Maschine bis alle Aufträge auf 3.
Maschine fertig sind.
s3 = Bearbeitungszeit der Auftragsfolge auf 3. Maschine + Bearbeitungszeit der anderen
Aufträge auf der 3. Maschine.
Maximalwert dieser drei s ergibt die min. Zykluszeit dieser Maschinenfolge
Knoten K212
Ab jetzt muss t1, t2, t3 mit Balkendiagramm ermittelt werden/oder rechnen ?? längerer Weg !
3
M1
11
4
M2
3
1
10
4
5
3
11
4
1
10
5
11
1
M3
Beim Rechnen die Spalten so sortieren wie die A-Werte sind
Wert t aus Endtabelle + Rest der Zeile + min Spalte unter dem Rest der Zeile
t1=3+11=14
t2= max (3+4+1);(3+11+1)=15
t3= max (3+4+10+5);(3+11+1+5)=22
s1 = t1 + pj1 + min {pj2 + pj3 }= 14 + (7 + 10 ) + min [(9+13) ; (12+2)] = 45
s2 = t2 + pj2 + min {pj3}= 15 + (9 + 12 ) + min [13 ; 2] = 38
s3 = t3 + pj3 = 22 + (13 + 2) = 37
S = max {s1 ; s2 ; s3 } = 45
Knoten K3132
Rechenweg wie vorher bei A1, A3 + A2
A1 A3 A2
A1
t1= 3+7+11 = 21
t2 = max
3
7
11
3
3+7+11+1 = 22
3+7+9+1 = 20
4
9
1
4
3+4+9+1 = 17
t3= max
10
3+7+11+1+5 = 27
3+7+9+1+5 = 25
3+7+9+13+5 = 37
3+4+9+1+5 = 22
immer höchsten Wert nehmen
3+4+9+13+5 = 34
3+4+10+13+5 = 35
 Melanie Mothes/ Rolf Baumanns
WS 08/09
A3
A2
7
11
9
1
13
5
Seite 3
41542/ 42012 - Reihenfolgeplanung – Branch and Bound
Seite 4
Dann die s-Werte: Wert t aus Endtabelle + Rest der Zeile + min Spalte unter dem Rest der Zeile
s1 = t1 + pj1 + min {pj2 + pj3 }= 21 + 10 + min [12+2] = 45
s2 = t2 + pj2 + min {pj3}= 22 + 12 + min [ 2] = 36
s3 = t3 + pj3 = 37 + 2 = 39
S = max {s1 ; s2 ; s3 } = 45
Knoten K3134
Schema:
A1, A3 + A4
t1 = 3+7+10 = 20
t2 = max
3+7+10+12 = 32
3+7+9+12 = 31
3+4+9+12 = 28
t3= max
3+7+10+12+2 = 34
3+7+9+12+2 = 33
3+7+9+13+2 = 34
3+4+9+12+2 = 30
3+4+9+13+3 = 31
3+4+10+13+2 = 32
1-2-3
1 2 3
1-2-3-6
1-2-5-6
1-4-5-6
1 2 3
4 5 6
1-2-3-6-9
1-2-5-6-9
1-2-5-8-9
1-4-5-6-9
1-4-5-8-9
1-4-7-8-9
1 2 3
4 5 6
7 8 9
Dann auch wieder die s-Werte
s1 = t1 + pj1 + min {pj2 + pj3 }= 20 + 11 + min [1+5] = 37
s2 = t2 + pj2 + min {pj3}= 32 + 1 + min [ 5] = 38
s3 = t3 + pj3 = 34 + 5 = 39
S = max {s1 ; s2 ; s3 } = 39
Nun eine Darstellung, wenn alle Knoten (rechts fehlt der 4. aus Platzgründen) ausgerechnet
werden würden:
0
45
37
45
45
1234
58
39
45
1243 1324
39
45
45
53
45
52
1342 1423 1432
2134
 Melanie Mothes/ Rolf Baumanns
58
46
52
52
2143 2314
54
60
65
2341 2413 2431
WS 08/09
46
58
46
3124
46
46
46
3142 3214
54
46
48
46
3241 3412 3421
Seite 4
41542/ 42012 - Reihenfolgeplanung – Branch and Bound
Seite 5
Lösungstableau:
Partielle Auftragsfolge 
X1
X2
X3
X4
X1, X2
X1, X3
X1, X4
X1, X3, X2
X1, X3, X4
( t1, t2, t3 )
(3, 7, 17)
(11, 12, 17)
(7, 16, 29)
(10, 22, 24)
(14, 15, 22)
(10, 19, 32)
(13, 25, 27)
(21, 22, 37)
(20, 32, 34)
(s1 , s2 , s3)
(37, 31, 37)
(45, 39, 42)
(37, 35, 46)
(37, 41, 52)
(45, 38, 37)
(37, 34, 39)
(37, 40, 45)
(45, 36, 39)
(37, 38, 39)
s
37
45
46
52
45
39
45
45
39
Optimale Auftragsreihenfolge: X1 , X3 , X4 , X2
 Melanie Mothes/ Rolf Baumanns
WS 08/09
Seite 5

Download Report