Die Hof-Disposition verständlich erklärt

Auf einem Firmenhof müssen wenige Fahrzeuge viele Ladekästen umsetzen, und jeder Auftrag hat eine Frist. Wer fährt was zuerst? Die Seite zeigt, was einfache Regeln leisten und was es wert ist, die kommenden Aufträge schon zu kennen.

Zuletzt aktualisiert: 11. November 2026

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

Ein Hof, wenige Fahrzeuge, viele Aufträge

Stellen Sie sich den großen Hof hinter einer Lagerhalle vor. Dort stehen abnehmbare Ladekästen für Lastwagen, die Wechselbrücken. Kleine Hoffahrzeuge kuppeln einen Kasten an, fahren ihn zu einem anderen Platz und stellen ihn ab. Eine solche Fahrt heißt hier Auftrag.

Die Aufträge treffen im Lauf des Vormittags ein. Jeder wird zu einer bestimmten Zeit freigegeben, erst dann darf der Kasten abgeholt werden. Jeder hat auch eine Frist, bis zu der der Kasten am Ziel stehen soll. Eine Minute Verspätung zählt bei den drei Sorten verschieden, das ist ihr Gewicht:

• Abfahrt: Der beladene Kasten fährt vom Hallentor zum Abfahrtsplatz, wo ein Lastwagen ihn abholt. Frist: die Abfahrt des Lastwagens. Gewicht 4.
• Bereitstellung: Ein angelieferter Kasten fährt vom Ankunftsplatz zum Hallentor und wird dort entladen. Frist: der Beginn des gebuchten Zeitfensters am Tor. Gewicht 2.
• Abräumen: Der leere Kasten fährt vom Tor auf einen Platz in der Mitte. Frist: großzügig. Gewicht 1.

Am Ende zählt die gewichtete Verspätung: die Minuten nach der Frist mal Gewicht, über alle Aufträge addiert. Warum gewichten? Ein verpasster Lastwagen ist ärgerlicher als ein leerer Kasten, der später geräumt wird. Bei gleichem Wert gewinnt der Plan mit weniger Leerfahrt, also Fahrt ohne Kasten zum nächsten Auftrag.

Die Seite beschreibt ein vereinfachtes Rechenbild (Fachwort: Modell) mit einem erfundenen Hof.

Wer fährt als Nächstes?

Wird ein Hoffahrzeug frei, muss entschieden werden, welcher Auftrag drankommt. Stellen Sie sich eine Einsatzleiterin vor, die die Aufträge per Funk bekommt. Einfache Regeln, die nur mit dem arbeiten, was schon eingegangen ist, heißen Online-Regeln:

• Wer zuerst kam (FIFO): Der älteste eingegangene Auftrag kommt zuerst dran, wie in der Schlange an der Kasse. Blind für: die Fristen.
• Frist zuerst (EDD): Der Auftrag mit der nächsten Frist kommt zuerst dran, wie bei Hausaufgaben mit Abgabetermin. Blind für: Gewicht und Weg.
• Abwägen (ATC): Die Regel wägt Wichtigkeit, Aufwand (Anfahrt plus Fahrt) und Zeitnot gegeneinander ab. Das gleicht Besorgungen vor Ladenschluss: Was Zeit hat, wartet, bei Zeitnot kommt das Wichtige und Kurze zuerst. Blind für: nichts davon.

Planen mit Vorwissen

Anders arbeitet, wer den Tagesplan schon kennt, etwa weil Lieferungen und Entladezeiten am Tor angemeldet sind. Das heißt hier Vorausplanung. Sie darf zwei Dinge. Erstens schickt sie ein Fahrzeug schon vor der Freigabe los. Es wartet dann am Abholplatz, und die Anfahrt ist erledigt, sobald es losgehen darf (vorpositionieren). Zweitens ordnet sie die Reihenfolge neu: Sie probiert für Aufträge andere Fahrzeuge und Plätze aus und behält jede Änderung, die den Plan verbessert. Das wiederholt sie mehrfach mit zufälligen Änderungen.

Warum können Online-Regeln das nicht? Ein freies Fahrzeug nimmt sofort einen bereitliegenden Auftrag, auch wenn bald ein dringenderer eintrifft, den es nicht kennen kann. Und es fährt erst nach der Freigabe los.

Der Vergleich ist bewusst nicht fair, denn die Vorausplanung weiß mehr. Er zeigt, was dieses Wissen wert ist. Als Gegenprobe dient ein Rechenprogramm, der Löser. Er sucht den besten Plan und kann beweisen, dass keiner besser ist. Dafür hat er zehn Sekunden, bei vielen Aufträgen reicht das nicht immer.

Was die Messung zeigt

Gemessen wurde die gewichtete Verspätung an erfundenen Auftragsfolgen, also zufällig erzeugten Abläufen. Drei Beispielhöfe haben viele Aufträge: eine Abfahrts-Stoßzeit, zu wenige Fahrzeuge und ein weitläufiger Hof. Je Hof gab es 20 Folgen für den Vergleich mit Vorwissen und 40 für den Vergleich der Regeln.

