Maschinenbelegungsplanung in mehrstufigen entkoppelten Produktionssystemen

Holm Fischäder, Richard Göhler und Gerfried M. Schneider

In diesem Beitrag werden die theoretischen Grundlagen der Maschinenbelegungsplanung für mehrstufige Produktionsumgebungen erörtert und davon ausgehend Lösungsverfahren für Belegungsprobleme unter praxisrelevanten Problemstellungen entwickelt. In … (Verweis auf Que l le durch Verlag) wurde eine Kurzfassung dieses Beitrages veröffentlicht. In der hier vorgelegten Online-Fassung werden die Abbildung praxistypischer Rahmenbedingungen für die Maschinenbelegungsplanung sowie die Bewertung alternativer Belegungspläne ausführlicher beschrieben.

Gegenstand der Maschinenbelegungsplanung
Maschinenkapazitäten in Industrieunternehmen sind in der Regel begrenzt und deren Erweiterung durch interne oder externe Ressourcen mit erheblichen Kosten verbunden. Folglich ist eine sinnvolle Belegung der vorhandenen Maschinen notwendig, da die Wahl der Bearbeitungsreihenfolge der Aufträge einen entscheidenden Einfluss auf die Wettbewerbsfähigkeit und das Erreichen von Unternehmenszielen haben kann. Für viele produzierende Unternehmen ist die Maschinenbelegungsplanung aus diesem Grund eine bedeutende Herausforderung innerhalb der Produktionsplanung und -steuerung [1].
In der Literatur wird der Begriff der Maschinenbelegungsplanung oft synonym zu Ablauf-, Reihenfolge- bzw. Auftragsreihenfolgeplanung oder Feinterminierung verwendet. Unter Maschinenbelegungsplanung wird in diesem Beitrag die Zuordnung von einer gegebenen Menge an freigegebenen Fertigungsaufträgen zu den verfügbaren Maschinen verstanden. Die Belegungsplanung beinhaltet demnach die Reihenfolgeplanung sowie die Feinterminierung [1]. Da mehrere Aufträge gleichzeitig um knappe Maschinenkapazitäten konkurrieren, ist es zunächst notwendig, Reihenfolgen zur Bearbeitung der Aufträge auf den einzelnen Maschinen zu bilden (Reihenfolgeplanung, sequencing). Anschließend werden für jeden Auftrag Start- und Endzeitpunkte der Bearbeitung festgelegt und somit eine detaillierte zeitliche Verteilung der Aufträge auf den Maschinen vorgenommen (Feinterminierung, scheduling) [1, 2].
Mit der Bestimmung, wann und in welcher Reihenfolge Aufträge bearbeitet werden, ist die Maschinenbelegungsplanung die Nahtstelle zwischen der Produktionsplanung und der Durchführung von Produktionsprozessen [3]. Dabei liegen Ergebnisse vorangegangener Planungsschritte als Datum vor. Etwa sind Entscheidungen zum Produktionsprogramm oder der Kapazitätsplanung vorgelagert und dienen als Planungsvorgabe zur Maschinenbelegung [4]. Die Anzahl und Beschaffenheit der zu erstellenden Produkte sowie die Anzahl und Eigenschaften der Maschinen werden somit als gegeben vorausgesetzt. Neben der Menge an Aufträgen (j=1,..,n) und der verfügbaren Maschinen (i=1,…m) sind zudem folgende Eingangsdaten für ein Belegungsproblem gegeben: der (gewünschte) Fertigstellungstermin eines Auftrags fj , die Bearbeitungszeit eines Auftrags auf einer Maschine pj;i sowie die Anzahl an Arbeitsgängen je Auftrag gj . Eingangsdaten unterliegen Einflüssen von Zeit und Unsicherheit. In diesem Beitrag werden nur statische und deterministische Probleme behandelt, weshalb die Eingangsdaten als bekannt und sicher angesehen werden.
Des Weiteren lassen sich zwei Arten von Reihenfolgen unterscheiden [5, 6]: Die Maschinenfolge definiert die Sequenz der notwendigen Arbeitsgänge zur Erstellung eines Produktes und muss als bindende Restriktion stets erfüllt werden. Gegenstand der Maschinenbelegungsplanung ist die Auftragsfolge, d. h. die zeitliche Aufeinanderfolge mehrerer Aufträge auf einer Maschine unter Einhaltung der Maschinenfolgen. Die Lösung eines Planungsproblems liegt vor, sobald die Maschinen- und Auftragsfolgen für alle Aufträge und Maschinen bekannt sind [5]. Das Ergebnis lässt sich als maschinen- oder auftragsorientiertes Gantt-Diagramm visualisieren und wird auch als Belegungsplan bezeichnet.
 
Klassifikation von Maschinenbelegungsproblemen
In der Literatur existiert eine Vielzahl von Modellen zur Maschinenbelegungsplanung [2]. Zur Charakterisierung deterministischer Problemstellungen hat sich ein weitgehend einheitliches Klassifikationsschema durchgesetzt. Dabei werden Modelle hinsichtlich ihrer Maschinen- und Auftragscharakteristik sowie ihrer Zielsetzung klassifiziert. In diesem Beitrag ist primär das der Belegungsplanung zugrundeliegende Produktionssystem interessant, weshalb im Folgenden eine Klassifizierung nach der Maschinenumgebung vorgenommen wird. Dabei erfolgt zunächst eine Differenzierung anhand der Anzahl an Arbeitsgängen der Aufträge gj in einstufige und mehrstufige Problemstellungen (siehe Bild 1).
 


Bild 1: Klassifizierung von Maschinenbelegungsproblemen
nach der Maschinenumgebung.

Einstufige Fertigung
Besteht ein Auftrag aus genau einem Arbeitsgang (gj=1), liegt eine einstufige Fertigung vor, die abhängig von der Anzahl nutzbarer Maschinen weiter differenziert werden kann. Bei Einmaschinenproblemen als einfachsten Fall ist zur Bearbeitung von n Aufträgen genau eine Maschine verfügbar (m=1). Es ist lediglich die Reihenfolge der auf der einen Maschine zu fertigenden Aufträge zu bestimmen [6].
Stehen zur Bearbeitung der Aufträge mehrere Maschinen zur Verfügung ( m>1 ), liegt ein Problem paralleler Maschinen vor. Hier müssen neben Reihenfolgeentscheidungen auch Zuordnungsentscheidungen getroffen werden [1,6]. Hinsichtlich der Fertigungsgeschwindigkeit lassen sich des Weiteren identische parallele, uniforme parallele und heterogene parallele Maschinen unterscheiden. Bei identischen parallelen Maschinen gilt pj;i=pj. Die Fertigungszeit für den Auftrag j ist somit auf allen Maschinen gleich. Bei uniformen parallelen Maschinen unterscheiden sich die Fertigungsgeschwindigkeiten um einen konstanten Faktor  vi , sodass für die Bearbeitung des Auftrags j auf der Maschine i gilt: pj;i=pj/vi . Bei heterogenen parallelen Maschinen ist die Fertigungsgeschwindigkeit maschinen- und auftragsabhängig. Da in der Praxis oft Maschinen unterschiedlichen Typs zur Bearbeitung des gleichen Arbeitsgangs eingesetzt werden oder sich Maschinen gleichen Typs bspw. aufgrund von Abnutzung hinsichtlich ihrer Bearbeitungsgeschwindigkeit unterscheiden, ist dies der praxisrelevante Fall.
Mehrstufige Fertigung
Eine mehrstufige Fertigung liegt dann vor, wenn Aufträge aus mehreren Arbeitsgängen bestehen (gj>1). Diese Problemklasse weist folglich eine deutlich höhere Komplexität auf [6]. Sie wird nach dem eingesetzten Organisationstyp des zugrundeliegenden Produktionssystems differenziert.
Bei einer Fertigung nach dem Fließprinzip haben alle Erzeugnisse einen einheitlichen Materialfluss. Es wird in Fließfertigung mit bzw. ohne zeitliche Bindung unterschieden [3]. Liegt eine zeitliche Bindung vor, sind die einzelnen Fertigungsstufen durch Fördereinrichtungen verknüpft (Taktfertigung). Hierbei ist das Problem des Fließbandabgleichs zu lösen. Maschinenbelegungsprobleme treten bei Fließfertigung ohne zeitliche Bindung auf (Reihenfertigung; Flow Shop). Die Arbeitsgänge ähnlicher Produkte werden in der gleichen Reihenfolge bearbeitet. Für die Bearbeitung jedes Arbeitsgangs steht eine Maschine gleicher Art zur Verfügung.
Sonderfälle zu diesem allgemeinen Flow Shop-Problem ergeben sich durch:
·  eine identische Auftragsfolge auf allen Maschinen (Permutation Flow Shop-Problem),
·  parallele Maschinen des gleichen Typs auf mindestens einer Fertigungsstufe (Modellierung als Flexible Flow Shop) [2, 7]. In Flexible Flow Shop-Problemen durchlaufen die Aufträge somit nicht m Maschinen, sondern m Fertigungsstufen mit einer bestimmten Anzahl paralleler Maschinen.
Job Shop-Probleme sind verallgemeinerte Flow Shop-Probleme und beschreiben eine Werkstattproduktion. Die Arbeitsgangfolge der Aufträge ist unterschiedlich, muss aber dennoch wie durch die Maschinenfolge vorgeschrieben eingehalten werden. Eine Maschine kann dabei auch mehrere Arbeitsgänge bearbeiten. Wie bei Flow Shop-Problemen existieren analog die Sonderfälle Permutation Job Shop und Flexible Job Shop [2].
Bei Open Shop-Problemen ist die Reihenfolge, in der die Arbeitsgänge ausgeführt werden, beliebig. Somit sind weder eine Arbeitsgang- noch eine Maschinenfolge vorgegeben. Dieser Planungsfall umschreibt ein flexibles Fertigungssystem mit Mehrzweckmaschinen [2].
Entkopplungspuffer in der Maschinenbelegungsplanung
Im Klassifikationsschema für Maschinenbelegungsprobleme werden als Auftragscharakteristika verschiedene Annahmen und Rahmenbedingungen beschrieben. Darunter zählt auch die Berücksichtigung von physischen Entkopplungspuffern zweier aufeinanderfolgender Fertigungsstufen. Als Entkopplungspuffer werden in diesem Beitrag physische Zwischenlager bezeichnet, die kurzfristige, prozessbedingte Schwankungen aufeinanderfolgender Fertigungsstufen ausgleichen. Die Begriffe Entkopplungspuffer, Puffer und Zwischenlager werden synonym verwendet. In den meisten Veröffentlichungen zur Maschinenbelegungsplanung werden unbegrenzte Zwischenlagerkapazitäten angenommen [7].
Durch β10=no wait werden Probleme charakterisiert, bei denen keine Zwischenlagerung erlaubt ist. Nachdem ein Arbeitsgang auf einer Maschine fertiggestellt wurde, muss die Bearbeitung des nächsten Arbeitsgangs ohne Wartezeit beginnen. Aufträge werden somit nach dem FIFO-Prinzip gefertigt [2, 8].
Der Eintrag β10=block umfasst Probleme mit limitierten Zwischenlagerkapazitäten. Sind diese Kapazitäten vollständig ausgelastet, kann ein Auftrag die Maschine auf der vorherigen Fertigungsstufe nicht verlassen und blockiert diese bis entsprechende Kapazitäten im Zwischenlager frei werden [7, 8]. Das FIFO-Prinzip muss hierbei nicht zwingend eingehalten werden. Neben einem lokalen Puffer zwischen zwei aufeinanderfolgenden Maschinen bzw. Fertigungsstufen ist auch ein globaler Puffer für das gesamte Produktionssystem denkbar [2].
Entkopplungspuffer können in mehrstufigen Produktionssystemen unterschiedliche Funktionen haben, die Einfluss auf die Maschinenbelegungsplanung nehmen. Sie können durch eine Entkopplung des Produktionsablaufs unterschiedliche Fertigungsgeschwindigkeiten der einzelnen Arbeitsgänge ausgleichen oder die Auswirkungen von Störungen einer Fertigungsstufe auf das restliche Produktionssystem reduzieren. Ein gut dimensionierter Puffer ist somit notwendig, damit Belegungspläne auch bei einem Störungsfall oder bei sonstigen in der Planung unberücksichtigten Ereignissen realisierbar bleiben. Eine große Rolle spielen Puffer als Kopplungspunkte zur Änderung der Reihenfolge des Materialflusses (z. B. beim Übergang von einer bestands- zur auftragsgeführten Produktion oder vor der Montage von mehreren Vorprodukten). Zur mengengerechten Erfüllung des Kundenbedarfs ist dann stets eine hinreichende Anzahl an Zwischenerzeugnissen aus vorgelagerten Produktionsstufen erforderlich. Außerdem kann eine Zwischenlagerung aufgrund von technischen Restriktionen, z. B. zur Einhaltung einer Aushärtezeit, notwendig sein.
 
