16
34 Feinplanung und Steuerung
34.1 Einf¨uhrung
Auf- An- Liefertermin AG 1 AG 2 AG 3 AG 4
trag kunft Masch Zeit Masch Zeit Masch Zeit Masch Zeit
1 0 11 1 3 3 2
2 1 10 3 1 2 3 3 3 1 2
3 3 8 3 1
Der folgende Netzplan zeigt die einzelnen Arbeitsg¨ange der drei Auftr¨age. Der jeweils
erste Arbeitsgang (blau) ist ein Dummy, den man als Wartezeit auf die Auftragsankunft
interpretieren kann. Die Farben bezeichnen die unterschiedlichen Ressourcen. In je-
dem Knoten steht oben die Vorgangsdauer und unten das Wertepaar (Ressourcennum-
mer/Anzahl ben¨otigter Einheiten).
Beispiel
AN1 11
3
1/1
12
2
3/1
AN2
1
4/1
21
1
3/1
22
3
2/1
23
3
3/1
24
2
1/1
AN3
3
4/1
31
1
3/1
S
Keine B er¨ucksichtigung von Ankunftszeiten
11/1
12/121/1
22/1
23/1
24/1
31/1
1
2
3
4
Ressource
1 2 3 4 5 6 7 8 9 10
220
Keine B er¨ucksichtigung von Ankunftszeiten
1/1
3/1
3/1
2/1
3/1
1/1
3/1
11
12
21
22
23
24
31
Arbeitsgang
1 2 3 4 5 6 7 8 9 10
Ber¨ucksichtigung von Ankunftszeiten
11/1
12/121/1
22/1
23/1
24/1
31/1
1
2
3
4
Ressource
1 2 3 4 5 6 7 8 9 10 11
Ber¨ucksichtigung von Ankunftszeiten
1/1
3/1
4/1
3/1
2/1
3/1
1/1
4/1
3/1
11
12
AN2
21
22
23
24
AN3
31
Arbeitsgang
1 2 3 4 5 6 7 8 9
10 11
221
34.2 Merkmale von Reihenfolgeproblemen
Merkmale
Produktionsstruktur
Auftragszugangsprozeß
Bearbeitungsprozeß
Z ielsetzungen
Produktionsstruktur
eine Maschine
parallele Ressourcen
Reihenproduktion (flow shop)
Werkstattproduktion (job shop)
Zielsetzungen
A uftragsorient ier te Zeitgr¨oßen
Durchlaufzeiten
Wartezeiten
Lagerzeiten
Transportzeiten
Termin¨uberschreitungen
Liefertermine
R essourcenbezogene Zeitgr¨oßen
Kapazit¨atsauslastungen
Gesamtbelegungszeiten
R¨ustzeiten
Leerzeiten
222
34.3 Auftragsbezogene Zielsetzungen
Durchlaufzeit
D
p
= F
p
A
p
D
p
=
M
P
m=1
a
pm
|{z}
Bearbeitungszeit
+ t
pm
|{z}
Transportzeit
+ w
pm
|{z}
Wartezeit
Minimierung der Gesamt-Durchlaufzeit aller Auftr¨age
Min D =
P
P
p=1
M
P
m=1
(a
pm
+ t
pm
+ w
pm
)
Minimierung der mittleren Durchlaufzeit eines Auftrags
Min
D
P
Minimierung der mittleren Wartezeit eines Auftrags
Min
W
P
Minimierung der Zykluszeit
Min ma x{D
p
}
Minimierung der Gesamt-Termin¨uber schreitung aller Auftr¨age
v
p
= max {0, (F
p
L
p
)}
V =
P
P
p=1
v
p
=
P
P
p=1
max {0, (F
p
L
p
)}
223
34.4 Ressourcenbezogene Zielsetzungen
Bearbeitungs- und Leerzeiten
G =
P
X
p=1
M
X
m=1
a
pm
| {z }
Bearbeitungszeit B
+
M
X
m=1
l
m
| {z }
Leerzeit L
Maximierung der Auslastung
Max U =
B
G
Minimierung der Leerzeiten
Min L =
M
P
m=1
l
m
Zielwirkungen
Bestand
termingerechte Fertigstellung
Auslastung
34.5 Zielbeziehu ngen
Little’s Gesetz
W =
L
λ
224
osungsanatze der Reihenfolgeplanung
Problemtypen
Ankunftsprozeß statisch, Bearbeitungszeiten deterministisch
Ankunftsprozeß statisch, Bearbeitungszeiten stochastisch
Ankunftsprozeß dynamisch, Bearbeitungszeiten deterministisch
...
35 Reihenfolg eplanung ur ei ne Produktionsstufe
35.1 P Auftr¨age/ statische Situation/ mittlere Durchlaufzeit
P Auftr¨age/statische Situation/mittlere Durchlaufzeit
KOZ-Reih enfolge
a
[1]
a
[2]
··· a
[P ]
Zuf¨allige Reihenfolge (nach dem Auftragsindex)
mittlere DLZ = 10.17
2 4 6 8 10 12 14 16 18 20
Zeit
1
2
3
4
5
6
Auftragsposition
A 1
A 2W
A 3W
A 4W
A 5W
A 6W
KOZ-Regel
mittlere DLZ = 9.5
225
2 4 6 8 10 12 14 16 18 20 22
Zeit
1
2
3
4
5
6
Auftragsposition
A 2
A 3W
A 1W
A 5W
A 4W
A 6W
Gewichtung
a
[1]
w
[1]
a
[2]
w
[2]
···
a
[P ]
w
[P ]
35.2 P Auftr¨age/statische Situation/Maximale Versp¨atung
P Auftr¨age/statische Situation/Maximale Versp¨atung
Liefertermin-Regel Beispiel
Auftrag BearbeitungszeitAnkunftstermin Liefertermin
1 4 0 8
2 7 0 12
3 1 0 4
4 6 0 13
5 3 0 14
Liefertermin-Regel
2 4 6 8 10 12 14 16 18 20
Zeit
1
2
3
4
5
-----
4
5
Auftragsposition
A 3
A 1W
A 2W
A 4W
A 5W
Verspätungen der Aufträge
A4
A5
226
Verfahren von Hodgson (Moor e)
1. Start
Sortiere die Auftr¨age nach der Liefertermin-Regel und f¨uge sie in d ie
Menge R ein. Definiere eine Auftragsmenge J = {∅}, in der Auftr¨age
gesammelt werden, di e im Anschl an die Reihenfolge der kritischen
Auftr¨age betrachtet werden.
2. Bestimme den ersten versp¨ateten Auftrag
Eva luiere die Reihenfolge in der aktuel len Menge R und bestimme den
ersten versp¨ateten Auf trag A
α
in R. Gibt es keinen solchen Auftrag
A
α
, gehe zu Schritt 4.
3. Entfe rne einen Auftrag a us der Menge R
Betrachte die A u ftr¨a ge in der Menge R, die nicht nach dem Auftrag
A
α
beginn en und entferne den Auftrag A
β
mit der angsten Bear-
beitun gszeit aus der Meng e R und f¨uge ihn in die Menge J ein.
D. h. finde Auf trag A
β
mit t
β
= max
i=1,2,···
{t
i
}
Gehe zu Schritt 2.
4. Ende
Plane die Auftr¨age der Menge R nach der Liefertermin-Regel ein.
Danach plane die Auftr¨age der Menge J in einer beliebigen Rei h en-
folge ein.
Verfahren von Hodgson (Moor e)
osung
2 4 6 8 10 12 14 16 18 20
Zeit
1
2
3
4
5
-----
5
Auftragsposition
A 3
A 1W
A 4W
A 5W
A 2W
Verspätungen der Aufträge
A2
227
35.3 P Auftr¨age/dynamischer Auftragszugang/deterministische
Situation
P Auftr¨age/dynamischer Auftragszugang/deterministische Situation
Strategien
a) keine Verdr¨angung, keine geplanten Leerzeiten der Maschinen
b) keine Verdr¨angung, geplante Leerzeiten der Maschinen
c) Verdr¨angung, keine Wiederholung bereits erledigter Arbeiten
d) Verdr¨angung, Wiederholung bereits erledigter Arbeiten
KOZ-Regel, keine Verdr¨angung, kein Maschinenstillstand
1/1
1/1
1/1
A1
A3
A2
Arbeitsgang
123456789 10 11 12
KOZ-Regel, keine Verdr¨angung, geplanter Maschinenstillstand
1/1
1/1
1/1
L
A2
A3
A1
Arbeitsgang
1 2 3 4 5 6 7 8 9 10 11 12 13
KRB-Regel, Verdr¨angung
1/1
1/1
1/1
1/1
A1a
A2
A3
A1b
Arbeitsgang
1 2 3 4 56789 10 11 12
35.4 P Auftr¨age/dynamischer Auftragszugang/stochastische Sit-
uation
228
P Auftr¨age/dynamischer Auftragszugang/stochastische Situation
Durchlaufzeit ist Zufalls v ariable
a) stochastische Verdr¨angung
b) stochastische Bearbeitungszeiten der Auftr¨age in der Warteschlange
c) stochastische Bearbeitungszeit des aktuellen Auftrags
Priorit¨atsregeln
KOZ-Regel (K¨urzeste Operationszeitregel)
LOZ-Regel (L¨angste Operationszeitregel)
G RB-Regel (Gr¨oßte Restbearbeitungszeitregel)
KR B-Regel (K¨urzeste Restbearbeitungszeitregel)
Liefertermin-Regel
. . .
35.5 P Auftr¨age/statische Situation/reihenfolgeabh¨angige R¨ustzeiten
P Auftr¨age/statische Situation/reihenfolgeabh¨angige R¨ustzeiten
Beispiel aus der Schokoladenproduktion
i\j 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 33 33 34 481 33 33 481 481 33 0 33 34 481
2 32 0 5 34 481 4 5 481 481 6 32 0 34 481
3 32 2 0 34 481 4 5 481 481 0 32 3 34 481
4 32 33 33 0 481 33 33 481 481 33 32 33 0 481
5 32 33 33 34 0 33 33 2 3 33 32 33 34 0
6 32 7 5 34 481 0 0 481 481 6 32 8 34 481
7 32 7 5 34 481 0 0 481 481 6 32 8 34 481
8 32 33 33 34 3 33 33 0 3 33 32 33 34 4
9 32 33 33 34 3 33 33 5 0 33 32 33 34 4
10 3 2 2 0 34 481 4 5 481 481 0 32 3 34 481
11 0 33 33 34 481 33 33 481 481 33 0 33 34 481
12 3 2 0 5 34 481 4 5 481 481 6 32 0 34 481
13 3 2 33 33 0 481 33 33 481 481 33 32 33 0 481
14 3 2 33 33 34 0 33 33 2 3 33 32 33 34 0
36 Identische Bearbeitungsreihenfolgen (Flow sh op)
36.1 P Auftr¨age/2 Maschinen/Zykluszeit
229
P Auftr¨age/2 Maschinen/Zykluszeit
Verfahren von Johnson
F¨uge alle Auftr¨age in eine Liste ein.
ahle den Auftrag mit der k¨urzesten Bearbeitungszeit auf einer der beiden
Maschinen aus.
Wenn die k¨urzeste Bearbeitungszeit an Maschine 1 vorliegt, plane den Auftrag
so fr¨uh wie oglich ein.
Wenn die k¨urzeste Bearbeitungszeit an Maschine 2 vorliegt, plane den Auftrag
so sp¨at wie oglich ein.
Streiche den Auftrag aus der Liste.
Beispiel
I
A B C D E
M1 3 6 9 4 7
M2 2 3 8 6 4
Beispiel
II
1 2 3 4 5
- - - - 1
Beispiel
III
1 2 3 4 5
- - - - 1
- - - 2 1
Beispiel
IV
1 2 3 4 5
- - - - 1
- - - 2 1
4 - - 2 1
230
Beispiel
V
1 2 3 4 5
- - - - 1
- - - 2 1
4 - - 2 1
4 - 5 2 1
Beispiel
VI
1 2 3 4 5
- - - - 1
- - - 2 1
4 - - 2 1
4 - 5 2 1
4 3 5 2 1
Beispiel
osung
5 10 15 20 25 30
Zeit
M1
M2
Maschine
A-4 A-3 A-5 A-2 A-1
A-4 A-3 A-5 A-2 A-1
36.2 P Auftr¨age/2 Maschinen/Zykluszeit
P Auftr¨age/3 Maschinen/Zykluszeit
Erweiterung des Verfahrens von Johnson
Tra nsfor ma t ion in ein 2-Maschinen-Problem
231
M1 M2 M3
M1+M2 M2+M3
36.3 P Auftr¨age/M Maschinen/Zykluszeit
Heuristik von Campbell, Dudek und Smith
Trans f ormation in M 1 2-Maschinen-Problem
Maschine
Problem 1 2 3 4 5 6 7 8 9 10
1 1 10
2 1+ 2 9+ 10
3 1+ 2+ 3 8+ 9+ 10
4 1+ 2+ 3+ 4 7+ 8+ 9+ 10
5 1+ 2+ 3+ 4+ 5 6+ 7+ 8 + 9+ 10
6 1+ 2+ 3+ 4+ 5+ 6
5+ 6+ 7+ 8+ 9+ 10
7 1+ 2+ 3+ 4+ 5+ 6+ 7
4+ 5+ 6+ 7+ 8+ 9+ 10
8 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8
3+ 4+ 5+ 6+ 7+ 8+ 9+ 10
9 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9
2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10
NEH-Heuristik
1. Bestimme ur jeden Auftra g p die Summe der Bearbeitungszeiten an a llen Maschi-
nen
T
i
=
M
X
m=1
a
im
und sortiere die Auftr¨age absteigend nach diesem K r iterium.
2. Setze = 2. Nimm die Auftr¨age mit den angen 1 und 2 und bestimme die
Zykluszeit f¨ur die Reihenfolgen {1, 2} und {2, 1}. Fixiere die (partielle) R eihenfolge
mit der geringsten Z ykluszeit (makespan): π
= {π(1) , π(2)}
3. Setze = + 1.
Nimm den achsten Auftrag mit dem Rang und f¨uge ihn der Reihe nach in jede
Position der Reihenfolge π
1
(im vorhergehenden Schritt ermittelt) ein.
Bestimme f¨ur jede Reihenfolge die Zykluszeit und fixiere die (partielle) Reihenfolge
mit der k¨urzesten Zykluszeit.
232
4. Falls = P (Anzahl Auftr¨age) STOP; andernfalls gehe zu Schritt 3.
Literaturhinweis
Kalczynski and Kamburowski (2007)
233