Die LKW-Terminvergabe verständlich erklärt

Vier Behandlungszimmer, viele Wartende, und alle wollen zur selben Zeit dran sein: Die Reihenfolge des Aufrufens bestimmt die Wartezeit. Genauso ist es an den Toren einer Lagerhalle, an denen Lastwagen entladen werden. Diese Seite zeigt, welche Reihenfolge Wartezeit spart und wen sie trifft.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Morgen in der Arztpraxis

Eine Praxis hat vier Behandlungszimmer. Heute Morgen haben sich viele Patienten angemeldet, und jeder nennt seine Wunschzeit. Vor dieser Zeit kann niemand drankommen. Danach nur, wenn ein Zimmer frei ist. Wie lange jede Behandlung dauert, weiß die Praxis vorher.

Wer später drankommt als gewünscht, hat gewartet. Diese Wartezeit reicht vom Wunsch bis zum Beginn der Behandlung. Die Praxis will, dass alle zusammen möglichst wenig warten. Dafür muss sie entscheiden, wer wann in welches Zimmer kommt. Notfälle oder Vorrang gibt es nicht.

Dasselbe Problem hat eine Lagerhalle. An ihren Toren werden Lastwagen (kurz LKW) entladen, an jedem Tor immer nur einer. Jeder Fahrer nennt eine Wunschzeit für den Beginn, und die Dauer der Entladung ist bekannt. Aus Zimmern werden Tore, aus Patienten LKW. Wer für jeden LKW Tor und Startzeit festlegt, betreibt Terminvergabe.

Die Seite arbeitet mit einem vereinfachten Rechenbild (Fachwort: Modell), also einer Beispielrechnung mit erfundenen Daten. Darin ist alles vorher bekannt, es fällt nichts aus, und es geht um einen einzigen Tag. Die Aussagen in diesem Teil gelten für dieses Rechenbild, nicht für die Wirklichkeit.

Drei Regeln für die Reihenfolge

Drei einfache Regeln stehen zur Wahl. Jede legt fest, wer zuerst eingeplant wird:

• Anmeldereihenfolge: Wer sich zuerst gemeldet hat, wird zuerst eingeplant, und zwar an dem Tor, an dem er am frühesten starten kann. Wunsch und Dauer spielen für die Reihenfolge keine Rolle.
• Wunschzeit zuerst: Wer den frühesten Wunsch hat, wird zuerst eingeplant. Sonst gilt dasselbe wie bei der ersten Regel.
• Kürzeste Entladung zuerst: Sobald ein Tor frei wird, kommt von den LKW, deren Wunschzeit erreicht ist, der mit der kürzesten Entladung dran.

Warum sich die dritte Regel lohnen kann: Eine lange Entladung hält ein Tor lange besetzt, und alle dahinter warten mit. Eine kurze gibt das Tor schnell wieder frei.

Ein Beispiel mit nur einem Tor. Angenommen, zwei LKW wollen gleichzeitig starten, einer braucht 90 Minuten und einer 10. Kommt der lange zuerst dran, wartet der kurze 90 Minuten. Kommt der kurze zuerst dran, wartet der lange nur 10 Minuten. Zusammen sind das 90 gegen 10 Minuten Wartezeit.

Eine Falle bei der dritten Regel

Die dritte Regel wählt nur unter den LKW, die schon da sind. Das ist wichtig. Ordnet man dagegen morgens alle LKW des Tages nach der Dauer, entsteht eine Falle.

Ein langer LKW steht bereit, ein kurzer kommt erst später. Die Ordnung nach Dauer stellt den kurzen nach vorn. Das Tor bleibt leer, bis er da ist, und der lange LKW muss hinter ihm starten. Das ist unnötig: Der lange hätte sofort loslegen können.

Was die Messung zeigt

