Ablaufplanung bei Reihenproduktion (Flow-Shop)

Bei Reihenproduktion sind die Ressourcen dem Arbeitsplan der Produkte entsprechend angeordnet. Alle Produkte besuchen die Ressourcen in derselben Reihenfolge. Für die Bestimmung der Einlastungsreihenfolge der Aufträge gibt es verschiedene Verfahren, deren Anwendbarkeit u.a. von der Anzahl der Produktionsstufen abhängt.

Besonders bekannt ist das exakte Verfahren von Johnson, das die zykluszeitminimale Reihenfolge für N Aufträge an 2 Maschinen bestimmt. Ein weiteres Verfahren, das dieselbe Problemstellung wie das Verfahren von Johnson, allerdings für eine beliebige Anzahl von Maschinen, heuristisch löst, die die NEH-Heuristik.

1. Flowshop mit 2 Maschinen, N Aufträge, Ziel ist die Minimierung der Zykluszeit (makespan)

-> Algorithmus von Johnson

Zur Beschreibung des Verfahrens siehe Tempelmeier(2010), Aufgabe B3.6 Die folgenden mit dem Produktions-Management-Trainer erzeugten Bilder zeigen den Ablauf des Verfahrens.

a

a

2. Flowshop mit M Maschinen, N Aufträge, Ziel ist die Minimierung der Zykluszeit (makespan)

-> NEH-Heuristik

Hier wird wie folgt vorgegangen:

  1. Bestimme für jeden Auftrag $i$ die Summe der Bearbeitungszeiten an allen Maschinen

    $T_i =\sum_{m=1}^{M} a_{im}$

    und sortiere die Aufträge absteigend nach diesem Kriterium.
  2. Setze $\ell=2$. Nimm die Aufträge mit den Rängen $1$ und $2$ und bestimme die Zykluszeit für die Reihenfolgen $\{1,2\}$ und $\{2,1\}$. Fixiere die (partielle) Reihenfolge mit der geringsten Zykluszeit (makespan): $\pi^\ell=\{\pi(1),\pi(2)\}$
  3. Setze $\ell=\ell+1$. Nimm den nächsten Auftrag mit dem Rang $\ell$ und füge ihn der Reihe nach in jede Position der Reihenfolge $\pi^{\ell-1}$ (im vorhergehenden Schritt ermittelt) ein. Wenn die optimale Reihenfolge z.B. $4-3-5-2$ ist und man den Auftrag 1 einfügen will, dann erhält man:
    (1-4-3-5-2), (4-1-3-5-2), (4-3-1-5-2), (4-3-5-1-2), (4-3-5-2-1)
    Bestimme für jede Reihenfolge die Zykluszeit und fixiere die (partielle) Reihenfolge mit der kürzesten Zykluszeit.
  4. Falls $\ell=P$ (Anzahl Aufträge) STOP; andernfalls gehe zu Schritt 3.

Die Berechnung der Zykluszeit verlangt die Nachbildung des zeitlichen Produktionsablaufs und geht wie folgt, wobei die Indizes $i$ die aktuelle Reihenfolge beschreiben:

  1. Auftrag i kann an Maschine j erst beginnen, wenn er an Maschine j-1 beendet
    wurde:
    START(i,j) >= ENDE(i,j-1) alle i,j
  2. Maschine j kann mit Auftrag i erst beginnen, wenn der Auftrag i-1 auf dieser Stufe beendet
    wurde:
    START(i,j) >= ENDE(i-1,j) alle i,j
  3. Das Bearbeitungsende des Auftrags i auf Stufe j ergibt sich aus dem Bearbeitungsbeginn zuzüglich der Rüstzeit und der Bearbeitungszeit:
    ENDE(i,j) = START(i,j) + a(i,j) alle i,j
  4. F(0,j) = 0
  5. F(i,0) = 0

Beispiel

Daten

Auftrag
1
2
3
4
5
6
7
8
9
10
Maschine 1
4
1
5
2
5
1
3
3
2
4
Maschine 2
3
5
6
2
1
1
2
3
4
3
Maschine 3
4
1
5
2
5
1
3
3
2
4
Maschine 4
3
5
6
2
1
5
2
2
4
1

