Reihenfolgeproblem

Die Bearbeitung von n verschiedenen Produkten erfolgt in einer vom Produkt abhängigen Reihenfolge an m verschiedenen Maschinen. An jeder Maschine können nicht mehrere Produkte gleichzeitig bearbeitet werden. Zur Bearbeitung eines jeden Produktes wird an jeder Maschine eine vorgegebene Arbeitszeit benötigt. Im Produktionsablauf können dabei sowohl Wartezeiten, in denen auf Grund belegter Maschinen Produkte nicht bearbeitet werden können, als auch Maschinenstillstandszeiten auftreten.

Gesucht ist eine Reihenfolge der auf den einzelnen Maschinen nacheinander zu bearbeitenden Produkte, die je nach ökonomischer Zielsetzung die Gesamtdurchlaufzeit aller Produkte, die Gesamtwartezeit oder die Gesamtstillstandszeit aller Maschinen minimiert. Ein weiteres Ziel kann in der Minimierung der Gesamtdurchlaufzeit bestehen, wenn zusätzlich entweder keine Wartezeiten oder keine Stillstandszeiten nach der ersten Arbeitsaufnahme auftreten sollen.