Das Rechenbild wurde an je 120 zufälligen Tagen durchgespielt, mit 24 bis 60 LKW an zwei bis vier Toren. Verglichen wurde die mittlere Wartezeit je LKW. Diese Tage waren voll: Mit der Anmeldereihenfolge warteten die LKW nach eigener Nachrechnung im Mittel mehrere Stunden. Im Mittel über die Tage sank die Wartezeit je LKW so:

• Wunschzeit zuerst statt Anmeldereihenfolge: 21 bis 24 Minuten weniger.
• Kürzeste Entladung zuerst statt Wunschzeit zuerst: 45 bis 49 Minuten weniger.
• Kürzeste Entladung zuerst statt Anmeldereihenfolge: 69 bis 71 Minuten weniger.

Es steht jeweils eine Spanne, weil die Werte je nach zufällig gewürfelten Tagen um einige Minuten schwanken. Die dritte Regel war an keinem der 120 Tage schlechter als die beiden anderen. Eine viel größere Nachmessung fand zwei knappe Ausnahmen. Sie war in diesen Messungen also fast immer besser, aber nicht an jedem Tag. Die zweite Regel war an manchen Tagen schlechter als die erste. Warum, zeigt die Messung nicht.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Dort stellen Sie Zahl der LKW und der Tore selbst ein und sehen die drei Regeln nebeneinander. Dort heißen sie FCFS, ERD und SPT, in der Reihenfolge der Liste oben.

Häufige Missverständnisse

Die Angaben zur längsten Wartezeit, zu den pünktlichen LKW und zu ruhigen Tagen hat der Autor dieser Seite selbst nachgerechnet. In der Messreihe der Demo stehen sie nicht. Pünktlich heißt hier: ohne Wartezeit.

• „Wenn sich kein einzelner LKW mehr verbessern lässt, ist der Plan der beste.“ Nein. Dass kein einzelner LKW auf einen früheren Platz passt, trifft bei allen drei Regeln zu. Der Grund: Jeder LKW bekam schon beim Einplanen den frühesten freien Platz, und danach kamen nur weitere Buchungen dazu. Trotzdem liefern die Regeln verschieden gute Pläne. Ein Plan ist also nicht schon gut, weil niemand allein nach vorn kann.
• „Die Regel mit der kürzesten mittleren Wartezeit ist für alle die beste.“ Nicht ganz. Bei der dritten Regel wird ein langer LKW übergangen, solange kürzere nachrücken. Wahrscheinlich deshalb wartet der am längsten Wartende dort an fast allen nachgerechneten Tagen länger als bei der zweiten Regel. Die meisten pünktlichen LKW hat in den Rechnungen die Anmeldereihenfolge.
• „An jedem Tag ist die Wahl der Regel wichtig.“ Nein. Wo nie mehrere LKW gleichzeitig warten, gibt es nichts zu sortieren. Im Beispiel „Ruhiger Tag“ der Demo wartet nur ein LKW. Die zweite und die dritte Regel ergaben dort dieselbe mittlere Wartezeit. Auch in der Voreinstellung der Demo waren die beiden Werte gleich, obwohl dort bis zu drei LKW gleichzeitig warten.

Woran Sie das im Alltag erkennen

• Wer sich früh einen Termin holt, kann seine Wunschzeit wählen. Wer spät anruft, nimmt, was noch frei ist.
• Eine Änderungsschneiderei erledigt kleine Aufträge gern zwischendurch, denn sie halten niemanden lange auf. Große Aufträge warten dafür länger.
• Zur Stoßzeit, etwa montags früh in der Praxis, bildet sich eine Schlange. An ruhigen Vormittagen fehlt sie.

Wie ernst ist das Rechenbild zu nehmen?

Die Zahlen gelten für erfundene Zufallstage und zeigen Größenordnungen. Kein LKW hat Vorrang. Echte Hallen haben weitere Regeln, etwa Pausen zwischen zwei LKW.

Was Sie mitnehmen:

