Inhaltsübersicht I. Aufgabenstellung der Ablaufplanung bei Einzel- und Serienfertigung II. Modellierung von Ablaufplanungsproblemen III. Problematik der Lösung von Ablaufplanungsproblemen I. Aufgabenstellung der Ablaufplanung bei Einzel- und Serienfertigung In der Ablaufplanung geht es um die Reihenfolge von Teilprozessen eines Gesamtgeschehens, etwa eines Produktionsprozesses, sowohl in zeitlicher als auch in räumlicher Hinsicht. Damit handelt es sich um eine zentrale Frage der Ablauforganisation (Schweitzer, M. 1974; Küpper, H. -U. 1981). In typischer Form tritt sie im industriellen Fertigungsbereich auf. Andere Anwendungsgebiete mit analogen Ablaufplanungsproblemen sind etwa Verwaltungsprozesse, Transport- und Übermittlungsprozesse, Informationsverarbeitungsprozesse, die internen Verarbeitungsprozesse in Rechenmaschinen sowie die Stundenplangestaltung. Ausgangspunkt der Ablaufplanung ist in jedem Fall eine zu vollbringende Gesamtaufgabe. Soweit ihre Erfüllung noch nicht in Teilarbeiten (Arbeitsgänge) zerlegt ist, geschieht dies in einer produktbezogenen Ablaufplanung (Troßmann, E. 1986). Sie gehört zur Arbeitsplanung  (und CAP). Aufgabe der periodenbezogenen Ablaufplanung, mit der sich dieser Beitrag beschäftigt, ist es, für die Arbeitsgänge an definierten Aufträgen auf den verschiedenen Bearbeitungsstellen eine zeitliche und räumliche Reihenfolge so zu finden, dass bestehende Zielvorstellungen bestmöglich erfüllt werden. Dies wird vielfach als Ablaufplanung i.e.S. angesehen. Sie setzt die Bildung von Aufträgen voraus. Ein Auftrag gibt an, in welcher Menge bzw. Häufigkeit welche Produkte bereitzustellen sind. Soweit es sich nicht um Einzel- oder Massenfertigung handelt, ist dies mit der Bildung von Fertigungslosen verbunden. Sowohl in der Auftragsbildung als auch in der produktbezogenen Ablaufplanung werden nicht nur technisch erzwungene Bedingungen aufgestellt, sondern Vorentscheidungen in einer Kette sukzessiver Teilplanungen getroffen. Ihre separierte Lösung ist zwar in der Praxis üblich, insb. eine isolierte Losbildung kann aber zielungünstig sein (vgl. zur neueren Diskussion z.B. MacCarthy, B. L./Liu, J. 1993; Drexl, A./Fleischmann, B./Günther, H. -O. et al. 1994). Die Ablaufplanungsproblematik hängt grundlegend vom Programmtyp ab. In der Ablaufplanung bei Massenproduktion und Großserienfertigung dominiert eher die produktbezogene gegenüber der periodenbezogenen Ablaufplanung. Bei der Einzel- und Kleinserienfertigung dagegen ist typischerweise für mehrere Aufträge einer Planungsperiode ein gemeinsamer Ablauf zu finden. Die Serienfertigung eröffnet durch eine stückweise Losbearbeitung zusätzliche Möglichkeiten der Ablaufplanung: Die Losbearbeitung kann zugunsten eines anderen Auftrags unterbrochen werden, mit Teillosen können auch kleine Auslastungslücken genutzt oder die Auftragsbearbeitung auf Parallelstellen verteilt werden. Falls dagegen jedes Los zusammenhängend zu produzieren ist, besteht in der Ablaufplanung kein Unterschied mehr zur Einzelfertigung. II. Modellierung von Ablaufplanungsproblemen 1. Ziele der Ablaufplanung Eine optimale Gestaltung eines Ablaufplans setzt in jedem Fall Beziehungen zwischen den ablaufplanerischen Handlungsvariablen und den relevanten Zielgrößen voraus. Die Ablaufplanung als Teil der Produktions- und damit der Gesamtunternehmungsplanung hat ihre Ziele aus dem betrieblichen Zielsystem abzuleiten. Soweit auf Unternehmungsebene ein bestimmter finanzieller Überschuss angestrebt wird, muss z.B. die Deckungsbeitragswirkung von Reihenfolge-Alternativen oder bestimmten disponiblen Ergebnisparametern der Ablaufplanung bekannt sein. Beispiele ablauforganisatorischer Ergebnisparameter sind etwa die geplanten Fertigstellungstermine der Aufträge, ihre Durchlaufzeiten, die Belegungszeiten der Maschinen oder die Umrüstungshäufigkeit. Sie sind somit eigentlich nur Bezugsgrößen für Produktionskosten und -leistungen und die sonstige Zielberechnung. Dennoch zieht man sie bislang i.d.R. unmittelbar als ablauforganisatorische Zielgrößen heran. Entscheidungslogisch erhalten sie damit die Funktion von Zwischenzielgrößen. Abb. 1 zeigt eine typische Auswahl. Mit ihnen lassen sich mehrere, im Einzelnen unterschiedliche Ziele formulieren, die stärker sachorientiert sind. Abb. 1: Beispiele unmittelbar ablaufbezogener Zielinhalte In der wissenschaftlichen Diskussion hat man sich mit dem skizzierten hierarchischen Zielverhältnis bisher weniger beschäftigt als mit den Beziehungen von Ablaufplanungszielen untereinander. Hier sind definitionslogische und empirische Zielbeziehungen zu unterscheiden. Für typische Ablaufplanungsziele werden im Folgenden definitionslogische Zusammenhänge aufgeführt. Vorausgesetzt werden reihenfolgeunabhängige Bearbeitungs- und Rüstzeiten sowie gegebene Soll-Fertigstellungstermine der Aufträge. Dann sind die folgenden auftragsbezogenen Ziele äquivalent (vgl. hierzu und zu weiteren Beziehungen z.B. Rinnooy Kan, A.H. G. 1976): 1. Minimierung der Durchlaufzeitensumme aller Aufträge, 2. Minimierung der durchschnittlichen Durchlaufzeit, 3. Minimierung der Summe der Fertigstellungstermine aller Aufträge, 4. Minimierung des durchschnittlichen Fertigstellungstermins, 5. Minimierung der Summe aller ablaufbedingten Auftragswartezeiten (vor der nächsten Bearbeitungsstelle), 6. Minimierung der durchschnittlichen ablaufbedingten Auftragswartezeit, 7. Minimierung der Summe aller Terminabweichungen (Verspätungen und Verfrühungen) der Aufträge, 8. Minimierung der durchschnittlichen Terminabweichung. Bei den arbeitsträgerbezogenen Zielen sind äquivalent: 1. Minimierung der Zykluszeit der Aufträge, d.h. der Gesamtzeit für den Durchlauf aller Aufträge (makespan), 2. Minimierung der Gesamtbelegungszeit der Stellen, 3. Minimierung der Summe zyklusbezogener Leerzeiten aller Bearbeitungsstellen, 4. Minimierung der Summe beliebig stellengewichteter zyklusbezogener Leerzeiten aller Bearbeitungsstellen (damit auch der einfache Durchschnitt), 5. Maximierung des Kapazitätsauslastungsgrades als Verhältnis der Bearbeitungszeitensumme zur Gesamtbelegungszeit, 6. Maximierung der durchschnittlichen Anzahl von in Bearbeitung befindlichen Aufträgen. Schwieriger als definitionslogische sind empirische Zielbeziehungen zu untersuchen. Hier gab es ab den 1950er-Jahren über lange Zeit eine intensive Diskussion. Ausgangspunkt war eine Überlegung von E. Gutenberg zu den Zielen Minimierung der Durchlaufzeit und Maximierung der Kapazitätsauslastung, die er als die beiden wichtigsten Ziele der Ablaufplanung ansah. Zwischen ihnen ging er von einem konfliktären Verhältnis aus, das er »Dilemma der Ablaufplanung« nannte. Verschiedene Simulationsuntersuchungen, die dazu in späteren Jahren durchgeführt wurden, konnten weder das behauptete Dilemma noch eine Zielverträglichkeit generell nachweisen (einen Überblick dazu gibt Küpper, H. -U. 1981). Im Hinblick auf die zahlreichen Möglichkeiten, inhaltlich verschiedene Ziele der Ablaufplanung zu formulieren, ist jedoch allg. nicht nur von einem potenziellen Di- oder Trilemma der Ablaufplanung (Mensch, G. 1972), sondern von einem Polylemma (Schweitzer, M. 1967) auszugehen. Inwieweit die für einen bestimmten Anwendungsfall nachgewiesene Möglichkeit von Zielkonflikten die konkrete Ablaufplanung tatsächlich erschwert, hängt letztlich davon ab, welche der beteiligten Ablaufplanungsziele überhaupt geeignete Unterziele im verfolgten Zielsystem sind. 2. Klassifikation von Problemtypen und Modellen der Ablaufplanung So vielfältig wie der Anwendungsbereich der Ablaufplanung sind auch ihre Problemstellungen im Einzelnen. Einen grundsätzlichen Überblick, der nur die Haupteinteilungskriterien berücksichtigt, vermittelt Abb. 2. Für die Bearbeitungsstellen ist dort im Anschluss an die Literatur die weniger allg. Bezeichnung Maschinen gewählt. Grundsätzlich ist zwischen funktionsgleichen (parallelen) und funktionsverschiedenen Maschinen zu unterscheiden. Parallele Maschinen können technisch die gleichen (zumindest sich entsprechende) Arbeitsgänge vollbringen. Für die Ablaufplanung ist wichtig, ob bei allen Aufträgen die Arbeitsgang-Zeiten unabhängig von der gewählten Maschine sind (»identische parallele Maschinen«) oder bei jeder Maschine verschieden sein können (»heterogene (unrelated) parallele Maschinen«). Ein besonders in der internen Maschinensteuerung von Computern wichtiger Sonderfall besteht darin, dass die Verhältnisse der Bearbeitungszeiten auf allen Maschinen gleich sind, jede Maschine jedoch unterschiedlich »schnell« ist (»uniforme parallele Maschinen«). Im Falle verschiedener Maschinen führen im herkömmlich betrachteten Standardfall alle jeweils einen Arbeitsgang aus. Demgegenüber sind flexible Fertigungstechniken dadurch gekennzeichnet, dass die einzelnen Anlagenkomponenten mehrere, teils gleiche, teils verschiedene Funktionen erfüllen können. In diesem Sinne ersetzen, überlappen bzw. ergänzen sie sich. Abb. 2: Klassifikation von Problemen der Fertigungsablaufplanung Zur Kennzeichnung der auszuführenden Arbeit kann man nach den Merkmalen der Aufträge einerseits sowie denen der Arbeitsgänge in einem Auftrag andererseits unterscheiden. Für die ablaufplanerische Aufgabenstellung grundlegend ist, welche Bedingungen für die Reihenfolge der Arbeitsgänge einzuhalten sind. Beim Flow-Shop-Problem muss sie bei allen Aufträgen gleich sein; kombiniert mit verschiedenen Einfunktionsmaschinen ist dies in der klassischen Reihenfertigung tatsächlich der Fall. Das der Werkstattfertigung entsprechende Job-Shop-Problem geht ebenfalls von vorgegebenen Gangfolgen aus, sie sind aber i.A. für jeden Auftrag verschieden. Beim Open-Shop-Problem schließlich sind keinerlei Gangfolge-Bedingungen einzuhalten. Der Vielzahl möglicher Problemtypen, die sich aus der Kombination von Merkmalen der Abb. 2 ergeben, entspricht eine unübersehbare Anzahl formaler Modelle, die für die Ablaufplanung inzwischen entwickelt wurden. Die Übersichtsliteratur gliedert sie i.d.R. in folgende Gruppen, die gleichzeitig die Hauptunterschiede im Modellaufbau kennzeichnen (vgl. z.B. French, S. 1982; Blazewicz, J./Ecker, K./Schmidt, G. et al. 1993; Domschke, W./Scholl, A./Voß, S. 1993): - Einzel-Maschinen-Probleme, - Probleme mit mehreren parallelen Maschinen und Aufträgen mit je nur einem Arbeitsgang (»parallel machine scheduling«) - Flow-Shop-Probleme, - Job-Shop-Probleme, - Open-Shop-Probleme, - Sonderprobleme, etwa Probleme mit zusätzlichen Kapazitätsbeschränkungen (»ressource constrained scheduling«) oder die Ablaufplanung bei flexiblen Fertigungssystemen. Ein weiteres generelles Ordnungsprinzip für Ablaufplanungsmodelle ist durch die Zielvorstellung gegeben, die die Modellstruktur und Lösungsverfahren deutlich beeinflusst. Zur Klassifikation der Modelle wird häufig eine Notation mit drei Hauptkomponenten (α|β|γ) verwendet, die in je nach Autor verschiedene, jedoch immer zahlreiche Unterkomponenten gegliedert wird (vgl. ursprünglich Conway, R. W./Maxwell, W. L./Miller, L. W. 1967; Rinnooy Kan, A.H. G. 1976; Graham, R. L./Lawler, E. L./Lenstra, J. K. et al. 1979): - α für die Art und Zahl der im Modell zugelassenen Maschinen, - β für die Zahl der im Modell zugelassenen Aufträge und der vorausgesetzten bzw. berücksichtigten Bedingungen der Aufträge und ihrer Arbeitsgänge, - γ für die Zielvorstellungen. 3. Methoden der Ablaufplanung Verschiedene Modellierungen erlauben es, Ablaufprobleme präzise zu fassen; ihre Lösbarkeit bestimmt sich jedoch nach den einsetzbaren Methoden. Zunächst ist zwischen bloßen Darstellungsmethoden und eigentlichen Lösungsmethoden zu unterscheiden. Zu den grafischen Darstellungsmethoden der Ablaufplanung zählen Gantt-Diagramme und Ablaufgrafen. Gantt-Diagramme (vgl. Abb. 3) dienen der Abbildung eines fertigen Ablaufplans. Demgegenüber können mit Ablaufgrafen auch Reihenfolgealternativen und -bedingungen abgebildet werden. Hiervon sind mehrere äußerlich verschiedene Formen denkbar. Sie unterscheiden sich darin, ob Arbeitsgänge als Knoten oder Kanten dargestellt werden. Ferner können die Knoten nach den Aufträgen, ihren Arbeitsgängen oder den Maschinen zeichnerisch horizontal oder vertikal geordnet sein. Ein Beispiel zeigt Abb. 4. Abb. 3: Gantt-Diagramme zu einem Ablaufplan für vier Aufträge auf drei Maschinen Abb. 4: Darstellung eines Job-Shop-Problems als disjunktiver Graf Die vorgegebenen Arbeitsfolgen sind mit den durchgehenden Kanten dargestellt, die zu planenden Maschinenbelegungen mit unterbrochenen. Letztere haben zwei Pfeilspitzen, von denen je eine für einen gültigen und vollständigen Ablaufplan auszuwählen ist. Diese Darstellungsform als disjunktiver Graf (Balas, E. 1969) führt weiter zu einer grafentheoretischen Umformulierung des dargestellten Job-Shop-Problems: Bewertet man Knoten bzw. Kanten mit den jeweiligen Bearbeitungs- bzw. Umrüstzeiten, dann gibt für jede Wahl der disjunktiven Pfeile ein längster Weg zwischen Anfangs- und Endknoten die längste Gesamtzeit der Auftragserfüllung an. Grafentheoretisch ist das Problem der Zykluszeitminimierung in diesem Fall damit als Suche nach derjenigen Wahl der disjunktiven Pfeile zu interpretieren, die den längsten Weg minimiert. Eine grafentheoretische Konstruktion einer solchen Pfeilauswahl ist damit freilich noch nicht gegeben. Für eine exakte Optimierung kommen zunächst prinzipiell zahlreiche OR-Methoden infrage. Tatsächlich aber sind die meisten der bekannten Ablaufplanungsmodelle auf eine Anwendung einer der folgenden Lösungsmethoden konzipiert: - konstruktive Methoden; - Verfahren der (gemischt-)ganzzahligen bzw. binären linearen Planungsrechnung; - Entscheidungsbaumverfahren als dynamische Planungsrechnung, begrenzte Enumeration oder Branch-and-Bound-Methoden. Konstruktive Methoden bauen unmittelbar die gesuchte Reihenfolge auf. Sie nutzen dazu spezielle Eigenschaften des Problems. Für ganze Problemklassen kann dies daher nur in ganz wenigen, eher einfachen Fällen gelingen. Mehrere solcher Ordnungsregeln sind seit langem bekannt. Grundlegend sind folgende Beispiele (z.B. Rinnooy Kan, A.H. G. 1976; French, S. 1982; MacCarthy, B. L./Liu, J. 1993; Domschke, W./Scholl, A./Voß, S. 1993): - Um die mittlere Durchlaufzeit auf einer Maschine zu minimieren, ordnet man sie nach steigenden Bearbeitungszeiten: Regel der kürzesten Operationszeit (KOZ), SPT (= Shortest-Processing-Time)-Regel (Smith, W. E. 1956; Conway, R. W./Maxwell, W. L./Miller, L. W. 1967). - Um die maximale Verspätung von n Aufträgen auf einer Maschine zu minimieren, ordnet man nach frühesten zugesagten Lieferterminen: EDD (= Earliest-Due-Date)-Regel oder Jackson\'s Regel (Jackson, J. R. 1955). Eine Erweiterung für einen Unterfall stammt von Smith (Smith, W. E. 1956), der die optimale Reihenfolge von hinten her aufbaut. - Für die Minimierung der maximalen Terminabweichung und allgemeinere Zielsetzungen bei Ein-Maschinen-Problemen unter zusätzlichen Auftragsreihenfolge-Bedingungen baut ein Algorithmus von Lawler (Lawler, E. L. 1973) eine optimale Reihenfolge auf. Modifikationen zur Erfassung zusätzlicher Bedingungen stammen z.B. von Baker/Nuttle und Glazebrook (Baker, K. R./Nuttle, H. L. 1980; Glazebrook, K. D. 1980). - Zur Minimierung der Anzahl verspäteter Aufträge beim Ein-Maschinen-Problem dient der Algorithmus von Moore/Hodgson (Moore, J. M. 1968). Erweiterungen berücksichtigen die Forderung nach Fertigstellungsreihenfolge in der Ordnung der zugesagten Termine (Kise, H./Ibaraki, T./Mine, H. 1978) oder die Bevorzugung bevorrechtigter Aufträge (Sidney, J. B. 1977). - Für das Flow-Shop-Problem von n gleichzeitig freigegebenen Aufträgen auf zwei Maschinen stammt der grundlegende Algorithmus zur Zykluszeitminimierung von Johnson (Johnson, S. M. 1954). Hierzu gibt es mehrere Modifikationen und Erweiterungen insb. zum Problem bei drei und mehr Maschinen (z.B. Kusiak, A. 1986; Chow, W. S. 1989). Für verschiedene Sonderfälle haben insb. Panwalkar/Woollam (Panwalkar, S. S./Woollam, C. R. 1980) konstruktive Algorithmen angegeben. - Ein konstruktives Verfahren für die Zykluszeitminimierung eines Open-Shop-Problems mit zwei Maschinen schlagen Gonzalez/Sahni (Gonzalez, T./Sahni, S. 1976) vor. Mit Verfahren der ganzzahligen  linearen Planungsrechnung lassen sich Problemstellungen der Ablaufplanung sehr detailliert und auch facettenreich erfassen. Zur Abbildung der Reihenfolge-Bedingungen und -Alternativen wählt man i.d.R. Binärvariable. Bekannte Grundmodelle stammen z.B. von Bowman und Manne (Bowman, E. H. 1959; Manne, A. S. 1960), gefolgt von zahlreichen Ansätzen insb. aus den 1960er- und 1970er-Jahren (vgl. Überblick bei Rinnooy Kan, A.H. G. 1976). Die LP-Formulierung hat zudem den Vorteil, dass in die gleiche Modellstruktur viele weitere Teilprobleme aufgenommen werden können, mit denen die Ablaufplanung zusammenhängt. So ergeben sich z.B. simultane Losgrößen- und Reihenfolgemodelle, ggf. auch über mehrere Produktionsstufen hinweg. Die umfassendste Modellanalyse hierzu liefert Küpper (Küpper, H. -U. 1980), der insb. die Interdependenzen zwischen der Ablaufplanung und den wichtigen anderen produktionspolitischen Entscheidungen untersucht. So erweist sich der Modelltyp der LP als ein umfassendes Abbildungsinstrument, das auch komplexe Modelle systematisch aufzubauen erlaubt, doch bleiben die Lösungsmöglichkeiten ganzzahliger LP-Modelle hinter den Erfordernissen derartiger Ablaufplanungsmodelle deutlich zurück. Zwar konnten in den vergangenen Jahren auch hier bemerkenswerte Fortschritte erzielt werden, sodass inzwischen auch etwas umfangreicher Binärprobleme numerisch gelöst werden können (vgl. vor allem Preßmar, D. B. 1992); als generelles, praktisch einsetzbares Lösungsverfahren empfiehlt sich aber die LP für Ablaufprobleme nach wie vor kaum. Ablaufplanungsprobleme sind mathematisch gesehen spezielle Aufgaben der Kombinatorik. Daher liegt eine Modellierung als Entscheidungsbaumproblem nahe. Die Reihenfolge-Alternativen werden hier systematisch enumeriert – so braucht ein Entscheidungsbaumverfahren nicht auf Problemspezifika ausgerichtet zu sein. Allerdings ist die Integration kontinuierlicher Entscheidungsprobleme, etwa Losgrößenfragen, nahezu unmöglich. von den Typen der Entscheidungsbaumverfahren sind die Branch-and-Bound-Ansätze im Rechenablauf am flexibelsten (vgl. Seelbach, H. 1975 sowie zu einem der ersten Grundsätze Ignall, E./Schrage, L. 1965). Ihre Stärke ist, dass sie die besonderen Eigenschaften eines Problems ausnutzen können, und zwar einmal in der »Branch«-Regel, nach der sukzessive verschiedene Alternativenteilklassen gebildet werden, und zum anderen in der Bestimmung der »Bounds«, d.h. des innerhalb einer Alternativenteilklasse keinesfalls überschreitbaren, aber bestenfalls erreichbaren Zielausmaßes. Beim Job-Shop-Problem orientiert sich die Branch-Regel häufig an der Problemformulierung als disjunktiver Graf. Jede Verzweigung bedeutet hier eine bestimmte Festlegung einer weiteren disjunktiven Kante. Die Qualität eines Branch-and-Bound-Verfahrens hängt weitgehend von der Bound-Berechnung ab. Besonders eindrucksvoll zeigen dies die Lösungsversuche eines in der Literatur seit 1963 (Muth, J. F./Thompson, G. L. 1963) immer wieder behandelten Job-Shop-Fallbeispiels zur Zyklusminimierung bei 10 Aufträgen und 10 Maschinen. Eine exakte Lösung gelang erst 1989, als Carlier/Pinson (Carlier, J./Pinson, E. 1989) eine besonders geschickte Bound-Berechnung fanden. III. Problematik der Lösung von Ablaufplanungsproblemen 1. Komplexität exakter Verfahren zur Ablaufplanung Auch bei den vergleichsweise erfolgreichen Branch-and-Bound-Verfahren stößt die tatsächliche numerische Lösbarkeit bereits bei kleinem Problemumfang alsbald an zeitliche Grenzen. Deshalb stellt sich die Frage, ob für nicht ganz triviale Ablaufprobleme überhaupt exakte Lösungsverfahren mit vertretbarerem Rechenaufwand existieren können. Dies hat man ab Beginn der 1970er-Jahre mit der Komplexitätsanalyse der theoretischen Informatik (vgl. Cook, S. A. 1971; Karp, R. M. 1972; Bachem, A. 1980) zu beantworten versucht. Sie hat zu einer Neuorientierung der gesamten Methodendiskussion der Ablaufplanung geführt. Kernidee ist, die Optimierungsprobleme einer der beiden folgenden Gruppen zuzuordnen: - der »Klasse P« der polynomial lösbaren Probleme: Zu ihnen kennt man mindestens ein polynomiales Lösungsverfahren: Bei einem solchen steigt die Anzahl der Rechenoperationen mit der Problemgröße – gemessen durch die Länge der Eingabedaten – höchstens wie ein Polynom. - der Klasse der »NP-schwierigen« Probleme: Sie umfasst alle Probleme, die mindestens von gleicher Komplexität wie das Problem des Handlungsreisenden (Travelling Salesman Problem) sind (Cook, S. A. 1971). Zwar existiert kein Beweis, dass sie nicht polynomial lösbar sind, alle bisherigen Erkenntnisse lassen dies aber vermuten. Nun kann auch die polynomiale Lösbarkeit ab einer gewissen Größenordnung (z.B. ab einer größeren Anzahl von Aufträgen oder Maschinen) zu einem nicht mehr vertretbaren Rechenaufwand führen. Aber es gibt dennoch einen zentralen Unterschied zu den NP-schwierigen Problemen: Letztere erlauben schon bei relativ kleinem Problemumfang oft nur eine Rechenzeitabschätzung, die sich nach Jahrhunderten bemisst (Garey, M. R./Johnson, D. S. 1979; Bachem, A. 1980). Der Nachweis seiner NP-Schwierigkeit bedeutet für ein Problem praktisch, dass auf eine exakte Optimierung verzichtet werden muss. Für die Ablaufplanungsprobleme sind die Ergebnisse der Komplexitätsanalyse eher ernüchternd: Polynomial lösbar sind nur die ganz einfachen Grundprobleme für eine oder zwei Maschinen bzw. zwei oder drei Aufträge sowie vereinzelte Sonderfälle komplizierterer Probleme. Auf sie können im Wesentlichen die o.g. konstruktiven Lösungsmethoden oder Modifikationen und Weiterentwicklungen davon angewendet werden. Für einige Problemklassen ist die Komplexitätsfrage noch ungeklärt. Die überaus meisten Probleme aber sind NP-schwierig (vgl. zur Einordnung in die Komplexitätsklassen im Detail z.B. Rinnooy Kan, A.H. G. 1976; Brucker, P. 1981; Domschke, W./Scholl, A./Voß, S. 1993). Nun darf man die Charakterisierung eines Ablaufproblems als NP-schwierig nicht überbewerten. Es sagt eigentlich nur, dass man dafür keinen Algorithmus erwarten darf, der in allen Unterfällen und bei jeder denkbaren numerischen Ausprägung der Parameter mit akzeptablem Aufwand arbeitet. Da die Komplexitätsbeweise sich am ungünstigsten Fall orientieren müssen (»Worst-Case«-Analyse), wäre für einen konkreten Algorithmus durchaus ein durchschnittliches Laufzeitverhalten denkbar, das weit unter den errechneten Grenzen bleibt. Das prominente Beispiel hierfür ist das Simplexverfahren, das in der praktischen Anwendung hervorragend, jedoch wegen des »worst-case« von primalen und dualen Rechenzyklen nicht polynomial ist. Da zur Lösung der Ablaufplanungsfragen typischerweise Entscheidungsbaumverfahren dominieren, ist hier freilich derartig Markantes kaum zu erwarten. Eher schon mag eine präzisere Analyse der Parameterverhältnisse und -größenordnungen des konkreten betrieblichen Problemfalls rechenzeitgünstige Spezialalgorithmen ermöglichen. Dies setzt jedoch voraus, in die Lösungsmethode mehr »problembezogenes« Verständnis einzubringen, statt sie eher formal zu konstruieren (French, S. 1982). Gerade diese Problemdurchdringung fällt jedoch in der Ablaufplanung besonders schwer: I.d.R. erscheint keine der möglichen Reihenfolgen von vorneherein als optimale Lösung besonders prädestiniert. 2. Heuristische Ablaufplanung Die weitgehende Erfolglosigkeit der Suche nach effizienten Algorithmen und die Erkenntnisse der Komplexitätsuntersuchungen führen dazu, dass bei der Ablaufplanung i.A. heuristische Methoden im Vordergrund stehen. Darunter wiederum sind zunächst die Prioritätsregeln für die Reihenfolgeplanung zu nennen. Sie führen nicht nur unmittelbar zu einer Lösung; sie erlauben auch die sukzessive Einplanung nacheinander eintreffender Aufträge, und sie sind vor allem auch dezentral einsetzbar (Haupt, R. 1989). Heuristische Methoden, die zu einem zentralen Gesamt-Ablaufplan führen, orientieren sich häufig am Vorbild exakter Lösungsansätze für gleiche oder auch einfachere Ablaufplanungs-Problemstellungen. So sind z.B. zahlreiche Ablaufplanungs-Heuristiken als unvollständige (abgebrochene) Branch-and-Bound-Verfahren zu interpretieren. Nach jeweils eigenen Regeln bleiben dann ganze Zweige des Entscheidungsbaums unberücksichtigt. Dem gleichen Prinzip folgen die »tabu-search«-Verfahren (vgl. z.B. Glover, F. 1989; Widmer, M./Hertz, A. 1989). Bei ihnen werden Tabu-Listen wegzulassender Alternativenteilmengen vorgegeben bzw. aufgebaut, die aber gegen Ende einer Lösungskonstruktion wieder unbeachtet bleiben dürfen. Heuristiken, die auch im Verfahrensablauf stärker problemspezifisch sind, generieren im ersten Schritt bereits eine relativ gute Lösung, die anschließend iterativ zu verbessern versucht wird. Das Prinzip der Verbesserungsverfahren besteht darin, zu »benachbarten« Alternativen überzugehen (z.B. Haupt, R. 1987; Fry, T. D./Vicens, L./Macleod, K. et al. 1989). Sie unterscheiden sich nur durch eine Transformation, etwa einen Reihenfolgen-Tausch von der vorherigen Lösung. Eine spezielle Variante ist das simulated annealing (vgl. Aarts, E./Korst, J. 1990). Zur Konstruktion einer Anfangslösung bieten sich u.a. Prioritätsregeln sowie konstruktive Verfahren für vereinfachte (»relaxierte«) Probleme an. Für manche Problemtypen gibt es spezifische Eröffnungsverfahren, so das »Shifting-Bottleneck«-Verfahren von Adams/Balas/Zawack (Adams, J./Balas, E./Zawack, D. 1988). Es konstruiert über die Bestimmung der Auftragsfolgen geschickt aufeinanderfolgend gewählter »Engpass-Maschinen« eine zielgünstige Anfangslösung für das Job-Shop-Problem. Erst in den Anfängen sind Expertensysteme in  PPSfür den heuristischen Entwurf günstiger Ablaufpläne (Schmidt, G. 1989; Noronha, S. J./Sarma, V.V. S. 1991). Im Unterschied zu den exakten Verfahren ist bei Heuristiken der Rechenaufwand nahezu beliebig begrenzbar. Das Generieren einer Anfangslösung benötigt durchweg keinen nennenswerten Zeitaufwand. Ob und wie lange man Verbesserungsiterationen durchführen will, hat man in der Hand. Versuche, die Lösungsgüte durch Berechnung einer maximalen absoluten oder relativen Abweichung vom exakten Optimum brauchbar abzuschätzen, schlagen – wieder aus Gründen des Worst-Case-Ansatzes – regelmäßig fehl (vgl. Garey, M. R./Johnson, D. S. 1979). Man kann aber mit Simulationsuntersuchungen eine Durchschnittsgüte nachweisen. So sind für die Standardprobleme der Ablaufplanung heute akzeptable Heuristiken verfügbar bzw. problemspezifisch konstruierbar. Wie Anwendungsbeispiele, etwa ihr Einsatz in elektronischen Leitstandkonzepten zeigen, gilt dies insb. auch für die Ablaufplanung unter den veränderten Bedingungen heutiger Produktion mit flexiblen Fertigungssystemen (vgl. hierzu Kuhn, H. 1990; Montazer, M./Van Wassenhove, L. N. 1990) und kürzeren Umrüstzeiten. Erweiterte Möglichkeiten der Variantenfertigung, kleinere Losgrößen, reduzierte Pufferläger, eine knapper gewordene Ressourcenausstattung sowie engere Terminvorgaben lassen die Bedeutung einer guten Ablaufplanung künftig eher steigen. Literatur: Aarts, E./Korst, J. : Simulated Annealing and Boltzmann Machines, New York 1990 Adams, J./Balas, E./Zawack, D. : The Shifting Bottleneck Procedure for Job Shop Scheduling, in: MS, 1988, S. 391 – 401 Bachem, A. : Komplexitätstheorie im Operations Research, in: ZfB, 1980, S. 812 – 844 Baker, K. R./Nuttle, H.L. W. : Sequencing Independent Jobs within a Single Resource, in: NRLQ, 1980, S. 499 – 510 Balas, E. : Machine Sequencing via Disjunctive Graphs: an Implicit Enumeration Algorithm, in: OR, 1969, S. 941 – 957 Blazewicz, J./Ecker, K./Schmidt, G. : Scheduling in Computer and Manufacturing Systems, Berlin et al. 1993 Bowman, E. H. : The Schedule-Sequencing Problem, in: OR, 1959, S. 621 – 624 Brucker, P. : Scheduling, Wiesbaden 1981 Carlier, J./Pinson, E. : An Algorithm for Solving the Job-Shop Problem, in: MS, 1989, S. 164 – 176 Chow, W. S. : An Efficient Implementation of a Two-Stage Production Scheduling Algorithm, in: JORS, 1989, S. 1049 – 1052 Conway, R. W./Maxwell, W. L./Miller, L. W. : Theory of Scheduling, Reading 1967 Cook, S. A. : The Complexity of Theorem-Proving Procedures, in: Proceedings of the Third Annual ACM Symposium on Theory of Computing, New York 1971, S. 151 – 158 Domschke, W./Scholl, A./Voß, S. : Produktionsplanung, Berlin et al. 1993 Drexl, A./Fleischmann, B./Günther, H. -O. : Konzeptionelle Grundlagen kapazitätsorientierter PPS-Systeme, in: ZfbF, 1994, S. 1022 – 1045 French, S. : Sequencing and Scheduling, Chichester 1982 Fry, T. D./Vicens, L./Macleod, K. : A Heuristic Solution Procedure to Minimize T on a Single Machine, in: JORS, 1989, S. 293 – 297 Garey, M. R./Johnson, D. S. : Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco 1979 Glazebrook, K. D. : On Single Machine Sequencing with Order Constraints, in: NRLQ, 1980, S. 123 – 130 Glover, F. : Tabu-Search-Part I, in: ORSA J. on Computing, 1989, S. 190 – 206 Gonzalez, T./Sahni, S. : Open Shop Scheduling to Minimize Finish Time, in: J. of the Association for Computing Machinery, 1976, S. 665 – 679 Graham, R. L./Lawler, E. L./Lenstra, J. K. : Optimization and approximation in deterministic sequencing and scheduling: a survey, in: Annals of Discrete Mathematics, 1979, S. 287 – 326 Haupt, R. : Produktionstheorie und Ablaufmanagement, Stuttgart 1987 Haupt, R. : A Survey of Priority Rule-Based Scheduling, in: ORSpek, 1989, S. 3 – 16 Ignall, E./Schrage, L. : Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems, in: OR, 1965, S. 400 – 412 Jackson, J. R. : Scheduling a Production Line to Minimize Maximum Tardiness, in: Research Report 43, University California, Los Angeles, 1955 Johnson, S. M. : Optimal Two- and Three-Stage Production Schedules With Setup Times Included, in: NRLQ, 1954, S. 61 – 68 Karp, R. M. : Reducibility among Combinatorial Problems, in: Complexity of computer computations, hrsg. v. Miller, R. E./Thatcher, J. W., New York 1972, S. 85 – 103 Kise, H./Ibaraki, T./Mine, H. : A Solvable Case of the one Machine Scheduling Problem with Ready Times and Due Dates, in: OR, 1978, S. 121 – 126 Kuhn, H. : Entlastungsplanung von flexiblen Fertigungssystemen, Heidelberg 1990 Küpper, H. -U. : Interdependenzen zwischen Produktionstheorie und der Organisation des Produktionsprozesses, Berlin 1980 Küpper, H. -U. : Ablauforganisation, Stuttgart 1981 Kusiak, A. : Efficient Implementation of Johnson\'s Scheduling Algorithm, in: III E, 1986, S. 215 – 216 Lawler, E. L. : Optimal Sequencing of a Single Machine Subject to Precedence Constraints, in: MS, 1973, S. 544 – 546 Lawler, E. L./Lenstra, J. K./Rinnooy Kan, A.H. G. : Sequencing and Scheduling: Algorithms and Complexity, Report BS-R8909, Centrum voor Wiskunde en Informatica, Amsterdam 1989 MacCarthy, B. L./Liu, J. : Addressing the Gap in Scheduling Research: a Review of Optimization and Heuristic Methods in Production Scheduling, in: IJProdRes, 1993, S. 59 – 79 Manne, A. S. : On the Job-Shop Scheduling Problem, in: OR, 1960, S. 219 – 223 Mensch, G. : Das Trilemma der Ablaufplanung, in: ZfB, 1972, S. 77 – 88 Montazer, M./Van Wassenhove, L. N. : Analysis of Scheduling Rules for An FMS, in: IJProdRes, 1990, S. 785 – 802 Moore, J. M. : An N-Job, One-Machine Sequencing Algorithm for Minimizing the Number of Late Jobs, in: MS, 1968, S. 102 – 109 Muth, J. F./Thompson, G. L. : Industrial Scheduling, Englewood Cliffs 1963 Noronha, S. J./Sarma, V.V. S. : Knowledge-Based Approaches for Scheduling Problems: a Survey, in: IEEE Transactions on Knowledge and Data Engineering, 1991, S. 160 – 171 Panwalkar, S. S./Woollam, C. R. : Ordered Flow-Shop Problems with no In-Process Waiting: Further Results, in: JORS, 1980, S. 1039 – 1043 Preßmar, D. B. : Betriebswirtschaftliche Planung und mathematische Optimierung, in: Praxis und Theorie der Unternehmung, hrsg. v. Hansmann, K. -W./Scheer, A. -W., Wiesbaden 1992, S. 277 – 290 Rinnooy Kan, A.H. G. : Machine Scheduling Problems, Leiden 1976 Schmidt, G. : CAM: Algorithmen und Decision Support für die Fertigungssteuerung, Berlin et al. 1989 Schweitzer, M. : Methodologische und entscheidungstheoretische Grundfragen der betriebswirtschaftlichen Prozeßstrukturierung, in: ZfbF, 1967, S. 279 – 296 Schweitzer, M. : Ablauforganisation, in: HWB, hrsg. v. Grochla, E./Wittmann, W., 4. A., Stuttgart 1974, Sp. 1 – 8 Seelbach, H. : Ablaufplanung, Würzburg 1975 Seelbach, H. : Ablaufplanung, in: HWB, Bd. 1, hrsg. v. Wittmann, W./Kern, W./Köhler, R. et al., 5. A., Stuttgart 1993, Sp. 1 – 15 Sidney, J. B. : Optimal Single Machine Scheduling with Earliness and Tardiness Penalties, in: OR, 1977, S. 62 – 69 Smith, W. E. : Various Optimizers for Single Stage Production, in: NRLQ, 1956, S. 59 – 66 Troßmann, E. : Aufgaben der industriellen Fertigungsvorbereitung, in: WiSt, 1986, S. 245 – 252 Widmer, M./Hertz, A. : A New Heuristic Method for the Flow Shop Sequencing Problem, in: EJOR, 1989, S. 186 – 193