Wir sagen von uns, wir wendeten dieselbe Mathematik auf Touren und auf Fertigungsreihenfolgen an. Das ist keine Marketingformel, sondern steht so im Standardlehrbuch der Ablaufplanung – geschrieben von Michael Pinedo, dessen Buch zur Ablaufplanung an den meisten technischen Hochschulen im Regal steht.
Der Satz, um den es geht
Im Sammelband Elements of Scheduling schreibt Pinedo im Kapitel „Scheduling in Practice" ein Beispiel, das die Sache auf den Punkt bringt:
„Example 16.2 (A Routing Problem). Consider a warehouse with a single truck that has to bring merchandise to a number of clients. The delivery of merchandise to a client represents a job and the time that the truck spends at the client's site is the processing time. There may be release dates and due dates for the processing of that job… However, the time it takes the truck to travel from one client to another represent a form of sequence dependent setup time that cannot be disregarded."
Und unmittelbar danach:
„Another objective is to minimize the total time it takes the truck to do all its deliveries. This implies that the sum of the distances travelled (or, equivalently, the sum of the sequence dependent setups) has to be minimized. Such a problem is, of course, equivalent to the Travelling Salesman Problem."
Ein Kunde ist ein Auftrag. Die Standzeit ist die Bearbeitungszeit. Die Fahrzeit zwischen zwei Kunden ist eine reihenfolgeabhängige Rüstzeit. Damit ist die Tourenplanung ein Spezialfall der Maschinenbelegungsplanung – oder umgekehrt, je nachdem, aus welcher Richtung man kommt.
Dasselbe Buch formuliert es an anderer Stelle noch direkter: Man lasse reihenfolgeabhängige Rüst- und Umstellzeiten üblicherweise weg, denn „to do so would take us into the realm of the traveling salesman problem, which we now should like to avoid".
Wie alt diese Erkenntnis ist
Sie ist keine Neuigkeit. Gilmore und Gomory haben bereits 1964 ein Maschinenbelegungsproblem als Travelling Salesman Problem behandelt und dafür ein Lösungsverfahren angegeben. Picard und Queyranne haben 1978 die zeitabhängige Variante des TSP auf das Verspätungsproblem der Einmaschinenbelegung angewendet.
Der Grund für die Verwandtschaft ist strukturell: Beide Probleme suchen eine Reihenfolge, bei der die Kosten eines Schritts davon abhängen, was unmittelbar davor lag. Bei der Maschine ist es die Umrüstung von Produkt A auf Produkt B, beim Lkw die Fahrt von Kunde A zu Kunde B. Die Mathematik unterscheidet das nicht.
Wie schwer das Problem ist
Für die Fertigung gilt dieselbe unangenehme Nachricht wie für die Tourenplanung. Garey, Johnson und Sethi haben 1976 die Komplexität geklärt. Aus dem Abstract:
„determining a shortest-length schedule in an m-machine flowshop is NP-complete for m ≥ 3. (For m = 2, there is an efficient algorithm for finding such schedules.) […] the shortest-length schedule problem for an m-machine jobshop is NP-complete for every m ≥ 2."
Zwei Maschinen im Fließbetrieb: effizient lösbar – mit der Regel von Johnson aus dem Jahr 1954. Drei Maschinen: NP-vollständig. Werkstattfertigung: schon ab zwei Maschinen NP-vollständig.
Wie hart das praktisch ist, illustriert eine berühmte Testinstanz: das 10×10-Problem von Fisher und Thompson aus dem Jahr 1963 – zehn Aufträge, zehn Maschinen. Es blieb 26 Jahre ungelöst, bis Carlier und Pinson 1989 die Optimalität nachwiesen. Zwei Jahre später brauchten Applegate und Cook dafür weniger als sieben Minuten auf einer Workstation.
Zehn Aufträge, zehn Maschinen. Ein Umfang, den jede Fertigung täglich mehrfach plant.
Was Rüstzeitoptimierung bringt – die belegbare Zahl
Hier wird es dünn, und das sollte man offen sagen. Zu der Frage, welchen Anteil Rüstvorgänge an der Kapazität haben, kursieren viele Prozentzahlen; fast alle stammen von Softwareanbietern ohne benennbare Studie.
Die eine Angabe, die wir aus einer begutachteten Arbeit belegen können, stammt von Trovinger und Bohn (2005):
„As much as 50% of effective capacity can be lost to setups in printed circuit board assembly."
Und aus derselben Arbeit zum wirtschaftlichen Effekt:
„The economic value of setup reduction is rarely calculated. We estimate a reduction of key setup times by more than 80%, and direct benefits of $1.8 million per year. Total cost of the changes was approximately $350,000."
Wichtige Einschränkung: Die 50 Prozent gelten für die Leiterplattenbestückung, nicht für Fertigung allgemein. Der Satz „the economic value of setup reduction is rarely calculated" ist dabei fast die interessantere Aussage – er beschreibt genau die Lücke, die eine Planungsrechnung schließt.
Die einschlägigen Übersichtsarbeiten zum Thema stammen von Ali Allahverdi; die jüngste von 2015 wertet die Literatur bis dahin systematisch aus. Eine noch aktuellere Übersicht von 2025 hat über 2.100 Arbeiten aus den Jahren 1986 bis 2024 gesichtet.
Dokumentierte Fälle aus der Industrie
Wo es belastbare Zahlen gibt, stammen sie aus Anwendungsberichten in der Zeitschrift Interfaces beziehungsweise INFORMS Journal on Applied Analytics.
Dell ist der klarste Fall für Rüstzeitminimierung. Der Algorithmus plant Produktfamilien auf parallelen Kommissionierlinien so ein, dass die Zahl der Umrüstungen minimal wird:
„Dell was able to accommodate the twofold increase in product variety, as well as an effective production-volume increase of over 35 percent. Furthermore, Dell realized a conservative cost avoidance of more than $1 million annually"
Ohne die Lösung drohte dem Werk eine Verschlechterung der Produktionsrate um knapp 20 Prozent.
Volkswagen ist der beste europäische Beleg. Für die Kapazitätsplanung im Vorserienzentrum wurde ein binäres Optimierungsmodell entwickelt und als tabellenbasiertes Entscheidungssystem ausgerollt:
„the VPC estimated the annual cost savings to lie in the six-digit Euro range."
Und zur Qualität gegenüber der bisherigen Handplanung: „The schedules generated by the DSS were substantially better than the solutions generated by the current manual procedure, in terms of both accomplished manufacturing volume and planning effort."
Harris Semiconductor ist der größte dokumentierte Effekt: Die Termintreue stieg „from 75 to 95 percent without increasing inventories". Die Autoren schreiben, das System habe geholfen, den Geschäftsbereich von 75 Millionen Dollar Verlust zu über 40 Millionen Dollar Gewinn zu bringen – die Formulierung ist bewusst „helped move", nicht „caused".
Der ehrliche Gegenpol
Zur Glaubwürdigkeit gehört, auch die Gegenstimme zu nennen. Portougal und Robb haben 2000 einen Aufsatz mit dem Titel Production Scheduling Theory: Just Where Is It Applicable? veröffentlicht:
„A proliferation of scheduling research has done little to improve production planning practice… we show scheduling theory is relevant in few settings. For example, in increasingly common short-cycle environments, where production cycle times are shorter than the planning period, the order in which one processes jobs is seldom important… we call for caution in applying scheduling theory."
Das ist ein wichtiger Filter. Wenn Ihre Durchlaufzeit kürzer ist als Ihr Planungszeitraum, spielt die Reihenfolge kaum eine Rolle. Reihenfolgeoptimierung lohnt dort, wo Rüstvorgänge teuer sind, Engpassmaschinen existieren und Termine hart sind – nicht überall.
Woran Sie erkennen, ob es sich lohnt
Vier Indizien aus der Praxis:
- Die Rüstzeit hängt davon ab, was vorher lief. Farbwechsel, Temperaturwechsel, Reinigung zwischen Allergengruppen. Wenn jede Umrüstung gleich lang dauert, ist die Reihenfolge egal.
- Es gibt eine erkennbare Engpassmaschine. Dort entscheidet die Reihenfolge über den Durchsatz der gesamten Kette.
- Die Durchlaufzeit ist länger als der Planungszeitraum. Sonst greift der Einwand von Portougal und Robb.
- Die Planung hängt an einer Person. Dasselbe Muster wie in der Disposition – und dasselbe Risiko.
Wenn drei davon zutreffen, lohnt eine Rechnung. Es ist dieselbe Rechnung, die wir für Touren machen: Ist-Plan nachrechnen, optimiertes Szenario dagegenstellen, Delta ausweisen. Mehr dazu unter Produktionsplanung.
Der Transport zwischen den Stationen folgt einer anderen Logik als die Reihenfolge an der Maschine: Dort entscheidet nicht die Route, sondern der Takt – nachzulesen in Der Routenzug ist keine Tour.
Dieselben Verfahren in der Logistik erklärt der Leitfaden zur Tourenoptimierung – Reihenfolge unter Restriktionen ist in beiden Feldern dasselbe Problem. Wie eviit Reihenfolge- und Schichtplanung in der Fertigung angeht, steht auf der Seite Produktionsplanung.
Quellen
- Pinedo, M. L.: Scheduling in Practice, Kapitel 16 in Lenstra, J. K.; Shmoys, D. B. (Hrsg.), Elements of Scheduling, 2020. arXiv:2001.06005
- Johnson, S. M. (1954): Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1(1), S. 61–68. doi.org/10.1002/nav.3800010110
- Garey, M. R.; Johnson, D. S.; Sethi, R. (1976): The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research 1(2), S. 117–129. doi.org/10.1287/moor.1.2.117
- Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1979): Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Annals of Discrete Mathematics 5, S. 287–326. doi.org/10.1016/S0167-5060(08)70356-X
- Gilmore, P. C.; Gomory, R. E. (1964): Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research 12(5), S. 655–679. doi.org/10.1287/opre.12.5.655
- Carlier, J.; Pinson, E. (1989): An Algorithm for Solving the Job-Shop Problem. Management Science 35(2), S. 164–176. doi.org/10.1287/mnsc.35.2.164
- Trovinger, S. C.; Bohn, R. E. (2005): Setup Time Reduction for Electronics Assembly: Combining Simple (SMED) and IT-Based Methods. Production and Operations Management 14(2), S. 205–217. doi.org/10.1111/j.1937-5956.2005.tb00019.x
- Allahverdi, A. (2015): The third comprehensive survey on scheduling problems with setup times/costs. EJOR 246(2), S. 345–378. doi.org/10.1016/j.ejor.2015.04.004
- Loveland, J. L.; Monkman, S. K.; Morrice, D. J. (2007): Dell Uses a New Production-Scheduling Algorithm to Accommodate Increased Product Variety. Interfaces 37(3), S. 209–219. doi.org/10.1287/inte.1060.0264
- Weckenborg, C.; Kieckhäfer, K.; Spengler, T. S.; Bernstein, P. (2020): The Volkswagen Pre-Production Center Applies Operations Research to Optimize Capacity Scheduling. INFORMS Journal on Applied Analytics 50(2), S. 119–136. doi.org/10.1287/inte.2020.1029
- Leachman, R. C.; Benson, R. F.; Liu, C.; Raar, D. J. (1996): IMPReSS: An Automated Production-Planning and Delivery-Quotation System at Harris Corporation. Interfaces 26(1), S. 6–37. doi.org/10.1287/inte.26.1.6
- Portougal, V.; Robb, D. J. (2000): Production Scheduling Theory: Just Where Is It Applicable? Interfaces 30(6), S. 64–76. doi.org/10.1287/inte.30.6.64.11623