Ein Algorithmus für Flow-Shop-Scheduling

Beim Flow-Shop-Scheduling besteht das Problem darin, die Reihenfolge, in welcher eine Anzahl von Aufträgen eine Anzahl von Bearbeitungsstationen in jeweils gleicher vorgegebener technologischer Reihenfolge durchläuft, so festzulegen, daß die Gesamtbearbeitungsdauer möglichst minimal wird.
Ein Algorithmus zur Ermittlung einer optimalen Lösung für den Fall, daß die Anzahl der Bearbeitungsstationen und damit die Anzahl der Vorgänge je Auftrag gleich zwei beträgt, ist der Johnson-Algorithmus. Bei diesem Verfahren erhält man eine Reihenfolge, bei der Vorgänge mit einer kurzen Bearbeitungsdauer auf der ersten Station zuerst und auf der letzten Station zuletzt eingeplant werden. Bei dem hier vorgestellten Algorithmus wird versucht, die Aufträge ebenso anzuordnen, nur daß die Anzahl der Stationen hierbei größer als zwei sein kann. Um eine möglichst gute Belegung zu erhalten, wird für jeden Vorgang eines Auftrages ein Wahrscheinlichkeitswert ermittelt, der zwischen 0 und 1 liegt. Sollte der Auftrag zuerst bearbeitet werden, so entspricht das einem Wahrscheinlichkeitswert nahe 0. Sollte ein Auftrag dagegen zum Schluß bearbeitet werden, so wird ein Wert nahe 1 zugeordnet. Aus der Matrix der Wahrscheinlichkeitswerte läßt sich für jeden Auftrag ein mittlerer Wahrscheinlichkeitswert ermitteln. Die Festlegung der Auftragsreihenfolge erfolgt durch Sortieren der Aufträge entsprechend ihrer zugehörigen mittleren Wahrscheinlichkeitswerte, so daß der Auftrag mit dem kleinsten Wert zuerst und der Auftrag mit dem größten Wert zuletzt auf jeder Station bearbeitet wird.

Bedeutung der Symbole

I	Anzahl der Aufträge
J	Anzahl der Bearbeitungsstationen
d_ij	Bearbeitungsdauer von Auftrag i auf Station j
A_i	Gesamtbearbeitungsdauer des Auftrages i für alle Stationen
B_j	Gesamtbearbeitungsdauer aller Aufträge auf Station j
S_j	mittlere kumulierte Gesamtbearbeitungsdauer aller Aufträge bis Station j
D	Gesamtbearbeitungsdauer aller Aufträge auf allen Stationen
w_ij	Wahrscheinlichkeitswert für Auftrag i auf Station j
W_i	mittlerer Wahrscheinlichkeitswert für Auftrag i

Berechnung der Wahrscheinlichkeitswerte

Aus den gegebenen Bearbeitungsdauern d_ij ( i = 1...I , j = 1...J ) sind die Hilfsgrößen A_i , B_j , S_j und D folgendermaßen zu berechnen:

A_i = d_i1 + ... + d_iJ
B_j = d_1j + ... + d_Ij
S_j = B₁ + ... + B_j - ¹/₂ B_j
D = A₁ + ... + A_I = B₁ + ... + B_J

Die Wahrscheinlichkeitswerte sind definiert als reelle Zahlen im Intervall [ 0, 1 ]. Ein Wahrscheinlichkeitswert w_ij kann interpretiert werden als die Wahrscheinlichkeit, daß man eine gute Belegung erhält, wenn der Auftrag i auf der Station j zuletzt bearbeitet wird oder anders formuliert:
w_ij = 0 bedeutet: gute Belegung, wenn Auftrag i auf Station j zuerst bearbeitet wird
w_ij = 1 bedeutet: gute Belegung, wenn Auftrag i auf Station j zuletzt bearbeitet wird

Es gelten die folgenden Aussagen 1 und 2 (linearer Ansatz):

1.	Wenn	d_ij << A_i
	und	d_ij << B_j
	dann	w_ij = S_j/D

Interpretation: Vorgänge mit geringer Dauer möglichst auf erster Station zuerst und auf letzter Station zuletzt.

2.	Wenn	A_i - d_ij << A_i
	und	B_j - d_ij << B_j
	dann	w_ij = 1 - S_j/D

Interpretation: Vorgänge mit großer Dauer möglichst auf erster Station zuletzt und auf letzter Station zuerst.

3. Logische Verknüpfung von 1. und 2.

Bei einem bekannten Zusammenhang d₁ <=> w₁ und d₂ <=> w₂ erhält man mittels linearem Ansatz für den Zusammenhang zwischen w und d:

( w - w₁ ) / ( d - d₁ ) = (w₂ - w₁ ) / ( d₂ - d₁ )

Aus den Eckdaten der Aussagen 1 und 2 werden damit Aussagen für dazwischenliegende Daten abgeleitet.

4. Bei alleiniger Betrachtung des Auftrages i erhält man:

w_ij^A = S_j / D + ( D - 2 · S_j ) / D · d_ij / A_i

5. Bei alleiniger Betrachtung der Bearbeitungsstation j erhält man:

