Ablaufplanung: Verfahren von Johnson

Bei dem von Johnson betrachteten Ablaufplanungsproblem handelt es sich um eine Reihenfertigung mit 2 Maschinen und beliebig vielen ($n$) Aufträgen. Jeder Auftrag wird zuerst an Maschine 1 und dann an Maschine 2 bearbeitet. Als Ziel wird die Minimierung der Zykluszeit verfolgt. Die Bearbeitungszeit des Auftrags $i$ auf Maschine $m$ betragt $t_{im}$ Zeiteinheiten. Johnson hat bewiesen, daß im optimalen Ablaufplan Folgendes gilt:

Auftrag $i$ wird vor Auftrag $j$ bearbeitet, wenn $\min\{t_{i1}, t_{j2}\} \leq \min\{t_{j1}, t_{i2}\}$

Hier werden die Bearbeitungszeiten zweier Aufträge auf den beiden Maschinen verglichen. Die linke Seite der Ungleichung gibt die Situationen an, an denen zuerst der Auftrag $i$ bearbeitet werden muß: wenn die Bearbeitungszeit von $i$ an Maschine 1 das Minimum darstellt (in diesem Fall wird $i$ so früh wie möglich bearbeitet) oder wenn die Bearbeitungszeit von $j$ an Maschine 2 das Minimum darstellt (in diesem Fall wird $j$ so spät wie möglich bearbeitet). Die rechte Seite der Ungleichung beschreibt die Situationen, an denen $j$ vor $i$ bearbeitet werden muß. Betrifft die kürzere Bearbeitungszeit eines Auftrags die zweite Maschine, dann wird der Auftrag so spät wie möglich eingeplant; betrifft die kürzere Bearbeitungszeit eines Auftrags die erste Maschine, dann wird der Auftrag so früh wie möglich eingeplant. Das hat zur Folge, daß die Wartezeiten der Aufträge vor Bearbeitungsbeginn und die Wartezeiten nach Bearbeitungsende minimal werden.

Das Johnson-Verfahren läuft wie folgt ab:

1. Füge alle Aufträge in eine Liste ein.
2. Falls die Liste leer ist, STOP. Wähle den Auftrag mit der kürzesten Bearbeitungszeit auf einer der beiden Maschinen aus.
3. Betrifft die kürzeste Bearbeitungszeit die Maschine 1, dann plane den Auftrag so weit wie möglich vorne ein, andernfalls plane den Auftrag so weit wie möglich hinten ein.
4. Entferne den aktuellen Auftrag aus der Liste und gehe zu Schritt 2.

Dieses Verfahren wird in diesem Modul eingesetzt.

Symbole:

Annahmen:

• $n$ zu bearbeitende Aufträge, zum Zeitpunkt 0 an der Maschine vorhanden (statische Auftragsankunft)
• 2 Maschinen
• deterministische Bearbeitungszeiten $t_{im}$
• gleiche Bearbeitungsreihenfolge für alle Aufträge (zuerst an Maschine 1 und dann an Maschine 2)
• keine Lagerkapazitätsbeschränkungen zwischen den beiden Maschinen

Während des Verfahrens werden die Auftragsnummern der Reihe nach in die Auftragsreihenfolge eingetragen.
Der sich ergebende Ablaufplan kann in Form eines Gantt-Diagramms dargestellt werden.

Ansichten:

Literatur:

Jaehn, F. und Pesch, E. (2014), Ablaufplanung - Einführung in Scheduling. Berlin (Springer)

Datenschutz | © 2021 POM Prof. Tempelmeier GmbH | Imprint