Verfahren zur Lösung von Maschinenbelegungsproblemen 
Nachfolgend sollen die bekanntesten praxisrelevanten Lösungsverfahren zu mehrstufigen Belegungsproblemen vorgestellt werden. Sie lassen sich zunächst in optimierende und heuristische Verfahren unterscheiden, wobei diese Unterscheidung nicht immer überschneidungsfrei ist. Unterstützend kann das Werkzeug der Simulation eingesetzt werden (siehe Bild 2).
Für detaillierte Verfahrensbeschreibungen wird auf die jeweils angegebene weiterführende Literatur verwiesen.
 


Bild 2: Überblick über Lösungsverfahren von
Maschinenbelegungsproblemen.

 
 
Optimierende Lösungsverfahren
Optimierende Verfahren garantieren bei endlich vielen Rechenschritten die optimale Lösung für eine gegebene Problemstellung. Modelle der Maschinenbelegungsplanung gehören zur Klasse der kombinatorischen Optimierungsprobleme, bei denen eine optimale Lösung aus einer endlichen Menge zulässiger Lösungen gesucht wird [1]. Eine sehr aufwändige Lösungsmethode ist die vollständige Enumeration , bei der jeder mögliche Belegungsplan ermittelt und hinsichtlich eines Zielfunktionswertes verglichen wird. Die Optimallösung ist dementsprechend das Element der Lösungsmenge mit dem höchsten Zielfunktionswert [6].  
Demgegenüber wird bei der begrenzten Enumeration zur Reduzierung der Rechenzeit der Lösungsraum in Teilmengen gegliedert und schrittweise verkleinert. Ausgehend von einer zulässigen Basislösung werden nur Belegungspläne vollständig aufgebaut und als neuer Vergleichswert benutzt, deren Zielfunktionswert nicht schlechter als der bisher beste Vergleichswert ist. Hierzu zählt das Branch-and-Bound-Verfahren, was Untersuchungsgegenstand für eine Vielzahl an Veröffentlichungen zu Flow Shop- oder Job Shop-Problemen ist, aber selten Anwendung auf praktische Problemstellungen findet [8].
Heuristische Lösungsverfahren
Heuristische Lösungsverfahren verzichten auf eine Garantie der Optimalität der gefundenen Lösung, sondern versuchen möglichst gute zulässige Lösungen zu finden. Dies führt gegenüber optimierenden Verfahren zu einer höheren zeitlichen Effizienz. Problematisch ist dabei allerdings, dass die Güte der gefundenen Lösung nicht von einem Optimum abgeleitet werden kann, da dieses nicht bestimmt wird. Als Maßstab der Lösungsgüte müssen daher Abschätzungen in Form von oberen bzw. unteren Schranken herangezogen werden [9].
Heuristische Lösungsverfahren können in verschiedene Gruppen eingeteilt werden: Heuristiken dienen z. B. als Eröffnungsverfahren zum Finden einer zulässigen Ausgangslösung, z. B. für das Branch-and-Bound-Verfahren, um die Ermittlung einer Optimallösung zu beschleunigen [6]. Zum anderen können sie als Verbesserungsverfahren bzw. lokale Suchverfahren, ausgehend von einer zulässigen Lösung, zur iterativen Verbesserung des Zielfunktionswertes angewendet werden [9].
Unter der Vielzahl an heuristischen Lösungsansätzen sind Prioritätsregelverfahren und Metaheuristiken hervorzuheben, die aufgrund ihrer Relevanz bei der Lösung mehrstufiger Belegungsprobleme anschließend näher erläutert werden.
Prioritätsregelverfahren werden in der Literatur und Praxis am häufigsten zur Lösung von Maschinenbelegungsproblemen eingesetzt. Aufgrund ihrer Einfachheit liefern prioritätsregelbasierte Heuristiken auch bei komplexen Problemen als Eröffnungsverfahren in kurzer Zeit zulässige, aber meist suboptimale Lösungen [8]. Ihr Einsatz erfolgt in zwei Schritten: Zunächst werden die Aufträge, die um die Kapazitäten einer Maschine konkurrieren, mit einem Prioritätswert nach ihrer Dringlichkeit geordnet. Die Rangfolge ergibt sich aus dem zur Ordnung herangezogenen Kriterium. Die eingesetzten Prioritätsregeln lassen sich in bearbeitungszeitbezogene, fertigstellungsterminbezogene und sonstige Regeln unterteilen [1]. Zudem können mehrere Regeln miteinander kombiniert werden. Bild 3 zeigt beispielhaft eine Auswahl häufig eingesetzter Prioritätsregeln nach der oben beschriebenen Klassifikation. Ist die Sortierreihenfolge bekannt, werden die Aufträge entsprechend eingeplant und somit die Auftragsfolge der relevanten Maschine bestimmt. Die Wahl einer geeigneten Prioritätsregel ist von den verfolgten Zielen der Produktionsplanung abhängig [2].
 


Bild 3: Auswahl an Prioritätsregeln.

Metaheuristiken  sind Methoden zur Verbesserung von Ausgangslösungen auf Basis von problemunabhängigen Lösungsprinzipien. Charakteristisch für metaheuristische Verfahren ist eine übergeordnete Strategie, die einen problemspezifischen Ansatz so modifiziert, dass Lösungen gefunden werden, die allein mit dem untergeordneten Verfahren nicht möglich wären [1].
Beim Tabu Search , einem lokalen Suchverfahren, werden ausgehend von einem aktuellen Belegungsplan Lösungen aus dessen Nachbarschaft analysiert und eine neue Vergleichslösung mit besserem Zielfunktionswert identifiziert. Mithilfe einer Liste der letzten analysierten Belegungspläne als „verbotene“ Lösungen wird eine Rückkehr zu bekannten Plänen verhindert sowie Kreisbewegungen bei der lokalen Nachbarschaftssuche und ein vorzeitiges Abbrechen des Verfahrens eingeschränkt, um so zu besseren Lösungen zu gelangen. Die Länge dieser Tabuliste ist von der jeweiligen Problemstellung abhängig [1, 2, 9].
Schwellenwertverfahren verhindern durch die vorübergehende Akzeptanz von schlechteren Lösungen einen (zu) frühen Abbruch der Lösungssuche. Ausgehend von einem hohen Schwellenwert als akzeptable Verschlechterung des anfänglichen Zielfunktionswertes, wird dieser Wert im Verlauf des Verfahrens sukzessive reduziert. Vertreter dieser Verfahrensklasse sind das Simulated Annealing  für stochastische oder das Threshold Accepting   für deterministische Problemstellungen [1, 2, 9].
Die Idee von populationsbasierten Verfahren ist das Zurückführen der Generierungs- und Selektions-Mechanismen von Lösungen auf natürliche Phänomene. Bei Genetischen Algorithmen   als stochastische Suchverfahren werden erzeugte Populationen iterativ verändert und so Folgepopulationen gebildet. Dabei können identische Lösungen übernommen (Reproduktion), zufällige Lösungen miteinander kombiniert (Kreuzung) oder Elemente zufällig verändert werden (Mutation) [1].
Simulation als unterstützendes Verfahren
Simulation wird bei kombinatorischen Optimierungsproblemen eingesetzt, die derart komplex sind, dass sie sich durch analytische Methoden nicht lösen lassen bzw. nicht hinreichend genau abgebildet werden können [10, 11]. Beim Einsatz von Simulationen wird mittels Variation von Einflussgrößen die Analyse des dynamischen Verhaltens eines Systems ermöglicht. Durch Interpretation der Ergebnisse lassen sich so Rückschlüsse auf das Realsystem ziehen [11].
 


Bild 4: Ablauf von Simulationsuntersuchungen.

Der Ablauf von Simulationsuntersuchungen lässt sich in vier Phasen gliedern (siehe Bild 4). Zunächst wird die Problemstellung analysiert und daraus die Planungsaufgabe sowie Zielvorgaben abgeleitet. Das zu untersuchende reale und in der Regel komplexe Produktionssystem wird anschließend in Form eines abstrahierten Simulationsmodells vereinfacht abgebildet. Die Datenerhebung kann sich in der Praxis jedoch schwierig gestalten, wenn die zur Modellerstellung notwendigen Daten nicht oder nur teilweise digital vorliegen oder erst erhoben werden müssen. Der Aufwand für die Modellerstellung und Pflege des Modells ist zudem vom Detaillierungsgrad des Modells abhängig.
Durch systematische Parameteränderungen in dem experimentierfähigen Modell wird das dynamische Verhalten des Systems analysiert. Die optimale Parametereinstellung ist jedoch besonders bei komplexen Problemstellungen, z. B. aufgrund von Zielkonflikten, nicht offensichtlich und muss in einer Simulationsstudie experimentell ermittelt werden, deren Ergebnisse Rückschlüsse auf die Struktur sowie auf die statischen und dynamischen Eigenschaften des Ursprungssystems zulassen [6, 11].
Die Einsatzmöglichkeiten von Simulationen in der Belegungsplanung lassen sich wie folgt typologisieren [10]: 
Erstellung von Belegungsplänen für kurze Planungshorizonte. Dazu werden Aufträge mithilfe von Prioritätsregeln den Maschinen zugeordnet und Auftragsfolgen generiert. Im Gegensatz zu typischen Simulationsuntersuchungen werden hierbei wenige Simulationsläufe an einem deterministischen Modell durchgeführt, um mit unterschiedlichen Strategien der Belegungsplanung zu experimentieren.
Bestimmung der für die Simulation geeigneten Parameter. Die Simulation dient hier zur Bestimmung der Werte für Parameter, die hinsichtlich einer betrachteten Zielfunktion optimal sind.
Bei einer simulationsbasierten Optimierung werden zur Unterstützung von (meta-)heuris-
tischen Verfahren mehrere Belegungspläne ermittelt und anschließend gemäß der definierten Zielvorgaben bewertet.
Um die Effizienz eines Algorithmus zur Belegungsplanung vor dem Einsatz am realen Produktionssystem zu testen, kann dieser im Rahmen einer Simulation überprüft werden. Dazu wird das Originalsystem in einem Modell abgebildet und anschließend die Leistungsfähigkeit des Algorithmus im Vergleich zu anderen Lösungsmethoden für das Belegungsproblem bewertet - Emulation und Evaluation.
Anwendbarkeit der Lösungsverfahren auf reale Maschinenbelegungsprobleme
Simulationen haben gegenüber analytischen Optimierungsverfahren bei praktischen Fragestellungen der Belegungsplanung eine höhere Akzeptanz. Die Gründe dafür liegen vor allem in der besseren Anschaulichkeit der Ergebnisse und dem breiteren Anwendungsspektrum. Darüber hinaus lassen sich beim Einsatz von Simulationen Produktionssysteme hoher Komplexität meist ohne fundierte mathematische Kenntnisse abbilden.
Demgegenüber werden optimierende Lösungsverfahren nur zu wissenschaftlichen Betrachtungen von Spezialfällen der mehrstufigen Belegungsplanung mit geringer Komplexität eingesetzt und sind somit für die betriebliche Praxis kaum geeignet [12].
Für die Anwendung in der praktischen Belegungsplanung interessanter ist die Ermittlung von (suboptimalen) Lösungen mittels Heuristiken. Durch den Verzicht auf optimale Lösungen lassen sich mit heuristischen Verfahren auch für Problemstellungen in praxisrelevanter Größenordnung zufriedenstellende zulässige Lösungen mit vertretbarem Rechenaufwand erzeugen. Besonders beim Einsatz von Prioritätsregeln werden die Aufträge in sehr kurzer Rechenzeit mit einem Prioritätswert bewertet und geordnet. Häufig werden prioritätsregelbasierte Verfahren in Leitstände zur Produktionsplanung und -steuerung integriert [13].
 
