Maschinenbelegungsproblem mit parallelen Maschinen
# 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.^{: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:

$\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.^{: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.^{:342f.}$

### 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}$

## 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.^{: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}$

## 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.^{:354–361}$

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.