w_ij^B = S_j / D + ( D - 2 · S_j ) / D · d_ij / B_j

6. Logische Verknüpfung von 4. und 5.

Es gilt:
Wenn w_ij^A < w_ij^B dann w_ij^A < w_ij < w_ij^B
Wenn w_ij^A > w_ij^B dann w_ij^A > w_ij > w_ij^B
Wenn w_ij^A = w_ij^B dann w_ij^A = w_ij = w_ij^B

Mit linearem Ansatz erhält man für die Wahrscheinlichkeitswerte:

w_ij = ( w_ij^A + w_ij^B ) / 2

Man erhält damit eine I×J-Matrix der Wahrscheinlichkeitswerte. Man kann für jeden Auftrag einen mittleren Wahrscheinlichkeitswert berechnen mit

W_i^A = ( w_i1^A + ... + w_iJ^A ) / J

W_i^B = ( w_i1^B + ... + w_iJ^B ) / J

W_i = ( w_i1 + ... + w_iJ ) / J = ( W_i^A + W_i^B ) / 2

( linearer Ansatz ) und die Aufträge nach steigendem W_i sortieren. Man erhält damit eine Auftragsreihenfolge, bei der die Gesamtbearbeitungsdauer in der Regel nahe am Optimum liegt. Die so gefundene Reihenfolge kann als Ausgangslösung für Verbesserungsverfahren verwendet werden.

Beispiel

8 Aufträge (A1, ..., A8) sollen auf 4 Maschinen bearbeitet werden, jeder Auftrag zuerst auf M1, danach auf M2, auf M3 und zuletzt auf M4. Die Matrix der Bearbeitungsdauern d ist:

d	A1	A2	A3	A4	A5	A6	A7	A8
M1	1	3	5	3	4	2	6	2
M2	3	6	4	1	3	2	5	3
M3	2	4	5	5	2	3	3	6
M4	5	6	4	3	4	1	2	4

In welcher Reihenfolge müssen die Aufträge bearbeitet werden, damit die Gesamtbearbeitungsdauer möglichst minimal ist?
Die Reihenfolge nach steigender Nummer ( 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 ) ergibt eine Gesamtdauer von 42 Zeiteinheiten. Bei der Ermittlung der Reihenfolge durch Sortieren der Wahrscheinlichkeitswerte erhält man die Reihenfolge 1 - 8 - 2 - 4 - 5 - 3 - 6 - 7 (Gesamtdauer 37 Zeiteinheiten). Die einzelnen Rechenschritte sind dabei:

1. Berechnung der Hilfsgrößen:

j \ i	1	2	3	4	5	6	7	8	B_j	S_j
1	1	3	5	3	4	2	6	2	26	13
2	3	6	4	1	3	2	5	3	27	39,5
3	2	4	5	5	2	3	3	6	30	68
4	5	6	4	3	4	1	2	4	29	97,5
A_i	11	19	18	12	13	8	16	15	112	-

2. Berechnung der Matrix der w_ij^A - Werte

j \ i	1	2	3	4	5	6	7	8
1	0,186	0,237	0,329	0,308	0,352	0,308	0,404	0,218
2	0,433	0,446	0,418	0,377	0,421	0,426	0,445	0,412
3	0,568	0,562	0,548	0,518	0,574	0,527	0,567	0,521
4	0,534	0,637	0,706	0,685	0,643	0,778	0,778	0,673
W_i^A	0,430	0,470	0,500	0,472	0,497	0,510	0,548	0,456

3. Berechnung der Matrix der w_ij^B - Werte

j \ i	1	2	3	4	5	6	7	8
1	0,146	0,205	0,264	0,205	0,234	0,175	0,293	0,175
2	0,385	0,418	0,396	0,364	0,385	0,375	0,407	0,385
3	0,593	0,579	0,571	0,571	0,593	0,586	0,586	0,564
4	0,743	0,717	0,768	0,794	0,768	0,845	0,819	0,768
W_i^B	0,467	0,480	0,500	0,483	0,495	0,495	0,526	0,473

4. Berechnung des W_i - Vektors

i	1	2	3	4	5	6	7	8
W_i	0,448	0,475	0,500	0,478	0,496	0,502	0,537	0,465

5. Sortieren der Vektorkomponenten nach steigender Größe

i	1	8	2	4	5	3	6	7
W_i	0,448	0,465	0,475	0,478	0,496	0,500	0,502	0,537

Die mit dem Algorithmus für dieses Beispiel ermittelte Reihenfolge ist damit 1 - 8 - 2 - 4 - 5 - 3 - 6 - 7, die Maschinen werden dabei folgendermaßen von den Aufträgen belegt:

Maschine
   4       XXXXX  XXXXXXXXXXXXXXXXXXXXXXXX
   3     XX XXXXXXXXXXXXXXXXXXXXXXXXXXXX
   2  XXXXXXXXXXXXXXXX XXXXXX  XXXXX
   1 XXXXXXXXXXXXXXXXXXXXXXXXXX
  ---|----|----|----|----|----|----|----|----|--> Zeit
     0    5   10   15   20   25   30   35   40

(c) Lutz Tautenhahn 1995, 1999