Methodik zur Bewertung von alternativen Maschinenbelegungsplänen
Im Folgenden wird eine allgemeine Methodik zur Bewertung von alternativen Maschinenbelegungsplänen auf Basis eines multikriteriellen Zielsystems beschrieben, die auch in der betrieblichen Praxis anwendbar ist. Dazu werden zunächst Zielkriterien der Belegungsplanung analysiert und anschließend Besonderheiten bei der multikriteriellen Zielsetzung herausgearbeitet.
Zielsetzungen der Maschinenbelegungsplanung
Ziele beschreiben allgemein einen anzustrebenden bzw. zu erreichenden Zustand und liefern Informationen, welche Handlungsalternative aus einem Entscheidungsfeld für den Planer vorteilhaft ist [2]. Die Zielsetzung wird in der Literatur zur Maschinenbelegungsplanung durch den Eintrag γ im Klassifikationstripel gekennzeichnet. Die in der Belegungsplanung verwendeten Zielkriterien lassen sich nach verschiedenen Gesichtspunkten unterteilen. Eine mögliche Untergliederung erfolgt nach der Quantifizierbarkeit in quantitative und qualitative Kriterien.
Als Zielsetzungen der Maschinenbelegungsplanung werden in der Regel als quantitative Kriterien Zeit- und Kostengrößen herangezogen. Auf die Kosten zur Erstellung des Produktionsprogramms kann durch die Festlegung von Auftragsfolgen nur bedingt Einfluss genommen werden. Fixe Kostenbestandteile, wie bspw. Maschinenkosten, sind durch die Belegungsplanung nicht veränderlich [14]. Mit der Wahl optimaler Belegungsreihenfolgen wird demnach eine Produktion zu minimalen ablaufbedingten Kosten angestrebt. Die für die Belegungsplanung entscheidungsrelevanten Kostenarten werden im Folgenden kurz benannt: 
·  Terminüberschreitungskosten bei Nichteinhaltung gewünschter bzw. vorgegebener Fertigungstermine;
·  Fehlmengenkosten in Form von Konventionalstrafen (Pönale), bspw. bei verspäteter oder unvollständiger Lieferung;
·  Opportunitätskosten durch Wegfall von Folgeaufträgen durch verspätete oder unvollständige Lieferung (Goodwill-Verluste);
·  Anpassungs- und Beschleunigungskosten zur Vermeidung von Terminüberschreitungen sowie Anpassungsmaßnahmen, wie Überstunden oder Fremdvergabe von Aufträgen.
Das Primärziel der Belegungsplanung ist folglich eine mengen- und termingerechte Erfüllung von Kundenaufträgen und somit die Minimierung von Terminüberschreitungskosten [2, 6]. Weitere, für die Belegungsplanung entscheidungsrelevante, Kostenarten sind:
·  Kapitalbindungskosten durch Lagerung von Rohmaterial oder Zukaufteilen, Zwischenerzeugnissen und Fertigteilen. Sie sind vom Wert der gelagerten Güter, dem Zinssatz und dem Zeitraum der Lagerung abhängig, wovon letzterer durch die Belegungsplanung beeinflusst werden kann [6]. Da viele produzierende Unternehmen nach dem Just-in-time-Prinzip fertigen, ist für eine Minimierung der Lagerhaltungskosten weiterhin anzustreben, dass fremdbezogene Materialien erst kurz vor ihrem Verbrauchstermin zugehen und die Fertigstellung von Endprodukten nahe ihrem Auslieferungstermin liegt.
·  Rüstkosten zur Vorbereitung einer Maschine für die Produktion eines nachfolgenden Auftrags. Darunter werden einerseits notwendige Reinigungs-, Einstell- und Umrüstvorgänge zusammengefasst. Der dabei entstehende Ressourcenverzehr führt zu direkten Rüstkosten. Andererseits werden als indirekte Rüstkosten Opportunitätskosten subsumiert, die entstehen, wenn die vorzubereitende Ressource zeitweilig nicht zur Verfügung steht [2, 6]. Die Minimierung von Rüstkosten ist besonders bei reihenfolgeabhängigen Rüstzeiten relevant.
Bei einem heterogenen Maschinenpark wäre zudem eine erweiterte Betrachtung von ablaufbedingten Fertigungskosten denkbar, wenn funktionsgleiche Maschinen existieren, die einen Arbeitsgang zu unterschiedlichen Kosten ausführen oder die Leistung einer Maschine intensitätsmäßig anpassbar ist [15]. Für die meisten praktischen Fälle sind diese Effekte jedoch schwer quantifizierbar und werden daher hier vernachlässigt.
Auch wenn in der betrieblichen Praxis die Verwendung von Kostenkriterien interessant wäre, werden in der Maschinenbelegungsplanung zumeist Zeitkriterien als zu minimierende Ziele verfolgt. Die Ursache dafür liegt in der schwierigen Quantifizierbarkeit der direkten und indirekten Auswirkungen von Entscheidungen der Belegungsplanung auf die jeweiligen Kostengrößen [1, 2]. Zeitkriterien dienen dann als Substitute für Kostenkriterien und es wird unterstellt, dass sich eine Minimierung der Kosten proportional durch eine Minimierung des zeitbezogenen Ersatzzieles erreichen lässt [2, 14].
Nachfolgend werden die Zeitgrößen vorgestellt, die als Ersatzkriterien in Frage kommen. Die auftrags- und maschinenorientierten Gantt-Diagramme eines beispielhaften Belegungsplans zeigen zudem, wie diese Zeitgrößen ermittelt werden können. Daraus lassen
sich die Bearbeitungszeiten der Aufträge auf den einzelnen Maschinen, deren Rüst- und Wartezeiten sowie die Zykluszeit ablesen (siehe Bild 5).


Bild 5: Beispiel für ein maschinenorientiertes Gantt-Diagramm.

Die Zykluszeit oder Gesamtbearbeitungszeit (engl. makespan) Cmax des Auftragsbestandes bezeichnet die Zeitspanne zwischen Anfangszeitpunkt des ersten Auftrags bis zur Fertigstellung des letzten Auftrags. Sie ist auch ein Maß der Belegungszeit eines Produktionssystems durch den gesamten Auftragsbestand [2]. Die Zykluszeit ist jedoch von der Auftragsfolge der zu bearbeitenden Aufträge abhängig. Durch eine Minimierung der Zykluszeit bei gegebener Auftragsmenge wird eine hohe Kapazitätsauslastung angestrebt.
Ein Auftrag j hat vor einer Maschine Wartezeiten ( Wj;i ), wenn diese durch einen anderen Auftrag belegt ist und sich somit die Bearbeitung des neu ankommenden Auftrags verzögert. Die Wartezeit beschreibt das Zeitintervall zwischen der Fertigstellung eines Auftrags auf der Vorgängermaschine bis zum Beginn der Bearbeitung auf der betrachteten Maschine. Wartezeiten sind Lagerzeiten; sie können als ein zeitbezogenes Ersatzziel zur Minimierung der Kapitalbindungskosten infolge einer Zwischenlagerung von Halbfertigteilen herangezogen werden. Als Zielsetzung kann die Minimierung der gesamten Wartezeit Wj oder der mittleren Wartezeit W verfolgt werden.
Wj=i=1mWj;i                                             W=1n∙j=1nWj
Rüstkosten sind von der Rüstzeit auf einer Maschine abhängig. Wird eine Maschine i zur Bearbeitung eines Auftrags j vorbereitet, wird dies als Rüstzeit  Sj;i bezeichnet. Entsprechend ist die gesamte Rüstzeit des Belegungsplans S als Summe der Rüstzeiten über alle Maschinen und Aufträgen definiert.
S=j=1ni=1mSj;i
 
 


Bild 6: Beispiel für ein auftragsorientiertes Gantt-Diagramm.

In Bild 6 ist ein auftragsorientiertes Gantt-Diagramm dargestellt. Neben den bereits erläuterten Zeitgrößen lassen sich hier zudem die Verspätung und die Durchlaufzeit eines Auftrags ablesen.
Das Intervall der Bearbeitung eines Auftrags von der ersten bis zur letzten notwendigen Maschine wird als Durchlaufzeit bezeichnet. Dieser Zeitabschnitt entspricht der Summe aus Bearbeitungs-, Rüst-, und Wartezeit bzw. der Spanne zwischen Auftragsfreigabe rj und geplanter Fertigstellung Fj des Auftrags.
Dj=i=1m(pj;i+Sj;i+Wj;i)=Fj-rj
Die Wartezeit macht in vielen Fällen den größten Teil der Durchlaufzeit aus, weshalb beide Kriterien als Ersatzgröße der Kapitalbindungskosten in Frage kommen. Als Zielsetzung kann die Minimierung der summierten Durchlaufzeit D, der mittleren Durchlaufzeit D oder der maximalen Durchlaufzeit Dmax  verfolgt werden. Bei gegebener Auftragsanzahl gilt, dass die Minimierung des Gesamtbetrages einer Zeitgröße äquivalent zur Minimierung des Durchschnittswertes der gleichen Zeitgröße ist (bspw. D und D ) [2].
Wird ein Auftrag j vor oder nach dem geplanten Fertigstellungstermin fj beendet, wird dies als Terminabweichung TAj bezeichnet. Die Verspätung eines Auftrags Vj  berücksichtigt nur Terminüberschreitungen, also positive Werte von TAj.
Vj=max⁡{0;TAj}
Die gesamte Verspätung V eines Belegungsplans ist dementsprechend die Summe der Verspätungen aller Aufträge. Werden nur Terminüberschreitungen berücksichtigt, zeigt sich außerdem eine Abhängigkeit zwischen Zykluszeit bzw. Durchlaufzeit und Verspätung. Daher können diese Zeitgrößen als geeignetes Ersatzkriterium zur Minimierung der Terminüberschreitungskosten verfolgt werden.
Zusammenfassend sind den bei der Belegungsplanung relevanten Kostengrößen in Bild 7 deren proportionale Zeitkriterien zugeordnet.
 
 


Bild 7:   Entscheidungsrelevante Kostengrößen in der
Belegungsplanung und deren zeitbezogene Ersatzkriterien.

