Ein-Maschinen-Probleme sind in der Maschinenbelegungsplanung spezielle Modelle mit einer einzigen Maschine und n verschiedenen zu fertigenden Aufträgen. Obwohl die Modelle relativ einfach sind, verglichen mit Job-Shop-, Open-Shop- oder Flow-Shop-Problemen, gehören manche zu den NP-schweren Problemen.[1] Viele lassen sich jedoch in polynomialer Zeit lösen, also vergleichsweise schnell. Die Lösung der Modelle hängt von der angestrebten Zielsetzung ab. Beispiele sind die Minimierung der Zykluszeit, der Durchlaufzeit oder der Verspätungen. In der bei Maschinenbelegungsproblemen üblichen Notation handelt es sich um [1| | ]-Probleme. (Für Details zur Notation siehe Klassifikation von Maschinenbelegungsmodellen.) Die meisten Probleme lassen sich auch als Scheduling-Probleme in der Informatik betrachten: Die Maschine entspricht dann einem Prozessor und die Aufträge entsprechen den Prozessen. Analog lässt sich ein Maschinenbelegungsproblem mit parallelen Maschinen als Modell interpretieren mit mehreren Prozessoren.
- ↑ Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 307.