Vorwissen wirkt stark. Im Mittel über 20 Auftragsfolgen lag die Vorausplanung in allen drei Höfen unter der Hälfte der Verspätung der besten Online-Regel. Schon das Vorpositionieren allein senkte sie, das Neuordnen noch weiter. Warum? Die Anfahrt fällt in die Wartezeit statt hinter die Freigabe. Das ist mehr, als der Wechsel von Frist zuerst zu ATC bringt.

Wer zuerst kam, schnitt am schlechtesten ab. Im Mittel über 40 Auftragsfolgen war FIFO in allen drei Höfen deutlich am schlechtesten. Warum? Ein Auftrag mit knapper Frist wartet hinter älteren, die noch Zeit haben.

Die klügste Online-Regel gewinnt im Mittel, aber nicht jeden Tag. ATC senkte die Verspätung gegenüber Frist zuerst im Mittel in allen drei Höfen. Auf einzelnen Folgen war ATC aber nur in 13, 25 und 15 von je 40 besser (Stoßzeit, zu wenige Fahrzeuge, weitläufiger Hof). In den übrigen war es schlechter oder gleich.

Wie passt das zusammen? Denken Sie an Wartezeiten beim Arzt: Meist ist es ähnlich, an wenigen sehr vollen Tagen ist es lang, und diese Tage bestimmen den Durchschnitt. Wo ATC gewann, holte es im Mittel viel heraus. Wo es verlor, verlor es im Mittel wenig (Nachrechnung dieser Seite). Öfter gewann Frist zuerst in den beiden anderen Höfen, ATC im Hof mit zu wenigen Fahrzeugen.

Bei wenig Betrieb gibt es nichts zu verbessern. In einem ruhigen Beispielvormittag kam mit keinem Verfahren ein Auftrag zu spät. Wenn die Fahrzeuge die Arbeit locker schaffen, rettet keine Reihenfolge mehr eine Frist.

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 Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Häufige Missverständnisse

• „Die Vorausplanung findet den besten Plan.“ Bei bis zu 16 Aufträgen traf sie in neun oder zehn von je zehn Fällen den besten Plan, den der Löser fand. Bei vielen Aufträgen und wenigen Fahrzeugen nicht: Im Beispiel mit zu wenigen Fahrzeugen fand sie mit mehr Wiederholungen einen besseren Plan, der in der Demo aber zu lange gedauert hätte. Bei 30 Aufträgen konnte der Löser den besten Plan meist nicht beweisen, dann weiß niemand sicher, ob ein besserer existiert. Halb so viel Verspätung wie die beste Online-Regel heißt nicht bestmöglich.
• „Kürzere Wege sind das Ziel.“ Nein. Hier geht die Pünktlichkeit vor: Ein Plan mit mehr Leerfahrt gewinnt, wenn er weniger gewichtete Verspätung hat. Warum? Ein Lastwagen, der wegen eines Umwegs zu spät abfährt, kostet mehr als ein paar Minuten Fahrt.
• „Wer vorausplant, hat das Problem gelöst.“ Nein. Die Vorausplanung kennt alle Aufträge genau, und im Rechenbild geht nichts schief. In Wirklichkeit fällt ein Fahrzeug aus, oder eine Anlieferung kommt später.

Woran Sie das im Alltag erkennen

• Eine Paketbotin mit fester Route ist früher am Ziel als ein Fahrer, dem erst unterwegs Aufträge durchgegeben werden.
• Nicht jede verpasste Frist ist gleich schlimm: Den Zug zu verpassen kostet mehr, als eine Rechnung einen Tag später zu bezahlen.

Wie ernst ist das Rechenbild zu nehmen?

Aufträge, Wege und Fristen sind zufällig erzeugt, und es gibt keine Pausen und keine blockierten Tore. Die Aussagen gelten für dieses Rechenbild, nicht für jeden echten Hof.

Was Sie mitnehmen:

• Fragen Sie bei jedem Plan zuerst, wie viel vom Kommenden schon bekannt ist, bevor Sie über die Regel streiten.
• Prüfen Sie eine Regel an vielen Tagen und nicht an einem.
• Fragen Sie, was eine verpasste Frist wirklich kostet, bevor Sie alle Fristen gleich behandeln.

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 ein erfundener Betriebshof mit zufällig erzeugten Fahraufträgen; alle Zahlen gelten nur für diese erzeugten Instanzen.