Qualitative Zielkriterien umschreiben Sachziele und müssen in der Regel als Mindestanforderungen eingehalten werden. Erfüllt ein Belegungsplan die als bindende Restriktionen deklarierten Eigenschaften, wird er als zulässig bezeichnet. Die Definition, wann ein Plan zulässig ist, leitet sich aus der konkret verfolgten Planungsaufgabe ab [1, 14].
Ist bspw. ein Belegungsplan gefordert, der direkt in der Produktion umsetzbar ist, dürfen sich einerseits nicht mehrere Aufträge auf einer Maschine überlappen. Andererseits muss die im Arbeitsplan formulierte Maschinenfolge eingehalten werden. Wird zudem eine termingerechte Fertigstellung gefordert, dürfen in zulässigen Belegungsplänen die Fälligkeitstermine der Aufträge nicht überschritten werden. In der Regel werden nicht zulässige Pläne bei einer Bewertung von Belegungsplänen ausgeschlossen.
Multikriterielle Zielsetzungen
Bei der Zielsetzung von Belegungsproblemen können auch mehrere Zielkriterien verfolgt werden. Aufgrund der geringeren Komplexität gegenüber der Berücksichtigung mehrerer Zielkriterien wird bei Maschinenbelegungsproblemen in der Literatur meist nur ein (dominierendes) Ziel herangezogen. Eine Literaturanalyse von Ruiz/Vázquez-Rodríguez zu Flexible Flow Shop-Problemen zeigt, dass über 75% der untersuchten Veröffentlichungen monokriterielle Zielsetzungen verfolgen. Das am häufigsten verwendete Ziel ist dabei die Minimierung der Zykluszeit Cmax . Nur zwei Prozent der analysierten Modelle verfolgen mehr als eine Zielgröße [8].
Eine monokriterielle Zielsetzung setzt voraus, dass das Optimum mit der Berücksichtigung einer Zielgröße erreichbar ist. Alle anderen Ziele werden somit vernachlässigt. Abhängig von der Planungsphase sind jedoch bei praktischen Problemstellungen mehrere Zielkriterien relevant. Für die Maschinenbelegungsplanung mit einem kurzfristigen Planungshorizont ist bspw. eine Minimierung der Terminüberschreitungen bei gleichzeitig minimalen Rüstkosten gefordert.
Werden mehrere Zielkriterien verfolgt, können diese im Allgemeinen in drei Beziehungen zueinander stehen [15]: Zielneutralität ist für die meisten ökonomischen Probleme irrelevant. Ist eine Verbesserung eines Ziels ohne Verschlechterung eines anderen Kriteriums möglich, liegt eine Zielkomplementarität vor. In der Belegungsplanung ist jedoch die Betrachtung von Zielkonflikten von Bedeutung, wobei die Verbesserung eines Zielkriteriums nur mit einer Verschlechterung von mindestens einem anderen Kriterium verbunden ist [14, 15].
In der Literatur wird die Unvereinbarkeit der Minimierung der Durchlaufzeit bei gleichzeitiger Maximierung der Auslastung als das Dilemma der Ablaufplanung bezeichnet [5]. Durch Hinzunahme zusätzlicher Zielkriterien lässt sich dies sogar zu einem „Trilemma“ oder „Polylemma“ erweitern. Zur Lösung der angesprochenen Zielkonflikte ist es hilfreich, durch Gewichtung der einzelnen Zielgrößen eine Gesamtzielfunktion zu bilden [2].
Die Gewichtung ist im Gegensatz zum Wert der Zielgröße subjektiv und spiegelt die Rangfolge und die wertmäßige Distanz der Präferenzunterschiede der unterschiedlichen Zielkriterien wider. Mithilfe einer Definition von Gewichtungsfaktoren kann eine additive Verbindung verschiedener Teilziele zu einer übergeordneten Zielfunktion erfolgen. Dafür müssen die Gewichte λh positiv sein (λh>0; ∀h)   und sich zu Eins summieren ( h=1Hλh=1 ). Durch die Berücksichtigung mehrerer Zielgrößen ist eine Nachbildung der unternehmensspezifischen Kostenfunktion und somit bei der Belegungsplanung eine Minimierung aller ablaufbedingter Kosten möglich.
Bei der Gewichtung mehrerer Teilziele sind jedoch einige Aspekte zu berücksichtigen: Zum einen muss die Festlegung der Gewichtungsfaktoren vor Durchführung der Belegungsplanung geschehen, um eine Bevorzugung einzelner Entscheidungsalternativen zu vermeiden. Zudem besteht bei der Bestimmung der Gewichtung die Gefahr einer inkonsistenten Präferenzordnung oder der Abbildung von subjektiv wahrgenommenen Distanzen der Relevanz der Zielkriterien. Zur Gewichtung der zeitbezogenen Ersatzziele ist die Berücksichtigung von Kostengrößen hilfreich, auch wenn diese nicht vollständig ermittelbar sind [2, 9]. Alternativ können die Gewichtungsfaktoren nach einem gesamtheitlichen Vergleich oder einer Conjoint-Analyse bestimmt werden [15].

Beschreibung der Bewertungsmethodik
Unter Berücksichtigung der bisherigen Darlegungen wird im Folgenden eine allgemeine Methodik zur Bewertung alternativer Maschinenbelegungspläne entwickelt, die über den State of the Art der Literatur hinausgeht. Bewertungsmaßstab ist dabei ein Zielsystem aus mehreren Zielgrößen, die in einem Scoring-Modell bewertet werden. Dadurch kann aus einer Menge mehrerer Entscheidungsalternativen derjenige Belegungsplan ermittelt werden, der die ausgewählten Zielgrößen am besten erfüllt. Bild 8 zeigt diese Bewertungsmethodik in vier Schritten.
 


Bild 8: Schritte bei Anwendung der Bewertungsmethodik.

1. Zielsystem aufstellen
Bei der Belegungsplanung werden die übergeordneten erwerbswirtschaftlichen Ziele der Unternehmung auf ein Zielsystem aus mehreren relevanten qualitativen und quantitativen Zielkriterien heruntergebrochen. Zur Berücksichtigung von Sachzielen wird die Aufnahme von Strafpunkten in das Zielsystem empfohlen. Werden in einem Belegungsplan qualitative Zielkriterien verletzt, wird dieser mit Strafpunkten belastet, die das Bewertungsergebnis in entsprechender Höhe mindern. Bei Verletzung bindender Restriktionen kann der Belegungsplan auch gänzlich von der Bewertung ausgeschlossen werden. Die quantitativen Zielkriterien ersetzen die für das Unternehmen bedeutsamen ablaufbedingten Kosten, die in der Belegungsplanung durch leicht quantifizierbare, gewichtete Zeitkriterien abgebildet werden. Das Zielsystem besteht somit aus mehreren relevanten Kriterien, die durch Gewichtungsfaktoren und Strafpunkte berücksichtigt werden (siehe Bild 9).
 


Bild 9: Ausgestaltung des Zielsystems.

2. Ergebnisse der Kriterien ermitteln und normieren
Liegen mehrere alternative Belegungspläne vor, werden die Ergebnisse der verschiedenen Zielkriterien für jeden Plan ermittelt. Um Skalenunterschiede der Werte auszugleichen, werden aus den absoluten Ergebniswerten für jedes der zu minimierenden quantitativen Zielkriterien Zielerreichungsgrade berechnet. Die Berechnung des Zielerreichungsgrades erfolgt gemäß nachstehender Formel [11].
Eh(y)=ehmax-eh(y)ehmax-ehmin
Der Zielerreichungsgrad ist im abgeschlossenen Intervall [0,1] definiert und nimmt den Wert 1 an, wenn gilt: eh=ehmin . Die Werte ehmax bzw. ehmin als obere bzw. untere Schranken ergeben sich entweder aus den Maximal- bzw. Minimalwerten der absoluten Ergebnisse der ermittelten Belegungspläne oder können individuell festgelegt werden (z. B. als ein maximal akzeptierbares Ergebnis der Verspätung) [11]. Aus den ermittelten qualitativen Zielkriterien können zudem für jeden Belegungsplan, gemäß der Festlegung im Zielsystem, ggf. Strafpunkte bestimmt werden.

3. Zielfunktionswert berechnen
Um alternative Belegungspläne miteinander vergleichen zu können, ist ein geeigneter Maßstab notwendig. Dazu werden zunächst die ermittelten Werte der Zielerreichung mit den Gewichtungsfaktoren des jeweiligen Zielkriteriums multipliziert.
Ey=h=1Hλh∙Ehy
Der erreichte gewichtete Zielfunktionswert Ey  ist ein Maß, wie gut ein Belegungsplan die quantitativen Zielkriterien erfüllt. Jedoch ist damit die Zulässigkeit bzw. die Erfüllung von Mindestanforderungen nicht garantiert. Um auch die qualitativen Größen des Zielsystems zu berücksichtigen, müssen vom gewichteten Zielfunktionswert ggf. noch Strafpunkte abgezogen werden.
Zy=max⁡(0;Ey∙100-q=1Qκq(y))
Der gewichtete Zielfunktionswert wird zur Erhöhung der Auflösung mit dem Faktor 100 multipliziert, um auch nah beieinanderliegende Belegungspläne zu unterscheiden. Somit kann für die alternativen Belegungspläne eine dimensionslose normierte Vergleichsgröße berechnet werden, die sowohl qualitative als auch quantitative Zielkriterien berücksichtigt. Der gewichtete Zielfunktionswert nimmt Werte zwischen 0 und 100 an. Durch den Abzug von Strafpunkten mögliche negative Werte finden keine Berücksichtigung. Der minimale Zielfunktionswert beträgt 0.

4. Rangfolge der Belegungspläne bilden
Mithilfe des gewichteten Zielfunktionswertes als Vergleichsgröße können die alternativen Belegungspläne gemäß ihrer Zielerreichung geordnet werden. Der Belegungsplan mit dem höchsten Zielfunktionswert aller bewerteten Pläne ist dementsprechend die zu präferierende Alternative, die den zulässigen Plan mit den minimalen ablaufbedingten Kosten darstellt. Die beschriebene Bewertungsmethodik ist somit ein Werkzeug zur Entscheidungsunterstützung in der Maschinenbelegungsplanung.
 
Abbildung und Lösung von realen Maschinenbelegungsproblemen
Reale Maschinenbelegungsprobleme mit mehrstufigen Produktionssystemen und heterogenem Maschinenpark, auf dem ein großer Auftragsbestand einzuplanen ist, lassen sich mit den in der Literatur betrachteten formalen Modellen meist nicht lösen [7]. Zudem werden in der Praxis i. d. R. keine optimalen, sondern gute zulässige Lösungen gefordert, die sich schnell ermitteln lassen und somit flexibel an kurzfristige Ereignisse anpassbar sind [13]. Daher ist es sinnvoll, eine Belegungsplanung an einem Modell durchzuführen und so gewonnene Erkenntnisse auf das Ausgangsproblem zurückzuführen.
Nachfolgend wird ein allgemeiner Ansatz dargestellt, wie sich mehrstufige Maschinenbelegungsprobleme mit parallelen Maschinen unter Berücksichtigung praxistypischer Restriktionen abbilden und lösen lassen.

Zielsetzung und Vorgehensweise
Das im Folgenden dargestellte allgemeine Modell zur Ermittlung von zulässigen und hinsichtlich ablaufbedingter Kosten optimierter Belegungspläne für den Einsatz in der betrieblichen Praxis ist auf eine Vielzahl unterschiedlicher mehrstufiger Produktionssysteme anwendbar. Dazu wird, angelehnt an [4], eine Abbildung von Maschinenbelegungsproblemen durch die folgenden Modellbestandteile vorgeschlagen (siehe Bild 10).


Bild 10: Modellbestandteile zur Abbildung
von Maschinenbelegungsproblemen.

Die Kundenbedarfe mit terminierten Fertigungsaufträgen werden im Lastmodell als Kapazitätsnachfrage abgebildet und stellen im Planungszeitraum eine Belastung des Kapazitätsangebots des Produktionssystems dar. Im Ressourcen- und Produktmodell werden relevante Eigenschaften und Rahmenbedingungen der betrachteten Produktionsumgebung abgebildet. Das Die Möglichkeit zur Anmeldung haben Sie auf http://veranstaltungen.gito.de/Anmeldung-I40-Anwenderkonferenz2017zu den zur Verfügung stehenden Ressourcen. Durch die Definition des Zielsystems wird die Optimierungsrichtung festgelegt.
Dazu wird zunächst ein Katalog relevanter Charakteristika betrachteter Produktionssysteme aufgestellt und Annahmen für die Modellbildung definiert. Ausgehend von der Klasse der Flexible Flow Shop-Probleme werden schrittweise praxistypische Rahmenbedingungen abgebildet. Die Ausführungen werden durch die Formulierung eines heuristischen Planungsmodells zur Lösung realer Maschinenbelegungsprobleme komplettiert.

Modellannahmen
In einem mehrstufigen Produktionssystem sollen die zu fertigenden Artikel eine vorgegebene Operationenfolge (Maschinenfolge) und einen schleifenfreien, kontinuierlichen Materialfluss haben. Die einzelnen Fertigungsstufen sollen untereinander keine zeitliche Bindung besitzen. Das Produktionssystem wird durch Kundenbedarfe in Form von terminierten Fertigungsaufträgen belastet. Darüber hinaus sollen bei der Abbildung der charakterisierten Produktionssysteme folgende praxistypische Rahmenbedingungen berücksichtigt werden:
Zwischen den Fertigungsstufen werden Zwischenerzeugnisse in Entkopplungspuffern gelagert. Die Kapazitäten dieser Puffer sind beschränkt.
Auf mindestens einer Fertigungsstufe kann ein Arbeitsgang von mehreren parallelen Maschinen durchgeführt werden. Die Fertigungsgeschwindigkeiten der parallelen Maschinen auf den Fertigungsstufen sind heterogen.
Zur Vorbereitung der Produktion eines Artikels sind Rüstvorgänge notwendig. Die Dauer dieser Rüstvorgänge kann von der Wahl der Maschine und der Auftragsfolge abhängig sein.
Die Auswahl von Maschinenalternativen auf den Fertigungsstufen kann durch zusätzliche Restriktionen beschränkt sein.
Neben den genannten Rahmenbedingungen wird außerdem von statischen und deterministischen Maschinenbelegungsproblemen ausgegangen. Alle Aufträge und Maschinen sind von Anfang an und über die gesamte Planungsperiode verfügbar. In der Realität liegen durchaus dynamische und stochastische Problemstellungen vor, die bspw. durch ein laufendes Eintreffen neuer Aufträge oder durch das stochastische Auftreten von Maschinenausfällen gekennzeichnet sind [7]. Allerdings würde eine Reaktion auf jede Änderung zu einer zu hohen Planungsfrequenz führen.

