Open Shop

Unter einem Open Shop versteht man in der Maschinenbelegungsplanung eine Klasse von Modellen, bei denen n {\textstyle n} Aufträge zu fertigen sind. Ein Auftrag besteht dabei aus g {\textstyle g} Arbeitsgängen, die auf den m {\textstyle m} Maschinen bearbeitet werden müssen. Dabei ist sowohl die Reihenfolge der Aufträge frei wählbar, als auch die Folge der einzelnen Arbeitsgänge und somit auch die Maschinenfolge. Es sind Modelle von Produktionssystemen mit flexiblem Fertigungssystem. Wenn die Folge der Arbeitsgänge für jeden Auftrag vorgegeben ist, ist es ein Job Shop, der eine Werkstattfertigung modelliert. Ist die Arbeitsgangfolge für jeden Auftrag auch noch identisch, ist es ein Flow Shop, der ein Modell der Fließproduktion darstellt. Ist nur eine Maschine vorhanden, ergibt sich ein Ein-Maschinen Problem. Bestehen die Aufträge aus nur einem Arbeitsgang, der auf einer von mehreren Maschinen zu bearbeiten ist, ist es ein Maschinenbelegungsproblem mit parallelen Maschinen. Im Gegensatz zu den Job Shop- und Flow Shop-Problemen, die seit Ende der 1950er Jahre ausgiebig untersucht wurden, werden die komplexeren Open Shop-Probleme erst seit Anfang der 80er Jahre untersucht. Die meisten Modelle sind NP-schwer. Den allgemeinen Fall mit zwei Maschinen untersuchten Teofilo F. Gonzalez und Sartaj Sahni bereits Mitte der 1970er Jahre und fanden einen Algorithmus, der in n {\textstyle n} Rechenschritten zu einem optimalen Ergebnis führt.