• Hof und Fahrzeuge: Tore an der Hallenwand, dahinter drei Stellplatzfelder (Ankunft, Mittelfeld, Abfahrt). \(m\) identische Hoffahrzeuge stehen zur Zeit 0 am Depot und bleiben nach ihrem letzten Auftrag stehen; ein Rückweg zum Depot ist nicht modelliert. Wege sind rechtwinklig (Manhattan) und auf ganze Minuten aufgerundet; Kupplungszeit und Hofgeschwindigkeit sind fest. Alle Zeiten sind ganze Minuten, damit Heuristik, Prüfung und exakter Löser dieselbe Anfahrtsmatrix lesen.
• Aufträge: \(n\) Aufträge \(j\). Jeder verschiebt eine Wechselbrücke, wird zur Zeit \(r_j\) freigegeben, dauert \(p_j\) (Servicezeit: An- und Abkuppeln plus beladene Fahrt, ohne Anfahrt), hat die Frist \(d_j\) (Ende des Auftrags) und das Gewicht \(w_j\). Die Anfahrt \(\tau_{ij}\) ist die Leerfahrt vom Abstellort des Auftrags \(i\) zum Abholort von \(j\); \(\tau_{0j}\) gilt ab dem Depot. Mit der Startzeit \(S_j \ge r_j\) (das Fahrzeug steht am Abholort und kuppelt an) ist die Verspätung \(T_j = \max\{0,\; S_j + p_j - d_j\}\).
• Zufallsgenerator: Die Freigaben fallen in ein Zeitfenster; ein einstellbarer Anteil häuft sich als Welle um die Fenstermitte (Stoßzeit-Anteil), der Rest ist gleichmäßig verteilt. Weitere Regler: Anteil der Abfahrtsaufträge, mittlerer Fristpuffer (Abfahrten erhalten davon den kleinsten Anteil, Abräumfahrten den größten), Hoflänge, Zahl der Tore, Zahl der Aufträge und der Fahrzeuge. Voreinstellungen laut Messbedingungen: Stoßzeit-Anteil 70 %, Abfahrts-Anteil 45 %, Hoflänge 450 m, 10 Tore, Fristpuffer 15 min.
• Belastungsgrad: Faustgröße \(\rho = (\sum_j p_j + n\,\bar\tau) / (m\,F)\) mit der mittleren Anfahrt \(\bar\tau\) zwischen zwei Aufträgen und der Länge \(F\) des Freigabefensters. Wellen und Fristen bildet sie nicht ab.

Auftragsart	Weg	Frist	Gewicht
Abfahrt	Tor → Abfahrtsfeld	Abfahrt der Linie	4
Bereitstellung	Ankunftsfeld → Tor	Beginn des Tor-Slots	2
Abräumen	Tor → Mittelfeld	großzügig	1

• Online-Regeln: Wird zur Zeit \(t\) ein Fahrzeug frei, sehen sie nur Aufträge mit \(r_j \le t\). Ein freies Fahrzeug wartet nur, wenn kein freigegebener Auftrag offen ist (nicht verzögernd). Die Anfahrt beginnt frühestens bei der Freigabe, und die Pläne behalten diese tatsächlichen Startzeiten. FIFO wählt den ältesten freigegebenen Auftrag, Frist zuerst (EDD) den mit der nächsten Frist; beide setzen das freie Fahrzeug mit der kürzesten Anfahrt ein. ATC wählt das (Fahrzeug, Auftrag)-Paar mit dem größten Index (Formel unten) mit \(K = 1\).
• Gleiche Reihenfolge, vorpositioniert: die Reihenfolge der besten Online-Regel (nach Zielwert), mit frühestmöglichen Zeiten ausgewertet, ohne Umplanen. Diese Stufe trennt den Wert des Vorpositionierens vom Wert des Umplanens.
• Vorausplanung: Sie kennt alle Aufträge im Voraus (etwa durch Avisierung und Tor-Slots). Sie startet bei den Reihenfolgen der drei Online-Regeln, wertet jede mit frühestmöglichen Zeiten aus (das Fahrzeug fährt sofort los und wartet am Abholort bis zur Freigabe) und verbessert sie durch Umhängen (ein Auftrag an eine andere Stelle oder zu einem anderen Fahrzeug) und Tauschen. Die beste Lösung wird mit Iterated Local Search nachgeschärft: zufälliges Umhängen von drei Aufträgen, erneutes Polieren, Übernahme nur nicht schlechterer Ergebnisse; 40 Iterationen, fester Startwert des Zufallsgenerators, daher deterministisch.
• Exakter Löser: OR-Tools CP-SAT mit AddMultipleCircuit auf den Bögen \(x_{ij}\), 10 s Zeitlimit, auf Klick, mit der Vorausplanung als Startpunkt. Ohne Optimalitätsbeweis ist „Exakt“ die beste gefundene Lösung.
• Ziel: lexikografisch. Erst die gewichtete Verspätung, bei Gleichstand die Leerfahrtzeit. Die Verspätung hat strikten Vorrang.

Die Formeln