Flexible Flow Shop-Probleme
Das Modell des Flexible Flow Shop (FFS) stellt den Ausgangspunkt für die nachfolgenden Betrachtungen dar, da Produktionssysteme dieser Struktur in der industriellen Praxis häufig zu finden sind. Eine Menge an Aufträgen ( j=1,..,n ), bestehend aus mehreren Arbeitsgängen, ist dabei auf m Fertigungsstufen ( i=1,…m ) zu bearbeiten. Gegenüber regulären Flow Shop-Problemen sind hier zusätzliche Zuordnungsentscheidungen darüber zu treffen, auf welcher der parallelen Maschinen ein Arbeitsgang ausgeführt wird. Unter FFS-Problemen werden in der Literatur unterschiedliche Varianten von Maschinenbelegungsproblemen zusammengefasst, die die vier folgenden gemeinsamen Merkmale besitzen [8, 16]:
(1)  Das betrachtete Produktionssystem besteht aus mehreren Fertigungsstufen (m≥2).
(2)  Jede Fertigungsstufe i hat M(i)≥1 Maschinen, wobei auf mindestens einer Stufe M(i)>1 gilt.
(3)  Die zu bearbeitenden Aufträge j sind in der vorgeschriebenen Maschinenfolge auf den unterschiedlichen Fertigungsstufen zu bearbeiten (identischer Materialfluss). Ein Auftrag kann dabei eine oder mehrere Stufen überspringen, muss aber zumindest auf einer bearbeitet werden.

Jeder Auftrag j benötigt eine Bearbeitungszeit pj;i  auf der Fertigungsstufe i . Die Bearbeitung von Auftrag j auf der Stufe i wird als Vorgang oj;i bezeichnet.


Bild 11: Struktur eines Flexible Flow Shop-Problems.

Bild 11 zeigt beispielhaft ein Produktionssystem, das nach den Merkmalen des FFS beschrieben werden kann. FFS-Probleme bilden die Struktur vieler industrieller Produktionssysteme ab, worin ein Auftrag bestehend aus mehreren Vorgängen nacheinander auf mehreren Fertigungsstufen mit parallelen Maschinen gefertigt wird und jede Maschine nur einen Vorgang zur gleichen Zeit ausführen kann. In theoretischen Veröffentlichungen zur Maschinenbelegungsplanung werden zudem folgende, für eine praktische Anwendung partiell ungeeignete, Annahmen getroffen [16]:
·  Alle Aufträge und Maschinen sind zu Beginn der Planungsperiode verfügbar.
·  Bei den Maschinen auf jeder Stufe handelt es sich um identische parallele Maschinen.
·  Jeder Auftrag kann zur gleichen Zeit nur von einer Maschine bearbeitet werden.
·  Rüstzeiten sind vernachlässigbar.
·  Die Unterbrechung von Aufträgen ist nicht erlaubt.
·  Die Zwischenlagerkapazitäten sind unbegrenzt.
·  Aufträge verlassen nach ihrer Fertigstellung das System bzw. werden direkt ausgeliefert. Fertigteillager werden damit nicht berücksichtigt.
Da sich praktische Belegungsprobleme nur selten mit der dargestellten Standardform beschreiben lassen, soll im Folgenden das formale Modell des FFS sukzessive durch die Abbildung praxistypischer Rahmenbedingungen erweitert werden, um auch reale Produktionssysteme beschreiben zu können.

Berücksichtigung von begrenzten Entkopplungspuffern
Anders als in der Standardform des FFS angenommen, existieren in realen Produktionssystemen meist keine unbegrenzten Kapazitäten der Puffer zwischen den jeweiligen Fertigungsstufen. Begrenzt wird die Zwischenlagerkapazität besonders bei der Produktion von voluminösen Gütern dadurch, dass nur beschränkte Flächen oder eine endliche Anzahl an Stellplätzen zur Lagerung der Zwischenerzeugnisse verfügbar sind [7]. Aus dieser Flächenrestriktion ergibt sich eine maximale Menge der Artikel, die in dem Puffer zwischen zwei Fertigungsstufen gelagert werden können ( Bj;i ).
Die effektive Höhe des Pufferbestandes ist eine dynamische Größe. Die Artikelmenge eines Auftrags j  im Puffer zwischen der i -ten und (i+1) -ten Stufe zum Zeitpunkt t wird mit bj;it  bezeichnet. Die Berechnung des Entkopplungspufferbestandes erfolgt rekursiv aus der vorhergehenden Teilperiode t-1 . Die jeweilige Bestandsänderung ergibt sich aus den Zugängen der vorgelagerten und den Abgängen der nachgelagerten Fertigungsstufe:
bj;it=bj;it-1+zj;it-aj;i+1t≤Bj;i

Der Pufferzugang zj;it beträgt 1, wenn ein Artikel von der Stufe i in den Puffer transportiert wird. zj;it  nimmt dagegen größere Werte an, wenn Artikelbündel (z. B. volle Ladungsträger) betrachtet werden oder Artikel von mehreren parallelen Maschinen auf Stufe i stammen. Abgänge aj;i+1t  entstehen dementsprechend, wenn auf der Stufe i+1 Artikel oder Artikelbündel zur Bearbeitung von Auftrag j  bzw. des Vorgangs oj;i+1 benötigt werden. Voraussetzung dafür ist ein hinreichend großer Bestand im Entkopplungspuffer bj;it≥aj;i+1t . Mit bj;it=0  lassen sich zudem Anfangsbestände berücksichtigen. In diesem Beitrag wird von einem wahlfreien Zugriff auf die Artikel im Entkopplungspuffer ausgegangen.
Durch Bestandskurven lassen sich die zeitlichen Verläufe der Entkopplungsbestände visualisieren. Typisch sind sägezahnartige Bestandsverläufe. Die Steigung der Zu- und Abgänge ist von den Fertigungsgeschwindigkeiten auf den jeweiligen Stufen abhängig.

Losteilung, Lossplittung und Losüberlappung
In Standardmodellen zur Maschinenbelegungsplanung wird angenommen, dass ein Auftrag komplett und ohne Unterbrechung auf einer Stufe gefertigt werden muss, bevor die Bearbeitung dieses Auftrags auf der nächsten Stufe beginnen kann (geschlossener Lostransport) [17]. Dies führt dazu, dass sich die Zwischenlagerbestände auf ein Maximum aufbauen, das dem vollständigen Auftragsbestand entspricht, bevor diese abgebaut werden können.
Zur Senkung der maximalen Entkopplungspufferbestände und zur Verkürzung der Durchlaufzeit ist eine stufenüberlappende Fertigung vorzuziehen. Dazu müssen drei Begriffe unterschieden und definiert werden [17].
Unter Losteilung wird die Aufteilung eines Auftrags in kleinere Quantitäten (Teillose, Transportlose) verstanden, die voneinander zeitlich getrennt bearbeitet werden können. Die Bearbeitung eines Auftrags auf einer Maschine kann dazu unterbrochen werden.
Lossplittung (lot splitting) bezeichnet die simultane Bearbeitung von Teillosen des gleichen Auftrags auf parallelen Maschinen. Einer Verringerung der Durchlaufzeit steht hierbei jedoch ein höherer Rüstaufwand gegenüber [12].
Durch Losüberlappung (lot streaming) können Lose stufenüberlappend gefertigt werden. Das heißt, dass mit der Bearbeitung eines Teils des Loses bereits begonnen wird, ohne dass die Fertigung der Gesamtmenge dieses Loses auf der vorgelagerten Stufe beendet ist (partieller Lostransport) [12].
Die Bestimmung der Anzahl an Teillosen und deren Dimensionierung stellt eine zusätzliche Planungsaufgabe dar und hat einen entscheidenden Einfluss auf die Höhe der Entkopplungsbestände sowie auf die Durchlaufzeit eines Auftrags [17].

Heterogene parallele Maschinen
In der Standardform des FFS werden identische parallele Maschinen betrachtet, wobei ein Vorgang auf jeder Maschine die gleiche Bearbeitungszeit hat. In realen Produktionssystemen kommen jedoch für den gleichen Vorgang unterschiedlich effiziente Maschinen zum Einsatz. Ältere, weniger effiziente Maschinen, benötigen für die Bearbeitung des gleichen Vorgangs mehr Zeit als eine moderne Maschine, werden aber aufgrund hoher Wiederbeschaffungskosten weiter betrieben.
Zur Abbildung unterschiedlich schnell arbeitender Maschinen werden im Folgenden heterogene parallele Maschinen betrachtet. Die Fertigungsgeschwindigkeit, mit der ein Vorgang ausgeführt wird, ist dabei nicht nur von dem zu fertigenden Auftrag, sondern auch von der Maschine, auf der der Vorgang bearbeitet wird, abhängig. Im Standard-FFS beschreibt pj;i die Bearbeitungszeit des Auftrags j auf der Stufe i. Bei heterogenen parallelen Maschinen wird die Bearbeitungszeit um den Index der parallelen Maschine k(i) erweitert. Zur Erfassung der unterschiedlichen Bearbeitungszeiten aller Aufträge wird eine zusammenfassende Darstellung in Form einer Bearbeitungszeitmatrix pro Fertigungsstufe vorgeschlagen.
Die Bearbeitungszeitmatrix Pj;i  umfasst die unterschiedlichen Bearbeitungszeiten pj;i;k(i)  der M(i) parallelen Maschinen ( k(i)=1,…, M(i) ) auf Stufe i :
Pj;i=p1;i;1…p1;i;M(i)⋮⋱⋮pn;i;1…pn;i;M(i)

Reihenfolgeabhängige Rüstzeiten
Wird eine Maschine zur Bearbeitung mehrerer Aufträge unterschiedlicher Artikel verwendet, müssen oft Rüstvorgänge in Form von Werkzeugwechseln oder Reinigungsprozessen vollzogen werden. Da das Rüsten mit einem erhöhten Ressourcen- bzw. Personaleinsatz und einem temporären Stillstand der Maschine verbunden ist, verursacht jeder Rüstvorgang Kosten. Diese Rüstkosten gilt es im Zuge einer optimierenden Maschinenbelegungsplanung zu minimieren.
Rüstzeiten werden als eine Erweiterung der Bearbeitungszeiten modelliert und können für jede Fertigungsstufe in einer Rüstmatrix Rj*;j;i abgebildet werden, wobei j* für den Auftrag steht, der vor der Bearbeitung von Auftrag j auf der Maschine gerüstet war. Der Rüstvorgang zwischen zwei Aufträgen für identische Artikel ist in der Regel nicht zu berücksichtigen ( Sj*=j;j;i=0 ).
Rj*;j;i=0⋯S1;n;i⋮⋱⋮Sn*;1;i⋯0
Für den Fall, dass Rüstzeiten nicht nur von der Auftragsfolge, sondern auch von der betrachteten parallelen Maschine abhängig sind, wird die Notation der Rüstzeiten um den Index der parallelen Maschine k(i) erweitert. In diesem Fall muss für jede Maschine eine Rüstmatrix Rj*;j;k(i);i aufgestellt werden.