• Fragen Sie bei jeder Warteregel, was gezählt wird: der Durchschnitt, der längste Wartende oder die Zahl der Pünktlichen.
• Wer kurze Aufträge vorziehen will, sollte fragen, ob die kurzen überhaupt schon da sind.
• Fragen Sie bei einem fertigen Plan, ob eine andere Reihenfolge insgesamt besser wäre. Ob ein Einzelner nach vorn kann, reicht nicht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist eine Terminvergabe an parallelen Toren mit Wunschzeiten. Alle Zahlen gelten nur für die unten beschriebenen Zufallsdaten.

• Aufgabe: Gegeben sind \(n\) LKW \(J = \{1, \ldots, n\}\) und \(m\) gleichartige Tore \(D = \{1, \ldots, m\}\). Jeder LKW \(i\) hat eine Wunschzeit \(r_i \ge 0\) in Minuten ab Betriebsbeginn (früher darf er nicht starten, daher auch Freigabetermin) und eine Bearbeitungsdauer \(p_i\). Gesucht sind ein Tor \(\delta(i)\) und eine Startzeit \(s_i \ge r_i\) je LKW, ohne Überlappung am selben Tor. Die Wartezeit ist \(w_i = s_i - r_i\), das Ziel ist die Gesamtwartezeit \(\sum_i w_i\). In der Drei-Feld-Notation der Scheduling-Theorie ist das \(P_m \mid r_i \mid \sum C_i\) mit der Fertigstellungszeit \(C_i = s_i + p_i\).
• Zufallsdaten: Die Bearbeitungsdauern sind gleichverteilt zwischen zwanzig und neunzig Minuten und auf ganze Minuten gerundet. Jeder LKW wünscht unabhängig mit Wahrscheinlichkeit \(q \in [0, 1]\) (der Konzentration auf Stoßzeiten) eine von \(k\) Stoßzeiten. Diese liegen gleichverteilt zufällig im Tag, und der LKW wählt eine von ihnen gleichverteilt; seine Wunschzeit streut normalverteilt um sie mit einer Standardabweichung von sechs Prozent des Betriebstages. Alle anderen LKW wünschen gleichverteilt über den Tag. Wunschzeiten werden auf den Betriebstag begrenzt und gerundet. Die Nummer eines LKW (seine Stelle in der Anmeldereihenfolge) ist von Wunschzeit und Dauer unabhängig.
• Einstellbereiche: Voreingestellt sind 24 LKW, vier Tore, ein Betriebstag von zwölf Stunden, zwei Stoßzeiten und \(q = 0{,}5\). Einstellbar sind acht bis achtzig LKW, ein bis zehn Tore, vier bis vierundzwanzig Stunden und eine bis vier Stoßzeiten.
• Annahmen: Alles ist deterministisch: Wunschzeiten und Dauern sind exakt bekannt, kein LKW fällt aus oder kommt nicht. Es gibt einen einzigen Betriebstag. Anschließende Bearbeitung am selben Tor ohne Pufferzeit ist erlaubt, und jedes Tor ist für jeden LKW geeignet.
• Kennzahlen: Die Demo zeigt Gesamt- und mittlere Wartezeit, den Anteil pünktlicher LKW (Wartezeit null) und den Makespan, die späteste Fertigstellung. Die längste Wartezeit wird berechnet, aber nicht angezeigt. Bewusst gibt es keine Kosten in Euro, weil die Wirkung von Standzeiten vom Vertragsmodell mit den Spediteuren abhängt.

Die Formeln

Ziel und Bedingungen. Zu minimieren ist die Gesamtwartezeit:

\[\min \; \sum_{i=1}^{n} (s_i - r_i) \quad \text{u. d. N.} \quad s_i \geq r_i \;\; \forall i\]

Zwei LKW am selben Tor dürfen sich nie überlappen: Für alle \(i \neq j\) mit \(\delta(i) = \delta(j)\) gilt \(s_i + p_i \le s_j\) oder \(s_j + p_j \le s_i\).