Das Problem ist ein Scheduling-Problem auf parallelen Maschinen mit Freigabezeiten und reihenfolgeabhängigen Rüstzeiten (hier die Anfahrten), in der Notation von Graham et al. \(Pm \mid r_j, s_{ij} \mid \sum_j w_j T_j\). Schon der Spezialfall mit einer Maschine, ohne Freigaben und ohne Rüstzeiten, \(1 \,\|\, \sum_j w_j T_j\), ist stark NP-schwer (Lenstra, Rinnooy Kan, Brucker; siehe Quellen).

Modell. Die Variable \(x_{ij} \in \{0,1\}\) sagt, ob ein Fahrzeug den Auftrag \(j\) direkt nach dem Auftrag \(i\) bedient (Knoten 0 ist das Depot). Dazu kommen die Startzeit \(S_j\) und die Verspätung \(T_j\). Jeder Auftrag hat genau einen Vorgänger und einen Nachfolger, jeweils möglicherweise das Depot, und höchstens \(m\) Fahrzeuge verlassen das Depot (hier laufen \(j\) und \(i \ge 1\) über die Aufträge):

\[\sum_{i \ne j} x_{ij} = 1 \;\; \forall j, \qquad \sum_{j \ne i} x_{ij} = 1 \;\; \forall i \ge 1, \qquad \sum_{j} x_{0j} \le m\]

Zeitbedingungen. Der Bogen zum Depot kostet weder Zeit noch Kosten (\(\tau_{i0} := 0\)). Teilkreise ohne Depot schließen diese Bedingungen wegen \(p_i > 0\) ohnehin aus, denn die Startzeiten müssten entlang eines Kreises dauernd wachsen; der Löser verwendet dafür zusätzlich die Kreisbedingung AddMultipleCircuit:

\[x_{0j} = 1 \Rightarrow S_j \ge \tau_{0j}, \qquad x_{ij} = 1 \Rightarrow S_j \ge S_i + p_i + \tau_{ij}, \qquad T_j \ge S_j + p_j - d_j, \;\; T_j \ge 0\]

Ziel: primär die gewichtete Verspätung, sekundär die gesamte Leerfahrtzeit (verhindert Umwege bei gleich guter Verspätung), mit \(W\) so groß, dass die Leerfahrt nie eine Verspätung aufwiegen kann:

\[\min \; \Big(\sum_j w_j T_j\Big) \cdot W \;+\; \sum_{i,j} \tau_{ij}\, x_{ij}\]

ATC-Index in der Form der Demo (angelehnt an Vepsäläinen, Morton 1987; die Anfahrtszeit geht nach dem Vorbild der ATCS-Regel von Lee, Bhaskaram, Pinedo 1997 ein, aber nicht in deren vollständiger Form). Wird zur Zeit \(t\) ein Fahrzeug frei, bekommt jedes Paar aus wartendem Auftrag \(j\) und freiem Fahrzeug einen Index; \(\tau\) ist die Anfahrt dieses Fahrzeugs zu \(j\). \(\bar p\) ist die mittlere Servicezeit aller Aufträge, \(K\) der Vorblick-Parameter. Gestartet wird das Paar mit dem größten Index:

\[I_{j} \;=\; \frac{w_j}{p_j + \tau}\,\exp\!\Big(-\frac{\max\{0,\; d_j - (t + \tau + p_j)\}}{K\,\bar p}\Big)\]

Der Bruch \(w_j/(p_j+\tau)\) ist das Gewicht pro Aufwand. Der Exponentialterm liegt in \((0, 1]\) und misst die Dringlichkeit am Restpuffer \(\sigma_j = d_j - (t + \tau + p_j)\), der Frist minus dem voraussichtlichen Ende bei sofortigem Start. Bei \(\sigma_j \le 0\) ist er 1, bei großem Puffer nahe 0. Mit wachsendem \(K\) zählen mehr Aufträge als dringend; für \(K \to \infty\) bleibt nur \(w_j/(p_j+\tau)\).

Startzeiten. Für eine feste Reihenfolge je Fahrzeug mit Vorgänger \(i\) und Ende \(E_i = S_i + p_i\) (für den ersten Auftrag \(E = 0\) und \(\tau_{0j}\)) rechnet die Vorausplanung mit frühestmöglichen Zeiten \(S_j = \max\{r_j,\; E_i + \tau_{ij}\}\). Die Online-Regeln dagegen starten die Anfahrt erst ab der Freigabe, also \(S_j \ge r_j + \tau_{ij}\). Der Unterschied ist das Vorpositionieren.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum Vorpositionieren bei gleicher Reihenfolge nie schadet. Es seien \(S^o_j, E^o_j\) die Start- und Endzeiten des Online-Plans und \(S^v_j, E^v_j\) die des vorpositionierten Plans derselben Reihenfolge.