Beschränkung von Maschinenalternativen
Das Modell des FFS umfasst Produktionssysteme, bei denen zur Bearbeitung eines Vorgangs mehrere parallele Maschinen auf einer Fertigungsstufe zur Verfügung stehen. Jeder Artikel kann dabei auf alternativen Maschinen produziert werden. Die Anzahl von Maschinenalternativen kann in realen Problemstellungen jedoch beschränkt sein [1]. Zur Abbildung von Produktionssystemen mit einer beschränkten Anzahl von alternativen Maschinen pro Artikel wird die Einführung der Binärvariablen xj;i;k(i)  vorgeschlagen. Ist die Bearbeitung des Auftrags j auf der Maschine k(i) auf der Stufe i nicht möglich, gilt xj;i;k(i)=0 . Die Fertigungsmatrix Xj;i liefert eine zusammenfassende Darstellung welche Aufträge auf welchen parallelen Maschinen einer Fertigungsstufe bearbeitet werden können: 
Xj;i=x1;i;1…x1;i;M(i)⋮⋱⋮xn;i;1…xn;i;M(i)
Die Ursachen für eine Beschränkung der Maschinenalternativen können vielfältig sein. Einerseits ist denkbar, dass die Bearbeitung eines Vorgangs auf einer Teilmenge der parallelen Maschinen aufgrund von technischen Gegebenheiten, z. B. durch den Einsatz von verschiedenen Maschinentypen oder Werkzeugträgern, nicht möglich ist. Andererseits können einzelne Maschinen durch den Planer ausgeschlossen werden, wenn die Produktion eines Artikels auf diesen Alternativen zwar möglich, jedoch wegen eines hohen Ressourceneinsatzes oder einer langen Bearbeitungszeit unwirtschaftlich ist. Auch eine Mehrmaschinenbedienung kann in Form einer Fertigungsmatrix abgebildet werden.

Entwurf eines heuristischen Planungsmodells zur Lösung realer Maschinenbelegungsprobleme
Zur Ermittlung von zulässigen Belegungsplänen unter Beachtung der o. g. praxistypischen Restriktionen soll nun ein heuristisches Verfahren entwickelt werden. Dazu sind zunächst einige vorangestellte Bemerkungen zur Bewertung von Maschinenalternativen nötig.
Unterschiedliche Bearbeitungs- und Rüstzeiten sowie eine Einschränkung der Belegungsalternativen machen eine Bewertung der zur Auswahl stehenden parallelen Maschinen erforderlich.
Im Folgenden soll aus den o. g. Kriterien eine Formel zur Bewertung der parallelen Maschinen auf einer Fertigungsstufe entwickelt werden, womit die Auswahl der optimalen Alternative in der Belegungsplanung erleichtert wird. Eine Bewertung hinsichtlich mehrerer Kriterien ist hier sinnvoll, da bspw. der Vorteil einer geringeren Bearbeitungszeit durch eine längere notwendige Rüstzeit aufgehoben werden kann. Zur Bewertung der Maschinenalternativen wird deshalb der frühestmögliche Fertigstellungszeitpunkt des betrachteten Auftrags herangezogen. Dazu wird ein Auftrag probeweise auf allen alternativen Maschinen eingeplant und anschließend die Alternative mit dem frühesten möglichen Fertigstellungszeitpunkt ausgewählt, der von vier Faktoren abhängt:
·  dem einzuplanenden Auftrag j,
·  der Fertigungsstufe i, auf der die Bewertung durchgeführt wird,
·  der zur Bewertung herangezogenen Maschine k(i) und
·  dem vorher geplanten Auftrag j* auf Maschine k(i) .
Die Berechnung des frühesten möglichen Fertigstellungszeitpunktes F*j;i;k(i);j*  erfolgt gemäß der nachstehenden Formel:
F*j;i;k(i);j*=xj;i;k(i)∙(A*j;i;ki;j*+Sj*;j;i+pj;i;ki∙uj )
A*j;i;ki;j*  beschreibt den frühesten möglichen Anfangszeitpunkt auf Maschine k(i) . Die Auswahl fällt auf die Belegungsalternative mit dem frühesten möglichen Fertigstellungszeitpunkt, wobei gelten muss: F*j;i;k(i);j*>0 , um die nicht möglichen Alternativen mit xj;i;k(i)=0 auszuschließen. Werden mehrere Maschinenalternativen identisch bewertet, ist die Auswahl der Alternative arbiträr.
Zur Lösung realer Maschinenbelegungsprobleme wird auf ein heuristisches Verfahren zurückgegriffen, das mit einer endlichen Anzahl an Rechenschritten zu einer zulässigen Lösung führt. Das Ziel dabei ist, durch mehrmaliges Ausführen der Prozedur mit unterschiedlichen Einlastungsreihenfolgen verschiedene Belegungspläne zu erzeugen. Unter diesen Entscheidungsalternativen wird anschließend die hinsichtlich eines Zielsystems optimale Lösung ausgewählt.
Zunächst werden die Voraussetzungen zur Anwendung des Planungsmodells definiert: Neben einer vollständigen Abbildung des untersuchten Produktionssystems in einem Produkt- und Ressourcenmodell müssen auch sämtliche Aufträge, die das Lastmodell bilden, für den gesamten Planungszeitraum bekannt sein. Diese Aufträge konkurrieren um die begrenzten Maschinenkapazitäten. Daher ist eine Menge an Prioritätsregeln erforderlich, um unterschiedliche Einlastungsrangfolgen der Aufträge zu bilden. Zur Bewertung der ermittelten Belegungspläne ist außerdem eine Menge an Kriterien zu wählen, die zusammen das Zielsystem bilden.
Sind alle notwendigen Inputs bekannt, wird für jede Prioritätsregel ein Planungslauf durchgeführt und somit ein Belegungsplan ermittelt. Dazu werden zunächst die Aufträge nach ihrem Prioritätswert geordnet. Beginnend mit dem am höchsten bewerteten Auftrag wird jeder Auftrag gemäß der ermittelten Rangfolge eingeplant. Da dieses Planungsmodell mehrstufige Produktionssysteme betrachtet, besteht ein Auftrag aus mehreren Vorgängen. Ein Vorgang kann auf mehreren parallelen Maschinen auf einer Fertigungsstufe bearbeitet werden. Zur Auswahl, auf welcher der alternativen Maschinen ein Vorgang bearbeitet wird, findet die in Abschnitt 5.5.1  erläuterte Formel zur Bewertung von Maschinenalternativen Anwendung. Zusätzlich muss für jeden Vorgang geprüft werden, ob die Bearbeitung auf den Maschinenalternativen hinsichtlich der begrenzten Kapazitäten der Entkopplungspuffer zulässig ist. Letztendlich wird zur Bearbeitung des betrachteten Vorgangs die am besten bewertete zulässige Alternative gewählt. Befindet sich unter den parallelen Maschinen keine zulässige Alternative, kann der Vorgang nur unter Verletzung der Bestandsrestriktion bearbeitet werden. Daher wird in diesem Fall der Auftrag in der Einlastungsreihenfolge zurückgestellt und entsprechend mit dem nächsten Auftrag fortgefahren.
Nachdem auch der in der Rangfolge letzte Auftrag auf allen Fertigungsstufen eingeplant ist, wird der ermittelte Belegungsplan nach den im Zielsystem enthaltenen Kriterien bewertet. Mit der Bewertung der Lösung ist der Planungslauf für die betrachtete Prioritätsregel abgeschlossen. Dieser Planungslauf wird so oft wiederholt, bis für jede Prioritätsregel ein bewerteter Belegungsplan vorliegt. Für jede der Entscheidungsalternativen wird anschließend mit der beschriebenen Bewertungsmethodik ein Zielfunktionswert ermittelt. Dieser wird als Vergleichswert verwendet, wodurch der hinsichtlich des Zielsystems optimale Belegungsplan aus dem Entscheidungsfeld ausgewählt werden kann.
In Bild 12 ist das oben beschriebene Verfahren als Flussdiagramm zusammengefasst. Das aufgestellte Planungsmodell hat als heuristisches Verfahren nicht die Berechnung einer optimalen Lösung für ein spezifisches Belegungsproblem zum Ziel. Vielmehr können durch diese allgemeine Methode zulässige Lösungen für eine Vielzahl von verschiedenartigen Problemen ermittelt werden. Ebenfalls ist es über eine Anpassung der Kriterien des Zielsystems möglich, die jeweiligen Zielvorgaben für die Belegungsplanung zu variieren.
 


Bild 12: Flussdiagramm des heuristischen Planungsmodells.

Mehrstufige Maschinenbelegungsplanung an einem realen Anwendungsbeispiel
Im Folgenden soll das oben aufgestellte Modell zur Abbildung von Maschinenbelegungsproblemen mithilfe einer Simulationsuntersuchung an einem realen Planungsproblem verifiziert werden. Die Simulation wurde mit dem APS-System Asprova® [18] ausgeführt.

Problembeschreibung
In diesem Abschnitt wird ein reales Maschinenbelegungsproblem eines Zulieferunternehmens betrachtet, in dem Komponenten aus Dämmschaum produziert werden. Der Herstellungsprozess gliedert sich in die drei Arbeitsgänge Hartschaum, Weichschaum und einen abschließenden Beschnitt (siehe Bild 13). Die Fertigungsstufen werden von den zu produzierenden Artikeln in identischer Abfolge schleifenfrei durchlaufen. Einige Artikel lassen einzelne Arbeitsgänge aus, jedoch werden alle Artikel auf mindestens einer Fertigungsstufe bearbeitet. Auf den Fertigungsstufen Hartschaum und Weichschaum stehen identische parallele Maschinen zur Verfügung. Bei dem abschließenden Beschnitt handelt es sich um heterogene parallele Maschinen. Auf allen Stufen ist die Maschinenauswahl aufgrund technischer Gegebenheiten eingeschränkt. Darüber hinaus ist die Verwendung artikelspezifischer Werkzeuge notwendig.
Zwei aufeinanderfolgende Fertigungsstufen sind jeweils durch Entkopplungspuffer voneinander getrennt. Da für diese Puffer nur eine begrenzte Fläche zur Verfügung steht, kann nur eine begrenzte Anzahl an Artikeln zwischengelagert werden. Es liegt somit ein Flexible Flow Shop-Problem mit beschränkten Zwischenlagerkapazitäten vor.
 


Bild 13: Struktur des Produktionssystems im Anwendungsbeispiel.

Planungsaufgabe und Zieldefinition
Ausgehend von dieser Problembeschreibung lassen sich folgende Planungsaufgaben ableiten: Für das beschriebene Produktionssystem sollen in einer definierten Planungsperiode die Kundenbedarfe termin- und mengengerecht erfüllt werden. Bei der Maschinenbelegungsplanung sind die Rahmenbedingungen der Produktionsumgebung zu beachten (Einhaltung der Maschinenfolgen, Mehrmaschinenbedienung, Flächenrestriktionen, Werkzeuge …). Es sollen unterschiedliche zulässige Belegungspläne ermittelt werden, die direkt in der Produktion ausführbar sind.

Des Weiteren werden für die Maschinenbelegungsplanung zusätzliche Annahmen getroffen. Das Lastmodell ist durch Kundenbedarfe vorgegeben und schon zu Beginn der Planungsperiode vollständig bekannt. Das Unternehmen hat eine hohe Belastung durch Strafkosten infolge verspäteter Lieferungen. Hohe Zwischenproduktbestände und häufige Rüstvorgänge zeigen zudem die mangelnde Abstimmung der einzelnen Fertigungsstufen. Folglich strebt das Unternehmen eine Minimierung der ablaufbedingten Kostenarten Terminabweichungs-, Kapitalbindungs- und Rüstkosten an.
Um die Erfüllung der Planungsaufgaben messbar zu machen, wird zunächst ein Zielsystem aufgestellt, wonach die erzeugten Belegungspläne bewertet werden können. Die Ausführbarkeit der Belegungspläne und die Beachtung der Kapazität der Entkopplungspuffer werden als qualitative Kriterien in das Zielsystem aufgenommen. Mithilfe von quantitativen Kriterien als zeitbezogene Ersatzziele sollen die o. g. ablaufbedingten Kostengrößen berücksichtigt werden (siehe Bild 14).
 
 


Bild 14: Zielsystem im Anwendungsbeispiel.