Gleichwertig zur Summe der Fertigstellungszeiten. Es gilt \(\sum_i (s_i - r_i) = \sum_i C_i - \sum_i p_i - \sum_i r_i\). Die letzten beiden Summen hängen nicht vom Plan ab. Die Gesamtwartezeit zu minimieren ist deshalb dasselbe Problem wie die Summe der Fertigstellungszeiten zu minimieren, nur um eine Konstante verschoben.

Anmeldereihenfolge (FCFS) und Wunschzeit zuerst (ERD). Beide Regeln verarbeiten die LKW in einer festen Reihenfolge (FCFS: Nummer des LKW, ERD: aufsteigend nach \(r_i\), bei gleicher Wunschzeit nach der Nummer) und setzen jeden LKW auf den frühestmöglichen freien Platz über alle Tore, auch in eine Lücke zwischen gebuchten Intervallen. FCFS ist hier also ein Einfügen in Anmeldereihenfolge mit Lückenfüllung, kein reines Warteschlangen-FCFS. \(B_d\) sei die Menge der auf Tor \(d\) schon gebuchten Intervalle. Der früheste Start von \(i\) auf Tor \(d\) ist \(s_d(i \mid B_d)\), der kleinste Zeitpunkt \(t \ge r_i\), zu dem das Intervall \([t, t + p_i)\) kein Intervall in \(B_d\) überschneidet. Gewählt wird das Tor mit dem frühesten Start:

\[(\delta^*(i), s^*(i)) = \arg\min_{d \,\in\, D} \; s_d(i \mid B_d)\]

Der freie Platz kann in einer Lücke vor schon gebuchten Intervallen liegen. Die beiden Regeln unterscheiden sich nur in der Reihenfolge, in der die LKW an diese Platzierung übergeben werden.

Kürzeste Bearbeitung zuerst unter den verfügbaren LKW (SPT). Das ist eine Simulation statt einer festen Liste. \(f_d\) sei der Zeitpunkt, zu dem Tor \(d\) als Nächstes frei wird, und \(R\) die Menge der noch nicht eingeplanten LKW:

\[t = \min_{d \,\in\, D} f_d, \qquad d^* = \arg\min_{d \,\in\, D} f_d\]

Verfügbar sind \(A(t) = \{ i \in R : r_i \le t \}\). Ist \(A(t)\) leer, springt \(t\) auf die kleinste Wunschzeit unter den Übrigen, und \(A(t)\) wird neu gebildet. Gewählt wird:

\[i^* = \arg\min_{i \,\in\, A(t)} p_i\]

Bei gleicher Dauer wird einer der Gleichständigen gewählt, die Summe der Wartezeiten ändert das nicht. Danach gilt \(\delta(i^*) \leftarrow d^*\), \(s_{i^*} \leftarrow t\), \(f_{d^*} \leftarrow t + p_{i^*}\) und \(R \leftarrow R \setminus \{i^*\}\). SPT lässt kein Tor leer, solange ein verfügbarer LKW wartet; Leerlauf entsteht nur, wenn niemand verfügbar ist.

Herleitungen Schritt für Schritt

Die Herleitungen und das durchgerechnete Beispiel in diesem Abschnitt sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum „kürzeste zuerst“ ohne Wunschzeiten optimal ist (ein Tor).