• Schritt 1 (Anfang): Für den ersten Auftrag \(j\) eines Fahrzeugs gilt \(S^v_j = \max\{r_j, \tau_{0j}\} \le r_j + \tau_{0j} \le S^o_j\), also \(E^v_j \le E^o_j\).
• Schritt 2 (Fortsetzung): Gelte \(E^v_i \le E^o_i\) für den Vorgänger \(i\). Online ist \(S^o_j \ge E^o_i + \tau_{ij}\) (das Fahrzeug muss frei sein) und \(S^o_j \ge r_j + \tau_{ij} \ge r_j\). Daraus folgt \(S^v_j = \max\{r_j, E^v_i + \tau_{ij}\} \le \max\{r_j, E^o_i + \tau_{ij}\} \le S^o_j\), also wieder \(E^v_j \le E^o_j\), denn die Servicezeit ist dieselbe.
• Schritt 3: Kein Auftrag endet später, also ist keine Verspätung größer, und die gewichtete Summe ist nicht größer. Die Leerfahrtzeit ist gleich, weil die Reihenfolge gleich ist. Der lexikografische Zielwert wird nicht größer.
• Bedingung: Das Modell kennt keine Tor- oder Platzblockade und keine Fahrerpausen. Ein Fahrzeug, das am Abholort wartet, behindert niemanden. Das Vorpositionieren ist im Rechenbild kostenfrei; in einem Hof mit Blockaden gilt der Schluss nicht.

Warum die Vorausplanung nie schlechter ist als die beste Online-Regel.

• Schritt 1: Sie startet bei den drei Online-Reihenfolgen, mit frühestmöglichen Zeiten bewertet. Nach der vorigen Herleitung ist jede nicht schlechter als die Online-Regel, aus der sie stammt.
• Schritt 2: Die lokale Suche übernimmt nur echte Verbesserungen des Zielwerts, die Iterated Local Search nur nicht schlechtere Ergebnisse, und die beste Lösung bleibt erhalten. Das Ergebnis ist also nicht schlechter als jeder Start.
• Bedingung: Die Aussage gilt je Instanz und für denselben lexikografischen Zielwert. Sie sagt nichts über den Abstand zum Optimum.

Warum ein Mittelwert die Rangfolge von Fall zu Fall umkehren kann (ATC gegen Frist zuerst). Sei \(N\) die Zahl der Instanzen, \(n_+\) und \(n_-\) die Zahl der Instanzen, in denen ATC besser bzw. schlechter ist (Gleichstände zählen zu keiner der beiden Gruppen), und \(\bar g\) bzw. \(\bar l\) die mittlere Höhe des Gewinns bzw. Verlusts. Die mittlere Differenz der Verspätungen ist \((n_+ \bar g - n_- \bar l)/N\). ATC ist im Mittel besser genau dann, wenn \(n_+ \bar g > n_- \bar l\) gilt. Bei weniger Gewinnen als Verlusten verlangt das \(\bar g > (n_-/n_+)\,\bar l\): Wenige große Gewinne können viele kleine Verluste überwiegen.

Nachgespielt (Rechnung dieser Seite): Mit den 40 Instanzen je Konfiguration waren in allen drei Konfigurationen die mittleren Gewinne an den gewonnenen Instanzen mehr als dreimal so groß wie die mittleren Verluste an den verlorenen. In zwei der drei Konfigurationen liegt der Median von ATC über dem von Frist zuerst, in der Konfiguration mit zu wenigen Fahrzeugen darunter. Das erklärt, warum ATC im Mittel gewinnt und trotzdem in zwei der drei Konfigurationen auf der Mehrheit der Instanzen verliert.

Durchgerechnet: Vorpositionieren und Gewicht

Beide Beispiele sind konstruierte Fälle und Rechnungen dieser Seite, keine Messungen der Demo.

Zu spät losgefahren. Ein Fahrzeug, ein Abfahrtsauftrag \(j\) mit \(w_j = 4\) und ohne Fristpuffer, also \(d_j = r_j + p_j\). Das Fahrzeug braucht \(\tau_{0j} \le r_j\) für die Anfahrt vom Depot. Online startet es erst bei der Freigabe: \(S_j = r_j + \tau_{0j}\), Ende \(r_j + \tau_{0j} + p_j\), Verspätung \(\tau_{0j}\), gewichtet \(4\,\tau_{0j}\). Vorpositioniert startet es bei \(\max\{r_j, \tau_{0j}\} = r_j\), endet bei \(d_j\) und hat keine Verspätung. Das späte Losfahren kostet also genau die Anfahrtszeit, mit dem Gewicht multipliziert.

Der schwere Auftrag zuerst. Ein Fahrzeug, zwei zur Zeit 0 freigegebene Aufträge mit gleicher Servicezeit \(p\): \(A\) eine Abfahrt (\(w_A = 4\)), \(B\) ein Abräumen (\(w_B = 1\)). Beide haben die Anfahrt \(\tau_0\) vom Depot und die Frist \(d = \tau_0 + p\), die für genau einen reicht; zwischen beiden beträgt die Anfahrt \(\tau\).