Die Bewertung der Belegungspläne erfolgt gemäß Abschnitt 4.2 mit einem Zielfunktionswert, der mithilfe von Zielerreichungsgraden der quantitativen Kriterien berechnet wird. Jedes dieser Kriterien wird mit einem Gewichtungsfaktor versehen, der anhand des Verhältnisses der jeweiligen Kostensätze ermittelt wurde. Da für den betrachteten Zulieferer Konventionalstrafen infolge von verspäteten Lieferungen die kostenmäßig größte Belastung darstellen, werden die Terminabweichungskosten mit der höchsten Gewichtung von 0,5 bewertet. Kapitalbindungskosten stellen den zweitgrößten Kostenblock dar und werden mit dem Faktor 0,3 gewichtet. Rüstkosten gehen mit dem Faktor 0,2 in das Gesamtergebnis ein. Zur besseren Auswertbarkeit der Zielerreichungsgrade wurden im Vorfeld der Belegungsplanung Maximalwerte der einzelnen quantitativen Kriterien definiert. Bei Überschreitung dieser Obergrenzen erhält der Belegungsplan für das entsprechende Kriterium einen Zielerreichungsgrad von 0.
Bei der Berechnung des Zielfunktionswertes spielen auch eventuelle Strafpunkte bei Nichterfüllung der qualitativen Kriterien eine Rolle. Demnach werden in diesem Beispiel nicht ausführbare Belegungspläne mit 100 Strafpunkten belastet, damit nur in der Produktion umsetzbare Pläne als beste Entscheidungsalternative in Betracht kommen. Die Belastung für den Zulieferer infolge hoher Entkopplungspufferbestände wird ebenfalls mit Strafpunkten berücksichtigt. Dazu ist nicht nur die qualitative Aussage, ob ein Belegungsplan die Bestandsrestriktion verletzt, relevant, sondern auch die Höhe der Überschreitung der Restriktion. Das Maß für die Entkopplungsbestände ist die maximale Behälteranzahl während des Planungslaufes. Die Strafpunkte werden ebenfalls über einen Zielerreichungsgrad berechnet und liegen je nach Höhe der Bestandsüberschreitung in einem linksoffenen Intervall zwischen 0 und 50. Ein Belegungsplan erhält keine Strafpunkte, wenn der Maximalwert der Summe der Entkopplungsbestände kleiner als der festgelegte Wert der Bestandsrestriktion ist. Mit den maximalen Strafpunkten (50) wird die Entscheidungsalternative belastet, die eine definierte maximale Überschreitung der Restriktion übersteigt.

Aufbau des Simulationsmodells
Zur Durchführung der Simulationsuntersuchungen erfolgt zunächst die Abbildung des realen Produktionssystems des Unternehmens in einem Produkt- und Ressourcenmodell. Die Kundenbedarfe, die um das Kapazitätsangebot der verfügbaren Maschinen des Produktionssystems konkurrieren, werden in einem Lastmodell abgebildet.
Das Produkt- und Ressourcenmodell dient zur Abbildung relevanter Merkmale und Stammdaten des realen Produktionssystems. Welcher Artikel auf welcher Maschine gefertigt werden kann, zeigt die Fertigungsmatrix, in der die Artikel zeilenweise und die Maschinen spaltenweise aufgelistet werden. Die Elemente einer Zeile nehmen den Wert 1 an, wenn die Bearbeitung eines Artikels auf einer betreffenden Maschine möglich, bzw. erhalten den Wert 0, wenn die Bearbeitung nicht möglich ist. Sind für einen Artikel alle parallelen Maschinen einer Fertigungsstufe mit 0 bewertet, wird der entsprechende Arbeitsgang gemäß Arbeitsplan übersprungen.
Zur Erfassung der Bearbeitungszeiten der Artikel wird eine Bearbeitungszeitmatrix ausgefüllt. Die parallelen Maschinen der Stufen „Hartschaum“ und „Weichschaum“ werden hier jeweils in einer Spalte zusammengefasst, da es sich um identische parallele Maschinen mit einheitlichen Bearbeitungszeiten handelt.
Zur Bearbeitung eines Vorgangs werden auf allen drei Stufen artikelspezifische Werkzeuge als Produktionshilfsmittel benötigt. Es steht für jeden Artikel nur eine begrenzte Anzahl an Werkzeugen zur Verfügung. Die bei Werkzeugwechsel notwendigen Rüstzeiten sind in diesem Beispiel artikel- und reihenfolgeunabhängig sowie auf allen Maschinen einer Fertigungsstufe identisch. Folglich muss keine Rüstmatrix aufgestellt werden.
Die Kapazitäten der Zwischenpuffer sind durch die Platzverhältnisse innerhalb der Produktionsanlagen des Zulieferers begrenzt. Die maximale Anzahl einer Behälterart im Entkopplungspuffer leitet sich aus der Anzahl der zur Pufferung vorgesehenen Stellplätze und dem Stapelfaktor her.
Das definierte Produkt- und Ressourcenmodell wird im Planungszeitraum durch Kundenbedarfe belastet. Die Bedarfsmengen sind in Aufträge mit unterschiedlichen Fälligkeitsterminen gegliedert und bilden das Lastmodell des realen Systems ab. Alle Aufträge liegen zu Planungsbeginn vollständig vor und werden als nicht veränderlich angenommen. Es wird somit ein statisches und deterministisches Problem untersucht
Um die Durchführbarkeit der Belegungspläne auch bei ungeplanten Produktionsunterbrechungen zu garantieren und damit der Planungsaufgabe gerecht zu werden, wird für jeden Auftrag ein Eskalationsspielraum von sechs Stunden berücksichtigt. Das heißt, dass der geplante Fertigstellungstermin jedes Auftrags um mindestens diesen Zeitraum vor dem im Lastmodell fixierten Fälligkeitstermin liegen muss.

Durchführung der Simulation
Die nachfolgende Untersuchung dient der Planung der Maschinenbelegung eines realen mehrstufigen Produktionssystems mit dem Ziel der Ermittlung eines hinsichtlich des definierten Zielsystems optimierten Belegungsplans. Dazu werden die zusammengefassten Daten als Simulationsmodell genutzt und in eine APS-Software übertragen. Diese Software wird als Simulationswerkzeug verwendet, um durch Parametervariationen Entscheidungsalternativen zu generieren.
Zur Erfüllung der Planungsaufgabe ist aufgrund der hohen Komplexität des abgebildeten Produktionssystems ein automatisiertes Planungsmodell erforderlich. Daher wird zur Generierung alternativer Belegungspläne die APS-Software Asprova ®  eingesetzt. Die Planungslogik der Software lässt sich durch eine Vielzahl vom Benutzer einstellbarer Parameter anpassen. Die wichtigsten sind nachfolgend zusammengefasst:
Zur Festlegung der Einlastungsreihenfolge können verschiedene Kriterien herangezogen werden bspw. der Fälligkeitstermin oder eine vom Anwender definierte Priorisierung der Aufträge.
Bei der Zuweisungsrichtung lässt sich zwischen Vorwärts- und Rückwärtsterminierung unterscheiden. Unter Zuweisungsmodus kann ausgewählt werden, ob die Maschinenkapazität begrenzt oder infinit ist.
Unter Ressourcenauswahl können entweder priorisierte Ressourcen bevorzugt oder ein Bewertungsmaßstab mit variabler Gewichtung gewählt werden.
In dieser Simulationsuntersuchung werden Parametereinstellungen verwendet, die sich in bisherigen Projekten als effizient herausgestellt haben. Diese Werte werden als Grundeinstellungen nicht variiert (siehe Bild 15).
 


Bild 15: Grundeinstellungen des Simulationswerkzeugs.

Die einzuplanenden Fertigungsaufträge werden absteigend nach ihrem Fälligkeitstermin geordnet und entsprechend dieser Reihenfolge in einer Rückwärtsterminierung den Maschinen zugewiesen. Die Planung erfolgt unter Berücksichtigung der im Simulationsmodell definierten Maschinenkapazität. Stehen bei einem Vorgang mehrere alternative Ressourcen zur Auswahl, verwendet Asprova® eine interne Ressourcenbewertung, die vom Benutzer durch eine Gewichtung von Parametern beeinflussbar ist. Bild 16 zeigt eine Übersicht der Parameter mit veränderlicher Gewichtung, sowie deren Standardeinstellung, die mit (1|1|1|1) gekennzeichnet wird. Um verschiedenartige Belegungspläne als Entscheidungsalternativen zu generieren, werden diese Gewichtungen als Stellgrößen variiert.
 


Bild 16: Standardeinstellung der Stellgrößen
des Simulationswerkzeugs.

Zunächst soll der Einfluss einzelner Parameter auf den Zielfunktionswert ermittelt werden. Dazu wird die Gewichtung jeweils eines Parameters ceteris paribus variiert und der mit dieser Einstellung generierte Belegungsplan nach der in Abschnitt 4.2 entwickelten Methodik bewertet. Unter den bewerteten Lösungen hat die Alternative mit der Kombination (0,1|1|1|1) mit 96,76 den höchsten Zielfunktionswert.
Die Abhängigkeit zwischen zwei Größen lässt sich allgemein mit einem Korrelationskoeffizienten beschreiben. Bild 17 zeigt die Korrelation zwischen der Gewichtung der Parameter und dem Zielfunktionswert.
 


Bild 17: Korrelation der veränderlichen Parameter
mit dem Zielfunktionswert.

Im vorangegangenen Abschnitt wurden lokale Maxima bei der Variation der Gewichtungen einzelner Parameter ermittelt. Ausgehend davon soll nachfolgend das Bewertungsergebnis durch die Suche von optimierten Kombinationen verbessert werden. Zunächst wird das lokale Maximum mit dem höchsten Zielfunktionswert bei (0,1|1|1|1) geprüft.
Eine Variation der Parameter C und D lieferte kein neues Maximum. Die Untersuchung des Parameters B liefert mit der Kombination (0,1|2|1|1) einen leicht erhöhten Zielfunktionswert von 97,35.
Ausgehend von der ermittelten optimierten Kombination (0,1|2|1|1) wird nun eine weitere Verbesserung des Zielfunktionswertes mit der Variation der Parameter C und D geprüft. Im analysierten Wertebereich konnte jedoch keine weitere Steigerung des Bewertungsergebnisses erzielt werden. Somit stellt die Kombination (0,1|2|1|1) für dieses Anwendungsbeispiel die optimierte Parametereinstellung dar.

Interpretation und kritische Würdigung der Ergebnisse
Die in Abschnitt 5.6.4 dargestellten Simulationsuntersuchungen mit der APS-Software Asprova® dienten der Ermittlung von Belegungsplänen zur Erfüllung der vorgegebenen Planungsaufgabe. Mithilfe der Variation von Gewichtungen der Parameter zur Ressourcenbewertung wurden 108 Entscheidungsalternativen erzeugt und anschließend anhand eines multikriteriellen Zielsystems bewertet. Dabei konnte das Primärziel einer termin- und mengengerechten Erfüllung der Kundenbedarfe bei 103 der untersuchten Kombinationen realisiert werden. Durch die Bewertung der alternativen Belegungspläne und der Berücksichtigung von Strafpunkten bei Nichterfüllung definierter Mindestanforderungen wurde außerdem eine Rangfolge der Alternativen nach der Minimierung der relevanten Zeitgrößen ermittelt. Allgemein wird unterstellt, dass mit der Reduzierung der Zeitgrößen eine gleichgerichtete Verringerung der ablaufbedingten Kosten erzielt wird. In unserem Beispiel zeigt die Reduktion der summierten Rüstzeit um 10,9 Tage bzw. 21 % sowie die Veränderung der Entkopplungsbestände die Wirkungen der Parametervariationen und damit den entscheidenden Einfluss der Wahl einer optimierten Parametereinstellung auf die Produktionskennzahlen, die bereits bei einer endlichen Anzahl von Kombinationen der Gewichtungsfaktoren in einem begrenzten Wertebereich erzielt wurde.
Darüber hinaus wurde der Einfluss der veränderlichen Gewichtungen auf das Bewertungsergebnis analysiert. Die am besten bewertete Parametereinstellung (0,1|2|1|1) hat gegenüber der Standardeinstellung einen um 24 % höheren Zielfunktionswert (siehe Bild 18).
 


Bild 18: Zusammenfassung der Ergebnisse der
Simulationsuntersuchung.

Fazit und Ausblick
Die Ausführung einer größeren Anzahl von Planungsdurchläufen und anschließender, zum Teil manueller Bewertung, erwies sich in unserem Beispiel als sehr aufwendig. Für einen praktischen Einsatz ist folglich die Anzahl der zu untersuchenden Parametervariationen zu begrenzen. Weiterhin beschleunigt eine automatisierte Bewertung der generierten Belegungspläne in der APS-Software die Optimierung erheblich.
Die realitätsgetreue Abbildung des jeweils zugrundeliegenden Produktionssystems in einem Simulationsmodell ist eine zwingende Voraussetzung für auswertbare Ergebnisse. Eine einheitliche Struktur zur Aufnahme der Eingangsdaten, bspw. durch Standardarbeitsblätter, vereinfacht die Übertragung der Datengrundlage und verbessert deren Konsistenz. Erweiterungen des Simulationsmodells sind bspw. durch die Berücksichtigung der Personalplanung, von Ausschussraten oder geplanten Maschinenausfällen durch Wartung bzw. Reinigung denkbar.
 