• Schritt 1: Alle LKW sind von Anfang an da (\(r_i = 0\)). Dann gibt es keinen Grund für Leerlauf, und ein Plan ist eine Reihenfolge der LKW.
• Schritt 2: Zwei benachbarte LKW \(a\) und \(b\) beginnen ab dem Zeitpunkt \(t\). In der Reihenfolge \(a, b\) enden sie bei \(t + p_a\) und \(t + p_a + p_b\), die Summe ist \(2t + 2p_a + p_b\). In der Reihenfolge \(b, a\) ist sie \(2t + 2p_b + p_a\). Der Unterschied ist \(p_a - p_b\): Der kürzere LKW zuerst gibt die kleinere Summe.
• Schritt 3: Vertauscht man zwei Nachbarn, ändern sich die Fertigstellungen aller anderen LKW nicht, denn das Paar belegt danach dieselbe Zeitspanne. Jeder Tausch „länger vor kürzer“ senkt also die Summe, und die nach Dauer sortierte Reihenfolge ist optimal.
• Bedingung: Das gilt, wenn alle LKW zum Zeitpunkt null verfügbar sind. Für mehrere gleichartige Tore ohne Wunschzeiten gilt es nach Angabe der mathematischen Formulierung der Demo ebenfalls (ihre Beschreibung nennt dagegen nur eine Maschine); hier nicht hergeleitet. Mit verschiedenen Wunschzeiten und ohne Unterbrechung gilt es nicht mehr, wie das nächste Beispiel zeigt.

Was eine Wunschzeit ändert. Ein Tor, ein langer LKW \(L\) mit Wunschzeit 0 und Dauer 100, ein kurzer LKW \(S\) mit Wunschzeit 50 und Dauer 1.

• Vorab nach Dauer sortiert: \(S\) wird zuerst eingeplant und startet bei 50. \(L\) passt nicht mehr davor und startet bei 51. Die Gesamtwartezeit ist 51.
• Ereignisgesteuert (SPT): Bei 0 ist nur \(L\) verfügbar und startet sofort. \(S\) startet bei 100 und wartet 50. Die Gesamtwartezeit ist 50.
• Einordnung: Aufzählung aller Reihenfolgen ergibt 50 als Optimum. Der Unterschied beträgt in diesem Beispiel eine Minute. Das Beispiel zeigt nur das Prinzip; die Demo verwendet die ereignisgesteuerte Regel, weil sie in den geprüften Zufallsinstanzen nie schlechter war (Befunde).

Warum eine Einzelverschiebung am fertigen Plan nichts findet.