• Reihenfolge A, B: \(A\) endet bei \(d\), pünktlich. \(B\) beginnt bei \(\tau_0 + p + \tau\) und endet bei \(d + p + \tau\). Verspätung \(p + \tau\), gewichtet \(1 \cdot (p + \tau)\).
• Reihenfolge B, A: Ebenso, nur mit dem Gewicht von \(A\): \(4\,(p + \tau)\). Die Reihenfolge A, B spart \(3\,(p + \tau)\).
• Was die Regeln tun: FIFO und Frist zuerst sehen gleiche Freigabe und gleiche Frist und können nur nach der Auftragsnummer entscheiden. ATC hat für beide den Restpuffer \(\sigma = d - (0 + \tau_0 + p) = 0\), der Exponentialterm ist 1, und der Index ist \(w/(p + \tau_0)\). Der Auftrag \(A\) bekommt den vierfachen Index und fährt zuerst.

Befunde

Kurz:

• Im Mittel liegt die Vorausplanung unter der Hälfte der besten Online-Regel; schon das Vorpositionieren allein bringt einen großen Teil davon.
• FIFO ist die schlechteste Regel; ATC senkt den Mittelwert gegenüber Frist zuerst, verliert aber in zwei von drei Konfigurationen auf der Mehrheit der Instanzen.
• Bei wenigen Aufträgen liegt die Vorausplanung nahe am bewiesenen Optimum; bei hoher Last bleibt eine Restlücke.
• Alle Zahlen gelten für erzeugte Instanzen mit exaktem Vorwissen; die Grenzen stehen im Abschnitt danach.

Alle Zahlen sind Mittelwerte der gewichteten Verspätung (in Punkten; ein Punkt ist eine mit dem Gewicht multiplizierte Verspätungsminute) über zufällig erzeugte Instanzen der genannten Konfiguration. „Beste Online-Regel“ heißt: je Instanz die Regel mit dem besten Zielwert, danach gemittelt; der Wert liegt deshalb unter dem Mittel jeder einzelnen Regel. Die Tabellen nutzen verschiedene Stichproben und sind nicht untereinander vergleichbar. Die Instanzen sind durchnummeriert. Ein Nachspielen dieser Seite mit den Nummern 1 bis 20 (erste Tabelle) bzw. 1 bis 40 (ATC und Frist zuerst) reproduziert die Tabellenwerte.

Konfiguration	beste Online-Regel	gleiche Reihenfolge, vorpositioniert	Vorausplanung
Abfahrts-Stoßzeit (30 Aufträge, 3 Fahrzeuge)	70,2	51,5	31,1
Zu wenig Hoffahrzeuge (32 Aufträge, 2 Fahrzeuge)	170,6	138,9	80,7
Weitläufiger Hof (30 Aufträge, 4 Fahrzeuge, 850 m)	59,8	35,1	14,2

Vorwissen wirkt in diesen Konfigurationen stark: Die Vorausplanung liegt in allen drei Zeilen unter der Hälfte der besten Online-Regel, und schon das Vorpositionieren allein senkt den Wert. Sein Anteil an der gesamten Ersparnis liegt zwischen gut einem Drittel und etwas mehr als der Hälfte (Rechnung dieser Seite aus der Tabelle). Das ist mehr, als die Wahl zwischen Frist zuerst und ATC bringt (nur ein Zehntel bis ein Fünftel, siehe unten). Die Flottengröße wurde in der Messreihe nicht verglichen. In einer Rechnung dieser Seite (nur Online-Regeln, beste je Instanz, Instanzen 1 bis 20) senkt ein zusätzliches Fahrzeug den Wert im Stoßzeit-Hof auf etwa ein Zwanzigstel und im weitläufigen Hof auf gut ein Fünftel, also unter den Wert der Vorausplanung mit der alten Fahrzeugzahl. Ein Fahrzeug mehr kann in diesem Rechenbild mehr bringen als Vorwissen.

FIFO, Frist zuerst und ATC (Mittel über 40 Instanzen). FIFO ist deutlich am schlechtesten; nachgespielt ist es in fast jeder Instanz die schlechteste der drei Regeln. ATC senkt den Mittelwert gegenüber Frist zuerst, aber nicht auf jeder Instanz. Die Zahlen für „schlechter“ und „gleich“ in Klammern sind eine Nachrechnung dieser Seite:

Konfiguration	Frist zuerst	ATC	Instanzen mit ATC besser (schlechter, gleich)
Abfahrts-Stoßzeit	92	82	13 von 40 (25, 2)
Zu wenig Hoffahrzeuge	215	172	25 von 40 (13, 2)
Weitläufiger Hof	83	72	15 von 40 (22, 3)