Im Rahmen dieses Beitrages wurde die Maschinenbelegungsplanung mehrstufiger Produktionssysteme betrachtet. Der Fokus lag dabei auf Systemen mit Rahmenbedingungen, die vor allem in der industriellen Stückgüterproduktion zu finden sind. Das Ziel bestand darin, einen praxistauglichen Ansatz zur Abbildung mehrstufiger Produktionssysteme mit praxistypischen Restriktionen zu finden und eine allgemeine Methodik zu entwickeln, nach der alternative Belegungspläne bewertet werden können.
Da in der Praxis bei einer Optimierung der Belegungsplanung mehrere Zielkriterien einzubeziehen sind, stellt ein multikriterielles Zielsystem den Bewertungsmaßstab dieser Methodik dar. Das Zielsystem besteht aus relevanten qualitativen und quantitativen Kriterien, um die verfolgten Sach- und Formalziele möglichst genau abzubilden. Zeitgrößen werden dabei als Ersatzkriterien für die zu minimierenden ablaufbedingten Kostengrößen eingesetzt. Durch die Bewertung der Zielkriterien in einem Scoring-Modell ist es so möglich, aus einem Entscheidungsfeld jenen Belegungsplan zu ermitteln, der die übergeordneten Unternehmensziele am besten erfüllt.
Zur Lösung realer Maschinenbelegungsprobleme muss das zugrundeliegende Produktionssystem in einem Modell abgebildet werden. Die in der Literatur diskutierten Modelle können aufgrund ihrer geringen Komplexität und unrealistischer Annahmen nur als Ausgangspunkt dienen. Für die Abbildung von Produktionssystemen mit Reihenfertigung und einer Menge paralleler Maschinen pro Arbeitsgang kann das Modell des Flexible Flow Shop als Basis herangezogen werden. Dieses Modell wurde durch praxistypische Rahmenbedingungen erweitert, u. a. in Form von beschränkten Entkopplungspuffern und Losteilung der Fertigungsaufträge, heterogene parallele Maschinen, reihenfolgeabhängige Rüstzeiten und Beschränkungen der Maschinenalternativen, die in Form von Matrizen abgebildet wurden.
Unter Berücksichtigung dieser Rahmenbedingungen wurde schließlich ein Planungsmodell aufgestellt, das durch die Variation der Einlastungsreihenfolge unterschiedliche Belegungspläne generiert und mithilfe der entwickelten Bewertungsmethodik ein optimiertes Ergebnis durch eine Minimierung ablaufbedingter Kosten bestimmt. Dazu wurde auf ein heuristisches Lösungsverfahren zurückgegriffen und das erarbeitete Modell am Beispiel eines realen Produktionssystems verifiziert. Zur Lösung des Belegungsproblems wurde ein automatisiertes Planungsmodell (APS-Software Asprova® ) eingesetzt. Dazu wurde das Produktionssystem in ein Simulationsmodell überführt, mittels Variation von Parametereinstellungen unterschiedliche Belegungspläne generiert, der hinsichtlich des multikriteriellen Zielsystems beste Belegungsplan und damit eine optimierte Parametereinstellung ermittelt.
Die Anwendung auf das reale Belegungsproblem zeigt die Stärken und Schwächen des Verfahrens. Zum einen bietet der vorgestellte Ansatz zur Abbildung des Produktionssystems mit praktischen Restriktionen die Möglichkeit einer einfachen und standardisierten Vorgehensweise zur Aufnahme der Daten und somit zur Erstellung eines detaillierten und konsistenten Simulationsmodells. Zum anderen ist mit der Anwendung der Bewertungsmethodik die Auswahl eines optimierten Belegungsplans möglich. Allerdings treten durch die Verwendung eines Scoring-Modells die verfahrensspezifischen Probleme einer subjektiven Gewichtung und der Substituierbarkeit der einzelnen Kriterien auf. Für einen praktischen Einsatz, bspw. in einem Produktionsleitstand, ist eine Automatisierung des Bewertungsprozesses notwendig. Gezeigt wurden ebenfalls die Interdependenzen der Belegungsplanung auf andere Teilbereiche der Produktionsplanung, wie Losgrößenplanung (Bildung von Teillosen) und Lagerbetrachtungen (Entkopplungspuffer), was die Notwendigkeit einer simultanen Planung dieser Bereiche unterstreicht.
Weiterhin bleibt festzuhalten, dass für eine verbesserte Abbildung der Realität das vorgestellte Vorgehen bspw. durch die Einbeziehung stochastischer und dynamischer Problemstellungen erweiterbar ist, um Unsicherheiten wie Ausschussraten und Maschinenausfälle zu berücksichtigen.

 
Symbolverzeichnis
aj;i+1t  Pufferabgang des Auftrags j zur Stufe i+1 zum Zeitpunkt t
α  Maschinencharakteristika eines Belegungsproblems
A*j;i;ki;j*  frühester möglicher Anfangszeitpunkt des Auftrags j auf k(i)
bj;it  Entkopplungsbestand des Auftrags j nach Stufe i zum Zeitpunkt t
β  Auftragscharakteristika eines Belegungsproblems
Bj;i  maximaler Entkopplungsbestand des Auftrags j nach Stufe i
γ  Zielsetzungen eines Belegungsproblems
Cmax  Zykluszeit eines Belegungsplans
D  summierte Durchlaufzeit eines Belegungsplans
Dj  Durchlaufzeit des Auftrags j
Dmax  maximale Durchlaufzeit eines Belegungsplans
D  mittlere Durchlaufzeit eines Belegungsplans
eh(y)  Ergebniswert des quantitativen Kriteriums h von Belegungsplan y
ehmax  maximaler Ergebniswert des quantitativen Kriteriums h
ehmin  minimaler Ergebniswert des quantitativen Kriteriums h
Eh(y)  Zielerreichung des quantitativen Kriteriums h von Belegungsplan y
Ey  gewichtete Zielerreichung des Belegungsplans y
fj  gewünschter Fertigstellungstermin des Auftrags j ; Fälligkeit
Fj  geplanter Fertigstellungstermin des Auftrags j
F*j;i;k(i);j*  frühester möglicher Fertigstellungstermin des Auftrags j auf k(i)
gj  Anzahl der Arbeitsgänge des Auftrags j
h  Laufindex für quantitative Zielkriterien h=1,…,H
H  Anzahl quantitativer Zielkriterien
i  Laufindex für Maschinen, Stufen; i=1, …, m
j  Laufindex für Aufträge; j=1, …, n
j*  Vorgängerauftrag des Auftrags j auf der gleichen Maschine
λh  Gewichtungsfaktor eines quantitativen Zielkriteriums h
k(i)  Laufindex der parallelen Maschinen auf Stufe i ; k(i)=1,…, M(i)
κq(y)  Strafpunkte des qualitativen Kriteriums q von Belegungsplan y
m  Anzahl an Maschinen bzw. Fertigungsstufen
M(i)  Anzahl der parallelen Maschinen auf Stufe i
n  Anzahl an Aufträgen
NP  Komplexiätsklasse
oj;i  Vorgang des Auftrags j auf Stufe i
pj  Bearbeitungszeit des Auftrags j
pj;i  Bearbeitungszeit des Auftrags j auf der Maschine i
pj;i;k(i)  Bearbeitungszeit des Auftrags j auf der Maschine k(i)
pj;i;k(i)  Bearbeitungszeit pro Artikel des Auftrags j auf der Maschine k(i)
pr  Laufindex für Prioritätsregeln pr=1,…,PR
Pj;i  Bearbeitungszeitmatrix
PR  Anzahl an Prioritätsregeln
P  Komplexitätsklasse
q  Laufindex für qualitativen Zielkriterien q=1,…,Q
Q  Anzahl qualitativer Zielkriterien
rj  Auftragsfreigabe des Auftrags j
Rj*;j;i  Rüstmatrix
S  gesamte Rüstzeit eines Belegungsplans
Sj;i  Rüstzeit des Auftrags j auf der Maschine bzw. Stufe i
Sj*;j;i  Rüstzeit zwischen Auftrag j* und j auf Maschine bzw. Stufe i
t  Zeit
TAj  Terminabweichung des Auftrags j
uj  Artikel pro Teillos des Auftrags j
Uj  Auftragsmenge des Auftrags j
vi  Faktor der Fertigungsgeschwindigkeit von Maschine i
V  gesamte Verspätung eines Belegungsplans
Vj  Verspätung des Auftrags j
wj;pr  Prioritätswert der Prioritätsregel pr für Auftrag j
Wj  gesamte Wartezeit des Auftrags j
Wj;i  Wartezeit des Auftrags j vor der Maschine i
W  mittlere Wartezeit eines Belegungsplans
xj;i;k(i)  Binärvariable; Bearbeitung des Auftrags j auf k(i) ist möglich
Xj;i  Fertigungsmatrix
y  Laufindex für (alternative) Belegungspläne y=1, …,Y
y'  Belegungsplan mit maximalem Zielfunktionswert
Y  Anzahl der alternativen Belegungspläne
zj;it  Pufferzugang des Auftrags j aus Stufe i zum Zeitpunkt t
Zy  Zielfunktionswert eines Belegungsplans y
 
 
 
 
 
 

Literatur:

[1] Acker, I. J.: Methoden zur mehrstufigen Ablaufplanung in der Halbleiterindustrie. Wiesbaden 2011.
[2] Domschke, W./Scholl, A./Voß, S.: Produktionsplanung - Ablauforganisatorische Aspekte. Berlin 1997.
[3] Günther, H.-O./Tempelmeier, H.: Produktion und Logistik, 9. Auflage, Berlin 2012.
[4] Garlichs, R.: Entscheidungsorientierte Belegungsplanung von verketteten Montageanlagen. Düsseldorf/Hannover 1996.
[5] Corsten, H./Gössinger, R.: Produktionswirtschaft - Einführung in das industrielle Produktionsmanagement. München 2012.
[6] Daub, A.: Ablaufplanung. Bergisch Gladbach/Göttingen 1994.
[7] Pinedo, M. L.: Scheduling - Theory, algorithms, and systems, 4. Auflage, New York 2012.
[8] Ruiz, R./Vázquez-Rodríguez, J. A.: The hybrid flow shop scheduling problem, in: European journal of operational research 205 (1) 2010, S. 1–18.
[9] Schocke, K.-O.: Maschinenbelegungsplanung mehrstufiger Fließfertigungen - Vom Modell zum Leit-stand für die chemische Industrie, Wiesbaden 2000.
[10] Fowler, J. W./Mönch, L./Rose, O.: Scheduling and Simulation, in: Herrmann, J. W. (Hrsg.): Hand-book of production scheduling, New York 2006, S. 109–133.
[11] März, L./Krug, W.: Simulation und Optimierung in Produktion und Logistik - Praxisorientierter Leit-faden mit Fallbeispielen, Heidelberg 2011.
[12] Kurbel, K.: Produktionsplanung und -steuerung im Enterprise Resource Planning und Supply Chain Management, 6. Auflage, München 2005.
[13] Zelewski, S./Hohmann, S./Hügens, T.: Produktionsplanungs- und -steuerungssysteme - Konzepte und exemplarische Implementierungen mithilfe von SAP R/3, München 2008.
[14] Geiger, M. J.: Multikriterielle Ablaufplanung, Wiesbaden/Hohenheim 2005.
[15] Adam, D.: Planung und Entscheidung - Modelle, Ziele, Methoden; mit Fallstudien und Lösungen. Wiesbaden 1996.
[16] Fattahi, P./Hosseini, S. M. H./Jolai, F.: A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem, in: The International Journal of Advanced Manufacturing Technology 65 (5) 2013, S. 787–802.
[17] Buscher, U.: Durchlaufzeitcontrolling in der industriellen Auftragsfertigung, in: Freidank, C.-C./Müller, S./Wulf, I. (Hrsg.): Controlling und Rechnungslegung - aktuelle Entwicklungen in Wissenschaft und Praxis, Wiesbaden 2008, S. 115–138.
[18] http://www.asprova.eu (26.04.2017).