Parallele Maschinenplanung

Was ist Parallelmaschinenplanung?

Die Ablaufplanung auf parallelen Maschinen weist eine Menge von Aufträgen mehreren identischen Maschinen zu, um Ziele wie die Minimierung des Makespan (Gesamtdurchlaufzeit) oder der Gesamtverspätung zu erreichen. Sie erweitert die Ablaufplanung für eine einzelne Maschine auf Mehrmaschinen-Umgebungen, wie sie in Fertigung, Datenverarbeitung und Logistik verbreitet sind.

Die LPT-Regel (Longest Processing Time) ist eine bekannte Heuristik zur Minimierung des Makespan auf parallelen Maschinen: Die Aufträge werden nach absteigender Bearbeitungszeit sortiert und jeder Auftrag wird der Maschine zugewiesen, die als Erste verfügbar ist. Bei identischen Maschinen garantiert LPT einen Makespan innerhalb des 4/3-Fachen des Optimums. Andere Regeln (SPT, EDD, WSPT) optimieren andere Zielgrößen.

Die Maschinenauslastung — der Anteil der Gesamtzeit, in dem eine Maschine belegt ist — zeigt die Güte der Lastverteilung. Eine gleichmäßige Auslastung über alle Maschinen hinweg spricht für eine gute Balance. Das Gantt-Diagramm stellt den zeitlichen Ablauf je Maschine dar und macht Leerzeiten sowie Lastungleichgewichte unmittelbar sichtbar.

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

Berechnungsbeispiel

4 Aufträge (p=8,6,5,3) auf 2 Maschinen mit LPT. Zuweisung: Auftrag1(8)→M1, Auftrag2(6)→M2, Auftrag3(5)→M2 (Last 6→11), Auftrag4(3)→M1 (Last 8→11). Makespan = 11. Auslastung: M1=11/11=100 %, M2=11/11=100 %. Perfekt ausbalanciert. Ohne LPT (FCFS) ergäbe sich möglicherweise ein Makespan=14 bei schlechter Balance.

Wann diesen Rechner verwenden

• Beim Einplanen eines Auftragsbündels auf mehrere identische Maschinen zur Minimierung der Gesamtdurchlaufzeit oder Gesamtverspätung
• Bei der Kapazitätsplanung zur Bewertung, ob eine zusätzliche Maschine die Gesamtdurchlaufzeit für die aktuelle Auslastung bedeutsam reduzieren würde
• Beim Vergleich von Einplanungsregeln für den spezifischen Auftragsmix — verschiedene Regeln optimieren verschiedene Ziele und die beste Wahl hängt von den Prioritäten ab
• Nach einem Maschinenausfall zum schnellen Neu-Einplanen der verbleibenden Aufträge auf die verfügbaren Maschinen und zur Bewertung der Lieferauswirkung
• Beim Lastausgleich über Maschinen zur Minimierung der Leerlaufzeit und Sicherstellung, dass alle Maschinen gleichmäßig zum Produktionsplan beitragen

Häufige Fehler vermeiden

• SPT zur Minimierung der Gesamtdurchlaufzeit verwenden — SPT minimiert die durchschnittliche Durchlaufzeit, nicht die Gesamtdurchlaufzeit; für Parallelmaschinen LPT verwenden, die die längsten Aufträge zuerst zuweist
• Annehmen dass mehr Maschinen die Gesamtdurchlaufzeit immer proportional reduzieren — die Verbesserung folgt dem Gesetz abnehmender Grenzerträge; bei sehr ungleichen Auftragsgrößen kann eine zusätzliche Maschine die Gesamtdurchlaufzeit kaum verringern
• Freigabezeiten nicht berücksichtigen wenn Aufträge zu verschiedenen Zeiten eintreffen — statische Einplanungsregeln nehmen an, dass alle Aufträge zum Zeitpunkt Null verfügbar sind; bei unterschiedlichen Ankunftszeiten dynamische Einplanung verwenden
• Maschinenauslastungsbalance ignorieren — ein Schedule mit minimaler Gesamtdurchlaufzeit kann einige Maschinen für lange Zeiträume im Leerlauf lassen; Auslastung über alle Maschinen auf Fairness und Verschleißbalance prüfen

Ergebnisse interpretieren

• Gleichmäßige Auslastung über alle Maschinen (jeweils >90%) — die Last ist gut ausbalanciert; die Einplanungsregel arbeitet effizient
• Eine Maschine bei 100% Auslastung während andere deutlich niedriger — diese Maschine ist der Engpass; der längste Auftrag bestimmt wahrscheinlich die Gesamtdurchlaufzeit
• Gesamtverspätung = 0 — alle Aufträge werden vor ihrem Fälligkeitstermin fertig; der Schedule erfüllt alle Lieferzusagen
• Hohe Gesamtverspätung mit vielen verspäteten Aufträgen — die Auslastung übersteigt die Kapazität im Fälligkeitszeitfenster; Überstunden, zusätzliche Maschinen oder verlängerte Fälligkeitstermine erwägen
• LPT und SPT liefern sehr ähnliche Gesamtdurchlaufzeiten — die Bearbeitungszeiten der Aufträge sind relativ gleichmäßig; die Regelauswahl ist weniger wichtig wenn Aufträge ähnlich groß sind

Zugehörige Normen & Referenzen

• APICS CPIM Body of Knowledge — Behandelt Parallelmaschinen-Scheduling-Konzepte im Modul Produktionsaktivitätskontrolle
• ISA-95 (IEC 62264) — Standard für die Integration von Unternehmens- und Steuerungssystemen, definiert Planungsebenen einschließlich detaillierter Maschinenplanung

Häufig gestellte Fragen

Welche Prioritätsregel minimiert den Makespan auf parallelen Maschinen?

LPT (längste Bearbeitungszeit zuerst) ist die beste Heuristik zur Minimierung des Makespan. Indem die längsten Aufträge zuerst zugewiesen werden, entstehen am Ende keine Engpässe durch große Aufträge. LPT garantiert eine Lösung innerhalb des (4/3 - 1/(3m))-Fachen des Optimums, wobei m die Anzahl der Maschinen ist. Bei 2 Maschinen liegt sie damit innerhalb des 7/6-Fachen (≈17 %) des Optimums.

Wie gehe ich mit Aufträgen unterschiedlicher Freigabe- oder Fälligkeitstermine um?

Bei Freigabeterminen können Aufträge erst nach ihrer Freigabe beginnen — verwenden Sie eine dynamische Reihenfolgebildung, die die Prioritäten neu bewertet, sobald eine Maschine frei wird. Bei Fälligkeitsterminen helfen die Regeln EDD oder CR, die Verspätung zu minimieren. Für komplexe Aufgabenstellungen mit beiden Restriktionen simulieren Sie mehrere Regeln und vergleichen die Leistungskennzahlen. Die beste Regel hängt vom konkreten Auftragsmix und der Zielsetzung ab.