• Schritt 1 (Monotonie): Für Buchungsmengen \(B \subseteq B'\) gilt \(s_d(i \mid B) \le s_d(i \mid B')\). Jeder Startzeitpunkt, der gegen \(B'\) zulässig ist, ist auch gegen \(B\) zulässig, denn mehr Buchungen sperren nur Plätze. Das Minimum über die größere Menge ist höchstens so groß.
• Schritt 2: Bei FCFS und ERD wurde jeder LKW \(i\) gegen die Buchungen \(B\) seiner Vorgänger auf den frühesten Platz gesetzt. Im fertigen Plan stehen dort die Buchungen \(B' \supseteq B\), alle anderen LKW eingerechnet. Setzt man \(i\) einzeln neu, kann er also nicht früher starten.
• Schritt 3: Für SPT gilt dieselbe Aussage nach der Demo. Sie prüft sie für alle drei Regeln an Zufallsinstanzen, indem jeder LKW gegen alle anderen Buchungen neu gesetzt wird. Ein Beweis für SPT ist hier nicht ausgeführt.
• Bedingung: Die Aussage gilt für das Neusetzen eines einzelnen LKW bei festen anderen. Das Tauschen der Startzeiten zweier LKW kann die Summe ihrer Wartezeiten ohnehin nie senken, denn die Summe der beiden Startzeiten bleibt gleich.
• Folgerung: Ein Plan, den keine Einzelverschiebung verbessert, muss nicht optimal sein. Das Beispiel unten zeigt es: Der ERD-Plan ist durch Einzelverschiebung unverbesserbar, der SPT-Plan ist trotzdem besser, und beide liegen über dem Optimum.

Durchgerechnet: Vier LKW an einem Tor

Erfundener Fall, Rechnung dieser Seite, in beliebigen Zeiteinheiten. Vier LKW in der Anmeldereihenfolge T1 bis T4 mit Wunschzeit und Dauer: T1 (2, 1), T2 (0, 3), T3 (0, 1), T4 (2, 1). Ein Tor.

Regel	Startzeiten von T1, T2, T3, T4 und Gesamtwartezeit
FCFS	2, 3, 0, 6. Wartezeiten 0, 3, 0, 4, Summe 7. T3 füllt die Lücke vor T1, T4 findet erst bei 6 Platz.
ERD	4, 0, 3, 5. Wartezeiten 2, 0, 3, 3, Summe 8.
SPT	4, 1, 0, 5. Wartezeiten 2, 1, 0, 3, Summe 6. Bei 0 sind T2 und T3 verfügbar, T3 ist kürzer. Bei 1 ist nur T2 übrig.
Optimum (alle Reihenfolgen)	2, 4, 0, 3. Wartezeiten 0, 4, 0, 1, Summe 5.

Drei Dinge zeigt das Beispiel. Erstens ist ERD hier schlechter als FCFS; das hängt am Gleichstand der Wunschzeit null bei T2 und T3, den ERD nach der Nummer auflöst. Zöge ERD dort die kürzere Dauer vor, käme es auf 6 wie SPT. Zweitens ist SPT von den drei Regeln die beste, liegt aber über dem Optimum. Drittens hält das Optimum das Tor zwischen den Zeiten 1 und 2 absichtlich leer, obwohl T2 wartet: T2 würde das Tor bis 4 blockieren, und die beiden LKW mit Wunschzeit 2 müssten warten. Keine der drei Regeln sieht das voraus.

Befunde

Jede Zeile gilt für Zufallsinstanzen und ist ein Mittel über Instanzen, kein Erwartungswert für ein bestimmtes Szenario. Die Zeilen zu den drei Regeln stammen aus je 120 Zufallsinstanzen mit 24 bis 60 LKW, zwei bis vier Toren, ein bis zwei Stoßzeiten und Konzentration 0,5 bis 1,0. Die Spannen entstehen, weil die Werte je nach Mischung der Instanzen und Zuordnung der Zufallsdaten um einige Minuten schwanken; die Größenordnung blieb in allen geprüften Mischungen gleich.

Frage	Befund
Was spart ERD gegenüber FCFS?	Im Mittel 21 bis 24 Minuten kürzere mittlere Wartezeit je LKW; in 11 bis 15 von 120 Instanzen ist ERD schlechter.
Was spart SPT gegenüber ERD?	Im Mittel 45 bis 49 Minuten; in keiner der 120 Instanzen schlechter. Eine unabhängige Nachmessung über 1200 Instanzen derselben Mischung fand zwei Fälle, in denen SPT minimal schlechter war (3 bzw. 6 Minuten Gesamtwartezeit).
Was spart SPT gegenüber FCFS?	Im Mittel 69 bis 71 Minuten; in keiner der 120 Instanzen schlechter.
Verbessert ein nachträgliches Neusetzen einzelner LKW die SPT-Konstruktion?	Nein: In 0 von 300 Testinstanzen fand das Neusetzen eines einzelnen LKW auf den frühesten freien Platz eine Verbesserung (Angabe der Demo; ihre Messung liegt nicht vor, die Aussage folgt aus der Monotonie unten und wird an fünfundzwanzig Zufallsinstanzen automatisch geprüft). Die Demo nennt dieselbe Zahl für das Tauschen zweier LKW; ein Tausch der Startzeiten kann die Summe der Wartezeiten aber nie senken, die Zahl sagt dort nichts.
Ist ereignisgesteuertes SPT besser als SPT mit vorab sortierter Liste?	In 40 Zufallsinstanzen (24 LKW, vier Tore) war es nie schlechter.

Nachrechnung dieser Seite mit dem Quelltext der Demo, keine Messung der Demo und ohne feste Zahlen im Text:

• Wiederholung der Messmischung: Fünf weitere Mischungen von je 120 Instanzen mit denselben Bereichen ergaben dieselbe Rangfolge und Ersparnisse im selben Rahmen, einzelne Werte weichen um wenige Minuten von den Spannen ab. ERD war dort in sechs bis zehn von 120 Instanzen schlechter als FCFS, in einer weiteren unabhängigen Ziehung derselben Bereiche in bis zu sechzehn, also streut die Zahl um die der Tabelle. Sie hängt von der Mischung ab.
• Mittlere Wartezeit der Mischung: Mit FCFS lag sie in jeder Wiederholung bei mehreren Stunden. Die Ersparnisse oben gelten damit für stark ausgelastete Tage.
• Längste Wartezeit: Bei SPT war sie in fast allen Instanzen größer als bei ERD, im Mittel gut ein Drittel (Verhältnis der Mittelwerte; als Mittel der Einzelverhältnisse eher vier Zehntel bis fast die Hälfte). Bei FCFS war sie im Mittel am größten. Die Rangfolge der längsten Wartezeit ist also ERD vor SPT vor FCFS.
• Anteil pünktlicher LKW (Wartezeit null): Bei FCFS war er im Mittel ungefähr doppelt so hoch wie bei ERD und etwas weniger als doppelt so hoch wie bei SPT, obwohl FCFS die höchste mittlere Wartezeit hat. SPT liegt dabei knapp vor ERD. Erklärung (Vermutung, nicht geprüft): Wer früh angemeldet ist, bekommt noch den Wunschplatz, später Angemeldete weichen aus.
• Vier Einzelszenarien (Voreinstellung, „Ruhiger Tag“, „Schichtwechsel-Stoßzeit“, „Volle Auslastung“): ERD und SPT hatten in den ersten beiden dieselbe mittlere Wartezeit und in den letzten beiden hatte SPT die kleinere. Die längste Wartezeit von SPT war nirgends kleiner als die von ERD, in den letzten beiden größer. FCFS hatte überall die längste Wartezeit und überall mindestens so viele pünktliche LKW wie die anderen.
• Last und Gleichstand: Bei höchstens etwa zwölf LKW an vier Toren und kleiner Konzentration ergaben ERD und SPT in allen geprüften Fällen dieselbe mittlere Wartezeit; mit wachsender LKW-Zahl wurde der Anteil gleicher Fälle kleiner und lag bei sehr vielen LKW nahe null. In der Voreinstellung war sie trotz bis zu drei gleichzeitig wartender LKW gleich.
• Einzelfälle gegen SPT: Bei geringer bis mittlerer Last war SPT in einzelnen Instanzen schlechter als ERD, meist um wenige Prozent der Gesamtwartezeit, in einem Fall um knapp ein Drittel. Die Aussage „in keiner Instanz schlechter“ gilt nur für die 120 gemessenen Instanzen, nicht für die Mischung insgesamt (die größere Nachmessung fand zwei Ausnahmen) und nicht allgemein.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Rangfolge SPT, ERD, FCFS in der mittleren Wartezeit auf den Zufallsinstanzen der Messmischung, einschließlich der Größenordnung der Ersparnisse.
• Dass das Neusetzen eines einzelnen LKW auf der SPT-Konstruktion nichts verbessert (Monotonie, in den geprüften Zufallsinstanzen bestätigt).
• Dass keine der drei Regeln unter dem exakten Optimum liegt. Die Demo prüft das mit einer Vollaufzählung auf winzigen Instanzen (wenige LKW, bis zu drei Tore); dort verlangt die Prüfung außerdem, dass der mittlere Abstand zum Optimum bei SPT höchstens so groß ist wie bei ERD und bei ERD höchstens so groß wie bei FCFS.

Was sie nicht belegt:

• Abstand zum Optimum bei echten Größen: Das Optimum ist nur auf winzigen Instanzen berechnet. Die Zahl der reinen Torzuordnungen wächst wie \(m^n\), die Reihenfolge je Tor kommt noch dazu, eine vollständige Aufzählung scheidet aus. Keine der drei Regeln hat eine Optimalitätsgarantie für mehrere Tore mit verschiedenen Wunschzeiten; Optimalität für kürzeste zuerst gilt nur, wenn alle LKW gleichzeitig verfügbar sind (Smith 1956 für ein Tor); mit verschiedenen Wunschzeiten und ohne Unterbrechung nicht mehr.
• Keine vollständige Suche: Dass Einzelverschiebung nichts findet, heißt nicht, dass ein besserer Plan fehlt (Beispiel oben). Ein anderer Nachbarschaftsbegriff, etwa das Umordnen ganzer Teilfolgen oder absichtlicher Leerlauf, wurde nicht geprüft.
• Mittelwert verdeckt die Verteilung: Die Rangfolge SPT, ERD, FCFS gilt für die mittlere Wartezeit. Bei der längsten Wartezeit liegt in den Nachrechnungen ERD vor SPT, FCFS bleibt am schlechtesten. Beim Anteil pünktlicher LKW liegt FCFS vorn, SPT knapp vor ERD. Die Demo zeigt die längste Wartezeit nicht als Zahl.
• Stark ausgelastete Messmischung: Die Ersparnisse in Minuten entstehen an Tagen mit Wartezeiten von Stunden. An ruhigen Tagen sind die Unterschiede klein oder null. Der Betriebstag der Messmischung ist nicht angegeben (voreingestellt zwölf Stunden), die Auslastung lässt sich deshalb nicht beziffern.
• Streuung: Angegeben sind Spannen über verschiedene Mischungen und Zufallsfolgen, keine Standardfehler oder Konfidenzintervalle. Die Zahl der Instanzen mit schlechterem ERD hängt von der Mischung ab.
• Erfundene Daten: Gleichverteilte Dauern und aus Gleich- und Normalverteilung gezogene Wunschzeiten; keine echten Anlieferdaten. Die Anmeldereihenfolge ist eine Zufallsreihenfolge, in echten Systemen hängt sie mit Wunsch und Dauer zusammen.
• Was fehlt: Pufferzeiten zwischen LKW am selben Tor, Torkompatibilität für Fahrzeugtypen, harte Zusagen statt Wunschzeiten, mehrtägige Planung mit Übertrag, Ausfälle und schwankende Dauern. Ein Metaheuristik-Verfahren ist nicht enthalten.

Erweiterungen und Verweise

Verwandte Demos dieser Website:

• Harte Zusagen statt Wunschzeiten: Die lkw-fristen-demo zählt die Zahl der LKW mit verpasster Frist und vergleicht die Regeln mit einem exakten Verfahren.
• Schlange vor dem Tor: Die gate-demo setzt auf dieser Terminvergabe auf und fragt, was ein Terminsystem an der Warteschlange vor dem Gate des Terminals bringt.

Quellen

• Smith (1956): Various optimizers for single-stage production. Naval Research Logistics Quarterly (kürzeste Bearbeitung zuerst für ein Tor ohne Wunschzeiten).
• Lenstra, Rinnooy Kan, Brucker (1977): Complexity of machine scheduling problems. Annals of Discrete Mathematics (NP-Schwere mit Freigabeterminen, schon für eine Maschine).
• Graham, Lawler, Lenstra, Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics (Drei-Feld-Notation).
• Quelltext und Prüfungen der Demo: github.com/sebastian-hanisch/truck-appointment-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Gedächtnis und sind nicht geprüft. Die Befundtabelle gibt die Messreihe der Demo wieder; Herleitungen, das Vier-LKW-Beispiel und die Nachrechnungen sind Rechnungen dieser Seite.