Minimierung der Zykluszeit

Besonders einfach ist das Problem [IP|pmnt|Z] zu lösen, bei dem neben den ${\displaystyle n}$ unterbrechbaren (${\displaystyle pmnt}$) Aufträgen, ${\displaystyle m}$ Maschinen vorhanden sind und die Zykluszeit ${\displaystyle Z}$ minimiert werden soll, also die Zeit vom Beginn der Bearbeitung des ersten Auftrags bis zum Ende des letzten Auftrags. Wenn mindestens so viele Maschinen wie Aufträge vorhanden sind, wird jeder Auftrag sofort bearbeitet und die Zykluszeit entspricht der längsten Bearbeitungszeit t_max. Wenn weniger Maschinen vorhanden sind, gilt für die optimale Zykluszeit Z=t_sum/m mit t_sum als Summe der einzelnen Bearbeitungszeiten. Eine Maschinenbelegung ergibt sich, indem man die erste Maschine mit Aufträgen belegt, bis die gesamte Bearbeitungszeit genau gleich der optimalen Zykluszeit ist. (Da die Aufträge unterbrechbar sind, ist eine solche Belegung immer möglich. Ein unterbrochener Auftrag wird dann auf einer anderen Maschine weiterbearbeitet.) Danach wiederholt man das Verfahren, bis alle Aufträge eingeplant sind. Dieses Verfahren wird auch als Umbruchmethode bezeichnet.^:335

Das Problem [IP| |Z], ohne unterbrechbare Aufträge gehört bereits zur Klasse der NP-schweren Probleme. Es lässt sich wie folgt formulieren:

${\displaystyle \min Z}$

${\displaystyle \sum _{i=1}^{m}x_{ij}=1}$

${\displaystyle \sum _{j=1}^{n}t_{j}x_{ij}\leqq Z}$

${\displaystyle x_{ij}\in \lbrace 0,1\rbrace }$

Ignoriert man die letzte Zeile, so erhält man das Problem [IP|pmnt|Z], dessen Lösung somit als Abschätzung dienen kann. Eine Heuristik zur Lösung besteht darin, die Aufträge nach monoton fallenden Bearbeitungszeiten zu sortieren. Anschließend plant man die Aufträge in dieser Reihenfolge auf der Maschine ein, die am wenigsten belegt ist. Exakte Lösungen sind mit der dynamischen Programmierung oder Branch-and-Bound-Algorithmen möglich.^:338–342

Bei [IP|in-tree,t_j=1|Z] haben alle Aufträge die gleiche Bearbeitungszeit und es liegt ein Vorranggraph in Form eines Baumes vor, mit nur einem einzigen zu fertigenden Endprodukt und mehreren Zwischenprodukten. Es lässt sich mit dem sogenannten Highest Level First-Verfahren lösen, bei dem man dem Auftrag j einen Rangwert zuweist, der der Anzahl der Pfeile entspricht, die von j nach n zeigen, und dann die Aufträge nach fallenden Rangwerten einplant. Liegt ein Vorranggraph in Form eines Waldes vor, also mehrerer unverbundener Bäume, so kann man die Endprodukte mit einem zusätzlichen (fiktiven) Knoten verbinden und erhält wieder einen Baum. Bei [IP|out-tree,t_j=1|Z] liegt ebenfalls ein Vorranggraph in Form eines Baumes vor, bei dem jedoch aus einem einzigen Ausgangsprodukt mehrere Zwischen- und Endprodukte hergestellt werden. Es lässt sich analog lösen, wenn man als Rangwert die Anzahl der Pfeile im längsten Weg von j zu einem Endprodukt wählt.^:342 f.

Minimierung der Durchlaufzeit

Bei [IP| |D] möchte man die Durchlaufzeit minimieren. Dazu belegt man die Maschine mit der geringsten Belegung mit dem Auftrag der die kürzeste Bearbeitungszeit aufweist (Kürzeste Operationszeit-Regel / Shortest Processing Time-Regel).^:343

Minimierung der Zykluszeit

Das allgemeine Problem [UP| |Z] ist NP-schwer. Man löst es durch Modifikation der Lösungsverfahren von [IP| |Z]. Als Heuristik sortiert man wieder die Aufträge nach fallenden Bearbeitungszeiten. Zur Entscheidung, auf welche Maschine die Aufträge dann eingeplant werden sollen, stehen zwei Alternativen zur Verfügung:

• a) Die Maschine, die den Auftrag zum momentanen Planungszeitpunkt am frühesten fertigstellen würde.
• b) Die Maschine mit der geringsten Belegungszeit.

Liefert eine Regel keine eindeutige Entscheidung, so wählt man die andere Regel. Liefert diese ebenfalls keine eindeutige Entscheidung, so wählt man diejenige Maschine mit kleinstem i.^:352

Das Problem [UP|t_j=1|Z] lässt sich in polynomieller Zeit lösen, indem man es als Transportproblem formuliert und die speziellen dafür geeigneten Algorithmen anwendet. Die Aufträge entsprechen dabei den Anbietern und jede Kombination aus Auftrag und Maschine entspricht einem Nachfrager. Die Transportkosten c_kij entsprechen den Fertigstellungszeitpunkten, wenn Auftrag j als k-ter Auftrag auf Maschine i gefertigt wird.

Minimierung der Durchlaufzeit

[UP| |D] lässt sich ähnlich wie [IP| |Z] lösen. Ein Verfahren ist der Algorithmus von Horowitz und Sahni.^{:353:317–327}