Welche Regel öfter gewinnt, hängt von der Konfiguration ab: In den zwei Konfigurationen mit dem kleineren Belastungsgrad (Stoßzeit und weitläufiger Hof; Mittel über 40 Instanzen, Rechnung dieser Seite) gewinnt Frist zuerst auf mehr Instanzen, in der mit dem größten (zu wenig Fahrzeuge, etwa neun Zehntel) ATC. Mit noch weniger Fahrzeugen gewann ATC in der Nachrechnung dieser Seite öfter: im Stoßzeit-Hof mit zwei statt drei Fahrzeugen (Belastungsgrad etwa eins) auf allen 40 Instanzen. Eine Konfiguration mit Überlast zeigt die Tabelle nicht. Der Parameter \(K\) ist flach: Werte von 0,3 bis 3 liegen im Mittel innerhalb von etwa 10 % gegenüber \(K = 1\) (Messreihe; die Nachrechnung dieser Seite an den drei Konfigurationen mit 40 Instanzen bestätigt es). Gewählt ist \(K = 1\).

Geringe Last. Bei den Einstellungen des ruhigen Vormittags (Belastungsgrad etwa 20 %) gibt es mit den drei Online-Regeln keine Verspätung (nachgespielt in allen 40 Instanzen); die Verfahren unterscheiden sich nur in der Leerfahrt. In einer ruhigen Beispielinstanz (Einzelfall, kein Mittel) sind es 18 statt 23 min gegenüber der besten Online-Regel; FIFO und Frist zuerst haben 23 min, ATC allein 33 min.

Lokale Suche gegen ILS gegen Exakt. Messbedingungen: 3 Fahrzeuge, Zeitfenster der Freigaben \(\max(60,\,4n)\) min bei \(n\) Aufträgen, Fristpuffer 10 min, sonst die Voreinstellungen, Instanzen 0 bis 9 (bei 30 Aufträgen 0 bis 5), Belastungsgrad im Mittel je Zeile etwa 46 bis 67 % (einzelne Instanzen von gut 40 bis 70 %, Rechnung dieser Seite). „Nur Umhängen und Tauschen“ ist die lokale Suche aus allen drei Online-Reihenfolgen ohne ILS. Ein Treffer ist eine Instanz, in der die Methode den besten Zielwert (gewichtete Verspätung, dann Leerfahrt) erreicht; er zählt nur gegen bewiesene Optima. Der Löser lief 10 s mit der ILS-Lösung als Startpunkt, und „Exakt“ ist bei nicht bewiesenen Instanzen die beste gefundene Lösung.

Aufträge / Fahrzeuge	nur Umhängen und Tauschen (Treffer)	mit ILS, 40 Iterationen (Treffer)	Ø Verspätung lokal / ILS / Exakt	Laufzeit ILS
10 / 3	6 von 10	10 von 10	1,4 / 1,4 / 1,4	0,03 s
12 / 3	6 von 10	9 von 10	2,8 / 2,8 / 2,8	0,06 s
16 / 3	1 von 10	9 von 10	6,0 / 5,2 / 5,2	0,10 s
30 / 3 (Ø über alle 6 Instanzen; Exakt nur in 2 bewiesen, Treffer nur über diese 2)	0 von 2	1 von 2	30,3 / 27,8 / 27,7	0,69 s

Bei 10 und 12 Aufträgen unterscheiden sich die Verfahren fast nur in der Leerfahrtzeit (mittlere Verspätung identisch); bei 16 Aufträgen senkt ILS auch die mittlere Verspätung gegenüber der lokalen Suche, doch der ganze Unterschied stammt von einer der zehn Instanzen (Nachrechnung dieser Seite); bei 30 Aufträgen sinkt sie in vier von sechs Instanzen. Bei sehr hoher Last bleibt eine Restlücke: In einer Beispielinstanz mit zu wenigen Fahrzeugen liegt die Vorausplanung mit 40 Iterationen bei 36, mit 250 Iterationen und im 10-s-Lauf des Lösers (nicht als optimal bewiesen) bei 31. 250 Iterationen würden im ungünstigsten Fall über 6 s je Änderung eines Einstellers in der Demo kosten.

Der exakte Löser. Sein Modell stimmt auf kleinen Fällen mit der Aufzählung aller Reihenfolgen und Fahrzeugzuschnitte überein (5 Aufträge, 2 und 3 Fahrzeuge: identische Optima). Beweisbarkeit unter den Messbedingungen der Tabelle:

• bis 12 Aufträge: 10 von 10 bewiesen, im Mittel 0,02 bis 0,04 s, höchstens 0,12 s
• 22 Aufträge (8 Instanzen): 5 von 8 bewiesen, im Mittel 4,9 s
• 30 Aufträge: nur 2 von 6 innerhalb des Zeitlimits; mit großzügigeren Fristen und längerem Zeitfenster (Voreinstellungen, Puffer 15 min) 4 von 6

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Rangfolge beste Online-Regel, vorpositioniert, Vorausplanung im Mittel über 20 Instanzen in allen drei Konfigurationen. Je Instanz folgt „nicht schlechter“ aus den Herleitungen; nachgespielt wurde es in allen 40 bzw. 20 Instanzen je Konfiguration eingehalten.
• FIFO ist im Mittel deutlich am schlechtesten. ATC senkt den Mittelwert gegenüber Frist zuerst, ohne auf jeder Instanz zu gewinnen.
• Das Löser-Modell stimmt auf den kleinen Prüfinstanzen mit der Aufzählung überein.

