Der Moore-Algorithmus ist ein Verfahren aus der Produktionsplanung und Ablaufplanung. Er bestimmt für mehrere Aufträge eine Reihenfolge, bei der auf einer einzelnen Maschine möglichst wenige Aufträge nach ihrem jeweiligen Fälligkeitstermin fertiggestellt werden.
In der Fachliteratur wird das Verfahren meistens als Moore-Hodgson-Algorithmus bezeichnet. Es löst ein klar abgegrenztes Problem der Maschinenbelegungsplanung:
Eine Menge von Aufträgen soll auf einer Maschine so eingeplant werden, dass die Anzahl der verspäteten Aufträge minimal ist.
Der Algorithmus wurde 1968 von J. Michael Moore für die Bearbeitung von (n) Aufträgen auf einer einzelnen Maschine veröffentlicht. Die heute verbreitete vereinfachte Variante wird häufig Moore und Hodgson gemeinsam zugeschrieben.
Das Wichtigste in Kürze
Der Moore-Hodgson-Algorithmus:
- plant mehrere Aufträge auf einer Maschine,
- verwendet Bearbeitungszeiten und Fälligkeitstermine,
- beginnt mit einer Sortierung nach der EDD-Regel,
- erkennt den ersten verspäteten Auftrag,
- entfernt aus der bisherigen Auftragsfolge den Auftrag mit der längsten Bearbeitungszeit,
- wiederholt diese Schritte, bis alle verbliebenen Aufträge pünktlich sind,
- minimiert die Anzahl verspäteter Aufträge,
- minimiert nicht deren gesamte oder maximale Verspätungsdauer.
Die pünktlich ausführbaren Aufträge bleiben in EDD-Reihenfolge. Die entfernten Aufträge werden anschließend angefügt und gelten als verspätet.
Was optimiert der Moore-Algorithmus?
Für jeden Auftrag (j) werden mindestens zwei Werte benötigt:
- (p_j): Bearbeitungszeit des Auftrags
- (d_j): Fälligkeitstermin des Auftrags
Aus der gewählten Reihenfolge ergibt sich zusätzlich:
- (C_j): Fertigstellungszeitpunkt
- (L_j): Terminabweichung beziehungsweise Lateness
- (T_j): Verspätung beziehungsweise Tardiness
- (U_j): Kennzahl, ob der Auftrag verspätet ist
Die Terminabweichung wird berechnet als:
[
L_j = C_j – d_j
]
Ein negativer Wert bedeutet, dass der Auftrag vor seinem Fälligkeitstermin fertiggestellt wurde. Ein positiver Wert bedeutet, dass der Auftrag verspätet ist.
Die nicht negative Verspätung lautet:
[
T_j = \max(0, C_j-d_j)
]
Für die Bewertung des Moore-Algorithmus ist entscheidend, ob überhaupt eine Verspätung vorliegt:
[
U_j =
\begin{cases}
0, & C_j \leq d_j \
1, & C_j > d_j
\end{cases}
]
Das Optimierungsziel lautet:
[
\min \sum_{j=1}^{n} U_j
]
Die Summe entspricht der Anzahl verspäteter Aufträge.
Der Algorithmus versucht nicht, die Verspätungsdauer aller Aufträge zu minimieren. Für ihn zählt zunächst nur, wie viele Aufträge rechtzeitig fertig werden.
Voraussetzungen des Moore-Hodgson-Algorithmus
Der klassische Algorithmus liefert eine optimale Lösung unter bestimmten Annahmen:
- Es steht genau eine Maschine zur Verfügung.
- Die Maschine kann immer nur einen Auftrag gleichzeitig bearbeiten.
- Alle Aufträge stehen zu Beginn zur Bearbeitung bereit.
- Ein begonnener Auftrag wird nicht unterbrochen.
- Bearbeitungszeiten und Fälligkeitstermine sind bekannt.
- Rüstzeiten werden nicht gesondert berücksichtigt.
- Es bestehen keine Abhängigkeiten zwischen den Aufträgen.
- Jeder verspätete Auftrag wird gleich gewichtet.
In der üblichen Schreibweise der Ablaufplanung wird dieses Problem als
[
1 , || , \sum U_j
]
bezeichnet.
Dabei steht:
- (1) für eine einzelne Maschine,
- der leere mittlere Bereich für das Fehlen zusätzlicher Nebenbedingungen,
- (\sum U_j) für die zu minimierende Anzahl verspäteter Aufträge.
Der Moore-Hodgson-Algorithmus liefert für dieses klassische Problem eine optimale Lösung.
Ablauf des Moore-Algorithmus
Der Algorithmus kann in fünf Schritten dargestellt werden.
Schritt 1: Nach EDD sortieren
Alle Aufträge werden aufsteigend nach ihrem Fälligkeitstermin sortiert.
EDD steht für:
Earliest Due Date – frühester Fälligkeitstermin zuerst
Der Auftrag mit dem frühesten Fälligkeitstermin steht somit an erster Stelle.
Schritt 2: Fertigstellungszeiten berechnen
Die Bearbeitungszeiten werden der Reihe nach addiert.
Für den ersten Auftrag gilt:
[
C_1 = p_1
]
Für alle weiteren Aufträge gilt:
[
C_j = C_{j-1}+p_j
]
Anschließend wird geprüft, ob jeder Auftrag spätestens zu seinem Fälligkeitstermin beendet wird:
[
C_j \leq d_j
]
Schritt 3: Ersten verspäteten Auftrag suchen
Der Algorithmus betrachtet die EDD-Reihenfolge von vorne und sucht den ersten Auftrag, für den gilt:
[
C_j > d_j
]
Ist kein Auftrag verspätet, ist die aktuelle Reihenfolge bereits optimal und das Verfahren endet.
Schritt 4: Längsten bisherigen Auftrag entfernen
Sobald der erste verspätete Auftrag gefunden wurde, werden dieser Auftrag und alle vor ihm liegenden Aufträge betrachtet.
Aus dieser Teilmenge wird der Auftrag mit der längsten Bearbeitungszeit entfernt.
Warum gerade der längste Auftrag?
Durch seine Entfernung wird die bisher belegte Maschinenzeit maximal reduziert. Dadurch steigen die Chancen, dass möglichst viele kürzere Aufträge noch rechtzeitig abgeschlossen werden können.
Der entfernte Auftrag wird in eine separate Liste der verspäteten Aufträge verschoben.
Schritt 5: Prüfung wiederholen
Nach der Entfernung werden die Fertigstellungszeiten der verbleibenden Aufträge neu berechnet.
Das Verfahren wird so lange wiederholt, bis sämtliche verbliebenen Aufträge pünktlich fertiggestellt werden können.
Am Ende besteht der vollständige Produktionsplan aus:
- den verbliebenen pünktlichen Aufträgen in EDD-Reihenfolge,
- den zuvor entfernten verspäteten Aufträgen.
Für das primäre Ziel (\sum U_j) dürfen die entfernten Aufträge grundsätzlich in beliebiger Reihenfolge angefügt werden. Soll zusätzlich deren Verspätungsdauer möglichst gering bleiben, kann die Reihenfolge dieser Aufträge dennoch relevant sein.
Moore-Algorithmus mit einem einfachen Beispiel
Gegeben sind vier Aufträge:
| Auftrag | Bearbeitungszeit (p_j) | Fälligkeit (d_j) |
|---|---|---|
| A | 4 | 4 |
| B | 3 | 6 |
| C | 2 | 7 |
| D | 1 | 8 |
Schritt 1: EDD-Reihenfolge bestimmen
Die Fälligkeitstermine sind bereits aufsteigend sortiert:
[
A \rightarrow B \rightarrow C \rightarrow D
]
Schritt 2: Fertigstellungszeiten berechnen
| Position | Auftrag | Bearbeitungszeit | Fertigstellung (C_j) | Fälligkeit (d_j) | Ergebnis |
| 1 | A | 4 | 4 | 4 | pünktlich |
| 2 | B | 3 | 7 | 6 | verspätet |
| 3 | C | 2 | 9 | 7 | verspätet |
| 4 | D | 1 | 10 | 8 | verspätet |
B ist der erste verspätete Auftrag.
Schritt 3: Längsten Auftrag im betroffenen Bereich entfernen
Bis einschließlich B wurden folgende Aufträge eingeplant:
| Auftrag | Bearbeitungszeit |
| A | 4 |
| B | 3 |
Auftrag A hat die längste Bearbeitungszeit und wird deshalb aus der vorläufigen Reihenfolge entfernt.
Die verbleibende Reihenfolge lautet:
[
B \rightarrow C \rightarrow D
]
Schritt 4: Neue Fertigstellungszeiten berechnen
| Position | Auftrag | Bearbeitungszeit | Fertigstellung (C_j) | Fälligkeit (d_j) | Ergebnis |
| 1 | B | 3 | 3 | 6 | pünktlich |
| 2 | C | 2 | 5 | 7 | pünktlich |
| 3 | D | 1 | 6 | 8 | pünktlich |
Alle verbliebenen Aufträge sind nun pünktlich.
Schritt 5: Entfernten Auftrag anhängen
Auftrag A wird am Ende angefügt:
[
B \rightarrow C \rightarrow D \rightarrow A
]
Der vollständige Plan lautet:
| Position | Auftrag | Bearbeitungszeit | Fertigstellung | Fälligkeit | Ergebnis |
| 1 | B | 3 | 3 | 6 | pünktlich |
| 2 | C | 2 | 5 | 7 | pünktlich |
| 3 | D | 1 | 6 | 8 | pünktlich |
| 4 | A | 4 | 10 | 4 | verspätet |
Das Ergebnis enthält nur noch einen verspäteten Auftrag.
Eine Lösung ohne verspäteten Auftrag ist nicht möglich: Die gesamte Bearbeitungszeit beträgt zehn Zeiteinheiten, während der späteste Fälligkeitstermin bei acht liegt.
Der Moore-Hodgson-Algorithmus hat damit die minimale Anzahl verspäteter Aufträge gefunden.
Warum reicht die EDD-Regel nicht aus?
Die EDD-Regel sortiert ausschließlich nach Fälligkeitsterminen.
Sie löst ein anderes Optimierungsproblem:
[
1 , || , L_{\max}
]
EDD minimiert die größte Terminabweichung eines Auftrags. Da die maximale Verspätung aus der maximalen Terminabweichung abgeleitet werden kann, minimiert EDD unter den Standardannahmen auch die maximale Verspätung.
EDD minimiert aber nicht zwingend die Anzahl verspäteter Aufträge.
Im Beispiel führte die reine EDD-Reihenfolge zu drei verspäteten Aufträgen:
[
A \rightarrow B \rightarrow C \rightarrow D
]
Der Moore-Hodgson-Algorithmus entfernte den langen Auftrag A aus dem pünktlichen Teil und reduzierte die Anzahl verspäteter Aufträge dadurch auf eins:
[
B \rightarrow C \rightarrow D \rightarrow A
]
EDD ist somit ein Bestandteil des Moore-Hodgson-Algorithmus, aber nicht mit ihm gleichzusetzen.
Unterschied zwischen EDD, SPT und Moore-Hodgson
Die drei Verfahren verfolgen unterschiedliche Ziele.
| Verfahren | Sortier- oder Auswahlregel | Typisches Optimierungsziel |
| EDD | frühester Fälligkeitstermin zuerst | maximale Terminabweichung minimieren |
| SPT | kürzeste Bearbeitungszeit zuerst | durchschnittliche beziehungsweise gesamte Fertigstellungszeit minimieren |
| Moore-Hodgson | EDD plus Entfernung des längsten Auftrags bei Verspätung | Anzahl verspäteter Aufträge minimieren |
EDD: Earliest Due Date
Bei EDD werden die Aufträge aufsteigend nach ihrem Fälligkeitstermin sortiert:
[
d_1 \leq d_2 \leq \ldots \leq d_n
]
Das Ziel besteht darin, die maximale Terminabweichung zu minimieren.
SPT: Shortest Processing Time
Bei SPT werden die Aufträge aufsteigend nach ihrer Bearbeitungszeit sortiert:
[
p_1 \leq p_2 \leq \ldots \leq p_n
]
SPT priorisiert kurze Aufträge und minimiert unter den klassischen Annahmen die Summe beziehungsweise den Durchschnitt der Fertigstellungszeiten.
Die SPT-Regel ist kein eigenständiger Schritt des heute üblichen Moore-Hodgson-Verfahrens. Lediglich bei der Auswahl eines zu entfernenden Auftrags spielt die Bearbeitungszeit eine Rolle – entfernt wird der längste und nicht der kürzeste Auftrag.
Moore-Hodgson
Der Moore-Hodgson-Algorithmus kombiniert:
- eine EDD-Grundreihenfolge,
- eine Prüfung der Termintreue,
- die Entfernung des längsten bisher eingeplanten Auftrags.
Dadurch wird nicht die Höhe der Verspätungen, sondern ihre Anzahl minimiert.
Pseudocode des Moore-Hodgson-Algorithmus
Eine effiziente Variante verarbeitet die Aufträge einmal in EDD-Reihenfolge und verwaltet die bisher ausgewählten Aufträge in einer Max-Priority-Queue.
sortiere alle Aufträge aufsteigend nach Fälligkeit
pünktliche_Aufträge = leere Max-Priority-Queue
verspätete_Aufträge = leere Liste
gesamte_Bearbeitungszeit = 0
für jeden Auftrag in EDD-Reihenfolge:
füge Auftrag zu pünktliche_Aufträge hinzu
gesamte_Bearbeitungszeit += Bearbeitungszeit des Auftrags
wenn gesamte_Bearbeitungszeit > Fälligkeit des aktuellen Auftrags:
längster_Auftrag =
entferne Auftrag mit längster Bearbeitungszeit
gesamte_Bearbeitungszeit -=
Bearbeitungszeit des längsten_Auftrags
füge längsten_Auftrag zu verspätete_Aufträge hinzu
Ergebnis:
verbliebene Aufträge in EDD-Reihenfolge
danach die verspäteten Aufträge
Die Priority Queue liefert bei jeder Terminverletzung schnell den bisher längsten Auftrag.
Laufzeit des Algorithmus
Zunächst müssen die Aufträge nach ihren Fälligkeitsterminen sortiert werden. Dies benötigt typischerweise:
[
O(n \log n)
]
Werden die ausgewählten Aufträge zusätzlich in einem Max-Heap gespeichert, benötigen Einfügen und Entfernen jeweils:
[
O(\log n)
]
Da jeder Auftrag höchstens einmal eingefügt und entfernt wird, beträgt die gesamte Laufzeit:
[
O(n \log n)
]
Eine einfache Implementierung, die bei jeder Verspätung den längsten Auftrag durch vollständiges Durchsuchen der bisherigen Liste ermittelt, kann dagegen eine Laufzeit von
[
O(n^2)
]
erreichen.
Typische Fehler bei der Anwendung
Maximale Verspätung mit Anzahl verspäteter Aufträge verwechseln
Der häufigste Fehler besteht darin, dem Moore-Hodgson-Algorithmus die Minimierung der maximalen Verspätung zuzuschreiben.
Richtig ist:
- EDD minimiert die maximale Terminabweichung.
- Moore-Hodgson minimiert die Anzahl verspäteter Aufträge.
Alle verspäteten Aufträge entfernen
Die vom Algorithmus entfernten Aufträge verschwinden nicht aus dem realen Produktionsprogramm.
Sie werden lediglich aus der Gruppe der pünktlich einplanbaren Aufträge entfernt und anschließend an den Plan angefügt. Ohne diese Ergänzung entsteht keine vollständige Produktionsreihenfolge.
Nach jedem Schritt neu nach SPT sortieren
Der verbleibende Plan bleibt grundsätzlich in EDD-Reihenfolge.
Die Bearbeitungszeiten werden nur verwendet, um bei einer Terminverletzung den längsten bisherigen Auftrag auszuwählen.
Verspätung und Terminabweichung gleichsetzen
Die Terminabweichung (L_j) kann negativ sein:
[
L_j = C_j-d_j
]
Die Verspätung (T_j) kann dagegen nicht negativ werden:
[
T_j = \max(0,L_j)
]
Den Algorithmus auf ungeeignete Probleme übertragen
Der klassische Algorithmus ist nicht ohne Weiteres optimal bei:
- mehreren Maschinen,
- unterschiedlichen Freigabezeitpunkten,
- gewichteten Aufträgen,
- Reihenfolgeabhängigkeiten,
- Unterbrechungen,
- unterschiedlichen Verspätungskosten,
- sequenzabhängigen Rüstzeiten,
- begrenzten zusätzlichen Ressourcen.
Für solche Varianten werden andere Optimierungsmodelle, dynamische Programmierung, Branch-and-Bound-Verfahren, gemischt-ganzzahlige Modelle oder geeignete Heuristiken benötigt.
Gewichtete verspätete Aufträge
Im klassischen Modell zählt jeder verspätete Auftrag gleich viel.
Das kann in der Praxis unrealistisch sein. Ein verspäteter Großauftrag kann wesentlich schwerwiegender sein als ein verspäteter interner Kleinauftrag.
Bei unterschiedlichen Gewichten wird jedem Auftrag ein Gewicht (w_j) zugeordnet:
[
\min \sum w_j U_j
]
Der klassische Moore-Hodgson-Algorithmus löst dieses gewichtete Problem im Allgemeinen nicht optimal.
Es reicht dann nicht mehr aus, bei einer Terminverletzung immer den Auftrag mit der längsten Bearbeitungszeit zu entfernen. Bearbeitungszeit, Bedeutung und Verspätungskosten müssen gemeinsam berücksichtigt werden.
Praktische Einsatzbereiche
Der Moore-Hodgson-Algorithmus eignet sich insbesondere für Situationen, in denen:
- eine einzelne Produktionsanlage den Engpass bildet,
- Aufträge feste Bearbeitungszeiten besitzen,
- mehrere Liefertermine eingehalten werden sollen,
- die Anzahl verspäteter Aufträge wichtiger als die genaue Verspätungsdauer ist,
- Aufträge notfalls bewusst nach hinten verschoben werden dürfen.
Mögliche Anwendungsbereiche sind:
- Maschinenbelegungsplanung,
- Produktionsplanung,
- Auftragsfertigung,
- Wartungsplanung,
- Labor- und Prüfaufträge,
- Druckaufträge,
- administrative Fallbearbeitung,
- Stapelverarbeitung in IT-Systemen.
Das Modell abstrahiert jedoch zahlreiche reale Einflussgrößen. In der Praxis müssen häufig zusätzlich Materialverfügbarkeit, Personal, Prioritäten, Rüstzeiten, Transportzeiten und Maschinenstörungen berücksichtigt werden.
Einordnung des vorhandenen Java-Projekts
Das zum bisherigen Beitrag gehörende Java-Projekt liest Auftragsnamen, Bearbeitungszeiten und Fälligkeitstermine aus einer Konfigurationsklasse ein. Anschließend sortiert es die Aufträge nach EDD und entfernt bei einer erkannten Verspätung den längsten Auftrag aus dem betroffenen Teil der Liste.
Damit wird der zentrale Auswahlmechanismus des Moore-Hodgson-Algorithmus demonstriert.
Für eine vollständige Implementierung sollte das Programm jedoch zwei getrennte Listen führen:
- pünktliche Aufträge,
- entfernte beziehungsweise verspätete Aufträge.
Nach Abschluss des Algorithmus müssen beide Listen zu einer vollständigen Reihenfolge zusammengeführt werden. Außerdem sollte die Ausgabe ausdrücklich die Anzahl verspäteter Aufträge darstellen, statt den Algorithmus als Verfahren zur Berechnung der maximalen Verspätung zu beschreiben.
Fazit
Der Moore-Hodgson-Algorithmus ist ein klassisches Verfahren der Ablauf- und Produktionsplanung. Er bestimmt für mehrere Aufträge auf einer einzelnen Maschine eine Reihenfolge mit der kleinstmöglichen Anzahl verspäteter Aufträge.
Der Ablauf besteht aus drei zentralen Elementen:
- Sortierung nach dem frühesten Fälligkeitstermin,
- Erkennung einer Terminüberschreitung,
- Entfernung des bisher längsten Auftrags.
Die entfernten Aufträge werden anschließend an die pünktlich ausführbare EDD-Reihenfolge angefügt.
Entscheidend ist die korrekte Abgrenzung:
- EDD minimiert die maximale Terminabweichung.
- SPT minimiert die gesamte beziehungsweise durchschnittliche Fertigstellungszeit.
- Moore-Hodgson minimiert die Anzahl verspäteter Aufträge.
Unter seinen klassischen Voraussetzungen liefert der Moore-Hodgson-Algorithmus eine optimale Lösung für das Problem (1||\sum U_j). Bei gewichteten Aufträgen, mehreren Maschinen, Freigabezeitpunkten oder zusätzlichen Nebenbedingungen muss dagegen ein erweitertes Planungsverfahren eingesetzt werden.
Häufige Fragen zum Moore-Algorithmus
Was ist das Ziel des Moore-Algorithmus?
Das Ziel ist die Minimierung der Anzahl verspäteter Aufträge auf einer einzelnen Maschine.
Ist der Moore-Algorithmus dasselbe wie EDD?
Nein. EDD ist ein Bestandteil des Moore-Hodgson-Algorithmus. EDD allein minimiert die maximale Terminabweichung, nicht zwingend die Anzahl verspäteter Aufträge.
Warum wird der längste Auftrag entfernt?
Durch das Entfernen des längsten bisherigen Auftrags wird am meisten Bearbeitungszeit freigesetzt. Dadurch können möglichst viele kürzere Aufträge noch vor ihren Fälligkeitsterminen abgeschlossen werden.
Werden entfernte Aufträge nicht mehr produziert?
Doch. Sie werden lediglich aus dem pünktlichen Teil des Plans entfernt und am Ende der Reihenfolge angefügt.
Was bedeutet EDD?
EDD steht für „Earliest Due Date“. Aufträge werden aufsteigend nach ihrem Fälligkeitstermin sortiert.
Was bedeutet SPT?
SPT steht für „Shortest Processing Time“. Aufträge werden aufsteigend nach ihrer Bearbeitungszeit sortiert.
Was ist ein verspäteter Auftrag?
Ein Auftrag ist verspätet, wenn sein Fertigstellungszeitpunkt nach seinem Fälligkeitstermin liegt:
[
C_j > d_j
]
Ist der Moore-Hodgson-Algorithmus optimal?
Ja, für das klassische Problem mit einer Maschine, gleichzeitig verfügbaren Aufträgen, bekannten Bearbeitungszeiten, keinen Unterbrechungen und gleich gewichteten Verspätungen.
Welche Laufzeit hat der Algorithmus?
Mit einer geeigneten Max-Priority-Queue beträgt die Laufzeit (O(n \log n)). Eine einfache Implementierung mit wiederholter linearer Suche kann (O(n^2)) benötigen.
Funktioniert der Algorithmus für mehrere Maschinen?
Nicht in seiner klassischen Form. Mehrmaschinenprobleme benötigen andere oder erweiterte Verfahren.