Vorbereitung:

Rang
Auftrag
$T_i$
1
3
22
2
1
14
3
2
12
4
5
12
5
9
12
6
10
12
7
8
11
8
7
10
9
4
8
10
6
8

$\ell=2$; Bestimmung der ersten Reihenfolge ; die Angaben in den Auftragsspalten sind die jeweiligen Endtermine ENDE(i,j) der Aufträge an den jeweiligen Machinen.

Akt. Reihenfolge
3
1
M-1
5
9
M-2
11
14
M-3
16
20
M-4
22
25
Akt. Reihenfolge
1
3
M-1
4
9
M-2
7
15
M-3
11
20
M-4
14
26
Optimale Reihenfolge:
3-1
Zykluszeit:
25

Gantt-Diagramm:

a

Iteration:
Auftrag 3 / 12
Akt. Reihenfolge
2
3
1
M-1
1
6
10
M-2
6
12
15
M-3
7
17
21
M-4
12
23
26
Akt. Reihenfolge
3
2
1
M-1
5
6
10
M-2
11
16
19
M-3
16
17
23
M-4
22
27
30
Akt. Reihenfolge
3
1
2
M-1
5
9
10
M-2
11
14
19
M-3
16
20
21
M-4
22
25
30
Optimale Reihenfolge:
2-3-1
Zykluszeit:
26

Gantt-Diagramm:

b
Iteration:
Auftrag 4 / 12
Akt. Reihenfolge
5
2
3
1
M-1
5
6
11
15
M-2
6
11
17
20
M-3
11
12
22
26
M-4
12
17
28
31
Akt. Reihenfolge
2
5
3
1
M-1
1
6
11
15
M-2
6
7
17
20
M-3
7
12
22
26
M-4
12
13
28
31
Akt. Reihenfolge
2
3
5
1
M-1
1
6
11
15
M-2
6
12
13
18
M-3
7
17
22
26
M-4
12
23
24
29
Akt. Reihenfolge
2
3
1
5
M-1
1
6
10
15
M-2
6
12
15
16
M-3
7
17
21
26
M-4
12
23
26
27
Optimale Reihenfolge:
2 - 3 - 1 - 5
Zykluszeit:
27

Gantt-Diagramm:

c
Iteration:
Auftrag 5 / 12
Akt. Reihenfolge
9
2
3
1
5
M-1
2
3
8
12
17
M-2
6
11
17
20
21
M-3
8
12
22
26
31
M-4
12
17
28
31
32
Akt. Reihenfolge
2
9
3
1
5
M-1
1
3
8
12
17
M-2
6
10
16
19
20
M-3
7
12
21
25
30
M-4
12
16
27
30
31
Akt. Reihenfolge
2
3
9
1
5
M-1
1
6
8
12
17
M-2
6
12
16
19
20
M-3
7
17
19
23
28
M-4
12
23
27
30
31
Akt. Reihenfolge
2
3
1
9
5
M-1
1
6
10
12
17
M-2
6
12
15
19
20
M-3
7
17
21
23
28
M-4
12
23
26
30
31
Akt. Reihenfolge
2
3
1
5
9
M-1
1
6
10
15
17
M-2
6
12
15
16
21
M-3
7
17
21
26
28
M-4
12
23
26
27
32
Optimale Reihenfolge:
2 - 9 - 3 - 1 - 5
Zykluszeit:
31

Gantt-Diagramm:

d

Die weiteren Iterationen (nur noch die Gantt-Diagramme):

e

f

g

h

i

Die optimale Reihenfolge ist damit 6-2-4-7-8-10-9-3-1-5 mit einer Zykluszeit von 42 Zeiteinheiten.

Siehe auch ...

Literatur

Günther, H.-O. und Tempelmeier, H. (2016). Produktion und Logistik - Supply Chain and Operations Management. 12. Aufl., Norderstedt: Books on Demand.
Tempelmeier, H. (2014), Produktionsplanung in Supply Chains. 2. Aufl., Norderstedt: Books on Demand.
Tempelmeier, H. (2010). Supply Chain Management und Produktion. 3. Aufl., Norderstedt: Books on Demand.