Was sie nicht belegt:

• Kleine Stichproben: 20 bzw. 40 Instanzen je Konfiguration, höchstens zehn je Zeile der ILS-Tabelle, bei 30 Aufträgen nur sechs Instanzen mit zwei bewiesenen. Es gibt keine Konfidenzintervalle. Wo ATC und Frist zuerst dicht beieinander liegen, ist die Rangfolge nicht gesichert.
• Drei ausgewählte Konfigurationen: Ob die Rangfolge in anderen Parameterbereichen gilt, zeigt die Messung nicht. Bei geringer Last verschwindet sie.
• Exaktes Vorwissen und Suchaufwand: Die Vorausplanung kennt Freigaben, Dauern und Fristen genau, Störungen gibt es nicht. Die Lücke zu den Online-Regeln mischt zwei Wirkungen: Vorabinformation und Optimierungsaufwand (lokale Suche und ILS gegen Regeln, die nur den nächsten Schritt wählen). Nur die Stufe „vorpositioniert“ trennt einen Teil davon; eine Online-Regel mit anschließender Optimierung fehlt. Der Wert unsicherer Vorabinformation ist nicht gemessen.
• Kostenloses Vorpositionieren: Es gibt keine Tor- oder Platzblockade und keine Fahrerpausen. Wie viel vom Hebel in der Praxis bleibt, zeigt die Messung nicht.
• Regelklasse: Die Online-Regeln sind nicht verzögernd und ohne Blick auf kommende Freigaben. Eine Online-Regel, die kurz auf einen dringenden Auftrag wartet oder ein Fahrzeug schon zu einem erwarteten Ort schickt, gehört nicht zum Vergleich; der Befund gilt für diese Regelklasse.
• Setzungen: Die Gewichte 4, 2 und 1 und der Fristpuffer sind Setzungen. Die genannte Messreihe prüft sie nicht gezielt; gezielt geprüft ist nur \(K\).
• Löser und Rechner: Ohne Beweis ist „Exakt“ nur die beste gefundene Lösung. Beweisbarkeit und Rechenzeiten hängen vom Rechner ab, der Löser nutzt mehrere Rechenkerne; auf anderer Hardware können andere Instanzen bewiesen werden.
• Weitere Vereinfachungen: kein Rückweg zum Depot, feste Kupplungszeit und Hofgeschwindigkeit, rechtwinklige Wege. Die Belastungsgrade lassen sich aus den hier genannten Angaben nicht nachrechnen, weil Kupplungszeit und Geschwindigkeit nicht angegeben sind.

Erweiterungen und Verweise

Verwandte Demos dieser Website:

• Störungen: Die hofrobust-demo lässt ein Hoffahrzeug ausfallen oder die Fahrzeiten schwanken und vergleicht starren Vorausplan, Online-Regeln und reaktives Nachplanen. Sie prüft also gerade die Annahme, die diese Seite offen lässt: genaues Vorwissen.
• Parken: Die hofstellplatz-demo entscheidet, wo ankommende Wechselbrücken abgestellt werden. Hier sind die Abstellorte der Aufträge gegeben.
• Ankunftstermine: Die truck-appointment-demo vergibt Ankunftstermine an anliefernde Lkw. Die Hof-Disposition betrifft die Fahrzeuge dazwischen, das Umsetzen der Brücken auf dem Hof; Freigaben und Fristen sind hier gegeben.
• Nicht umgesetzt: Tor-Belegung als Ressource, ein Rückweg zum Depot und fortlaufendes Neuplanen bei neu eintreffenden Aufträgen.

Quellen

• Vepsäläinen, Morton (1987): Priority rules for job shops with weighted tardiness costs. Management Science 33 (ATC-Index).
• Lee, Bhaskaram, Pinedo (1997): A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions 29 (ATCS; die Demo übernimmt davon nur die Anfahrtszeit).
• Graham, Lawler, Lenstra, Rinnooy Kan (1979): Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5 (Notation).
• Lenstra, Rinnooy Kan, Brucker (1977): Complexity of machine scheduling problems. Annals of Discrete Mathematics 1 (NP-Schwere).
• Lourenço, Martin, Stützle (2003): Iterated local search. In: Glover, Kochenberger (Hrsg.): Handbook of Metaheuristics. Kluwer Academic Publishers (heute Springer).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/yard-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der Demo und aus dem Gedächtnis und sind nicht geprüft. Die Befundtabellen geben die Messreihen der Demo wieder. Herleitungen, Durchgerechnetes und das Nachspielen der Instanzen 1 bis 40 (Gewinne, Verluste, Mediane, FIFO-Rang) sind Rechnungen dieser Seite.