Maschinenbelegungsproblem mit parallelen Maschinen

Maschinenbelegungsprobleme mit parallelen Maschinen sind in der Maschinenbelegungsplanung spezielle Modelle mit mehreren parallel arbeitenden Maschinen einer einzigen Fertigungsstufe und n zu bearbeitenden Aufträgen. Die Aufträge können dabei in der Regel nur von einer Maschine gleichzeitig bearbeitet werden. Unterschieden wird dabei zwischen identischen parallelen (IP) Maschinen, uniformen parallelen (UP) Maschinen, bei denen sich die Bearbeitungszeiten der i-ten Maschine um einen Faktor p_i von einer Grundbearbeitungszeit unterscheiden, und heterogenen parallelen (HP) Maschinen, bei denen für jeden Arbeitsgang j und jede Maschine i die Bearbeitungszeiten t_ij verschieden sein können. (t_ij ist die Bearbeitungszeit von Auftrag j auf Maschine i) Es handelt sich also um die Probleme [IP| | ], [UP| | ] oder [HP| | ]. (Für Details zur Notation siehe Klassifikation von Maschinenbelegungsmodellen.) In der Informatik lassen sich die Modelle als Probleme mit mehreren Prozessoren betrachten. Die Maschinen entsprechen dann den Prozessoren und die Aufträge den Prozessen. Weitere Typen von Maschinenbelegungsproblemen sind Job-Shop-, Flow-Shop-, Open-Shop-Probleme oder Maschinenbelegungsproblem mit einer Maschine. Probleme mit mehreren Fertigungsstufen und parallelen Maschinen sind spezielle Flow Shop-Probleme, sogenannte hybride oder flexible Flow Shops.

Identische Maschinen

Minimierung der Zykluszeit

Besonders einfach ist das Problem [IP|pmnt|Z] zu lösen, bei dem neben den $n$ unterbrechbaren ($pmnt$) Aufträgen, $m$ Maschinen vorhanden sind und die Zykluszeit $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.

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

$\min Z$

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

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

$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.

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.

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).

Uniforme Maschinen

Uniforme Maschinen unterscheiden sich ausschließlich durch unterschiedliche Produktionsgeschwindigkeiten. Die Bearbeitungszeiten t_ij unterscheiden sich also für verschiedene Maschinen i nur um einen Faktor p_i.

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.

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.

Heterogene Maschinen

Bei heterogenen Maschinen liegen Bearbeitungszeiten t_ij vor, die für jede Maschine und jeden Auftrag unterschiedlich sein können. Die Probleme sind fast immer NP-schwer.

Das Problem [HP|pmnt|Z] lässt sich lösen, indem man zunächst mit einem linearen Gleichungssystem die optimale Zykluszeit bestimmt. Anschließend verteilt man die Aufträge mit der Umbruchmethode auf die Maschinen, wie bei [IP|pmnt|Z].

[HP| |D] lässt sich mit polynomiellem Aufwand lösen, indem man es als Transportproblem formuliert. Die Aufträge entsprechen dann den Anbietern mit Angebotsmenge 1 (jeder Auftrag ist genau einmal auszuführen). Die Maschinen treten jeweils n-mal als Nachfrager auf.

Siehe auch

• Unternehmensforschung (Operations Research)
• Losgröße
• Fließbandabstimmung
• Betriebsmittel
• Werkzeugmaschine
• Produktionsplanung und -steuerung
• Arbeitsvorbereitung
• Produktionstechnik

Literatur

• Blazewicz, Ecker, Pesch, Schmidt, Weglarz: Handbook on Scheduling, Springer, 2007, S. 137–199. (Kapitel "Scheduling on parallel Processors")
• Jaehn, Pesch: Ablaufplanung, Springer, 2014, S. 51–71 (Kapitel "Modelle mit parallelen Maschinen")
• Brucker: Scheduling Algorithms, Springer, 2007, 5. Auflage, S. 107–155 (Kapitel "Parallel Machines")
• Pinedo: Scheduling, Springer, 4. Auflage, 2012, S. 111–150 (Kapitel "Parallel Machine Models (Deterministic)), S. 295-320 (Kapitel "Parallel Machine Models (Stochastik))