Das Doppelspiel am Kran verständlich erklärt
Ein Containerkran löscht und lädt meist nacheinander und fährt dabei oft leer zurück. Beim Doppelspiel lädt er nach dem Löschen gleich wieder. Diese Seite erklärt zuerst ohne Formeln, warum das Zeit spart und warum es auf die Reihenfolge der Stapel ankommt, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Ein Kran, der leer zurückfährt
Ein Containerkran löscht, das heißt, er nimmt Container vom Schiff und setzt sie an Land ab. Danach lädt er, er hebt also Container an Land auf das Schiff. Meistens macht er beides nacheinander: erst alles löschen, dann alles laden. Dabei fährt er oft leer zurück, denn nach dem Löschen hat er nichts mehr am Haken.
Beim Doppelspiel setzt er nach dem Löschen gleich einen Container auf das Schiff. Ein Einzelspiel erledigt eine Aufgabe, entweder löschen oder laden. Ein Doppelspiel erledigt zwei Aufgaben in einem Spiel, nämlich löschen und laden.
Warum hängt es von der Reihenfolge ab?
Ein Schiff ist in Abschnitte unterteilt, die Bays heißen. Ein Bay besteht aus mehreren Stapeln von Containern. Geladen werden darf nur in einen Stapel, der schon leer ist, denn solange noch Container darin stehen, ist kein Platz.
Deshalb entscheidet die Reihenfolge, in der die Stapel geleert werden, wie oft sich zwei Aufgaben zu einem Doppelspiel paaren lassen. Ein Stapel, der früh leer ist, schafft früh Platz für Ladungen. Beim allerersten Stapel ist noch kein Platz frei, deshalb kann dort kein Doppelspiel entstehen.
Welche Vorgehen verglichen werden
Die Demo vergleicht vier Vorgehen. Das erste kennt kein Doppelspiel: erst alles löschen, dann alles laden. Das zweite leert die Stapel von links nach rechts. Das dritte beginnt mit den Stapeln, aus denen am wenigsten zu löschen ist, denn die sind am schnellsten leer. Das vierte ist die Regel von Johnson, ein altes Verfahren der Reihenfolgeplanung für Fertigungslinien mit zwei Stationen. Hier sind die beiden Stationen Löschen und Laden. Johnsons Regel braucht beweisbar die wenigsten Spiele, deshalb braucht die Demo keinen Löser, also kein Rechenprogramm, das die beste Lösung erst sucht.
Als Maßstab zeigt die Demo außerdem eine untere Schranke. Sie sagt, wie wenige Spiele es höchstens werden können, weil ein Spiel nie mehr als einen Container löscht und einen lädt. Sie ist kein Verfahren.
Was bringt das Doppelspiel?
Das Doppelspiel spart Kranzeit. Am meisten spart es, wenn sich Laden und Löschen die Waage halten, denn dann lassen sich besonders viele Aufgaben paaren. Die Reihenfolge der Stapel macht nur einen Teil des Gewinns aus: Schon die einfache Reihenfolge von links nach rechts spart viel, die beste spart noch etwas mehr.
Die einfache Regel „kurze Entladung zuerst“ ist bei viel Beladung so gut wie Johnsons Regel. Bei wenig Beladung liegt Johnson meist vorn. Die Regel „größte Entladung zuerst“ ist sogar schlechter als die Reihenfolge von links nach rechts. Die Zahlen dazu stehen im Fachteil.
Wie ernst ist das Modell zu nehmen?
Die Demo ist ein vereinfachtes Modell aus der Literatur. Sie kennt keine Fahrzeiten zwischen den Stapeln, keine Lukendeckel und keine Stabilität des Schiffs beim Laden, und alle Spiele dauern gleich lang. Wie viel länger ein Doppelspiel dauert als ein Einzelspiel, ist eine Annahme. Die Löschzahlen und Ladezahlen sind zufällig gezogen und stammen nicht aus einem echten Stauplan.
Alle Ergebnisse sind Größenordnungen aus einer Simulation, keine Messung an echten Kranspielen. Die Demo zeigt, wie die Mechanik wirkt, nicht wie viel Zeit ein bestimmter Hafen spart.
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. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.
- Bay: \(S\) Stapel; Stapel \(i\) hat \(u_i\) zu löschende und \(l_i\) zu ladende Container (ganzzahlig, aus dem Zufalls-Seed gezogen: je Lage wird mit dem eingestellten Anteil gelöscht beziehungsweise geladen). Es gilt \(U = \sum_i u_i\) und \(L = \sum_i l_i\).
- Spielregel: Ein Stapel muss vollständig gelöscht sein, bevor in ihn geladen wird. Ein Kranspiel ist ein Einzelspiel (löschen oder laden) oder ein Doppelspiel (aus einem Stapel löschen und in einen anderen, schon leeren Stapel laden).
- Zeit: Ein Doppelspiel kostet \(r\) Einzelspiele (Annahme \(r\) = 1,4, Regler 1,0 bis 1,9); ein Einzelspiel dauert 2 Minuten (30 Spiele je Stunde, wie in der Kran-Demo).
- Verfahren: Ohne Doppelspiel (erst alles löschen, dann alles laden), Bay-Reihenfolge (Stapel von links nach rechts leeren), kurze Entladung zuerst (aufsteigend nach der Löschzahl) und Johnson. Referenz aller Vergleiche ist „Ohne Doppelspiel“.
Doppelspiele einer Reihenfolge
Eine Reihenfolge \(\sigma\) der Stapel bestimmt, in welcher Folge sie ganz geleert werden. Mit \(A_0 = 0\) (verfügbare Ladungen) und für \(k = 1, \dots, S\) gilt:
\[d_k = \min\big(A_{k-1},\, u_{\sigma(k)}\big), \qquad A_k = A_{k-1} + l_{\sigma(k)} - d_k\]
Das Löschen aus Stapel \(\sigma(k)\) paart sich mit höchstens so vielen Ladungen, wie in schon geleerte Stapel gehören (\(A_{k-1}\) zählt nur Ladungen der Stapel \(\sigma(1), \dots, \sigma(k-1)\)). \(D(\sigma) = \sum_k d_k\) ist die Zahl der Doppelspiele.
Spiele und Zeit
Aus den Doppelspielen folgen Spielzahl \(Z\) und Kranzeit \(T\) (in Einzelspielen):
\[Z(\sigma) = U + L - D(\sigma), \qquad T(\sigma) = U + L - (2 - r)\, D(\sigma), \qquad 1 \le r < 2\]
Jedes Doppelspiel spart gegenüber zwei Einzelspielen \(2 - r\) Einzelspiele. Beide Größen werden von derselben Reihenfolge minimiert, denn \(T\) fällt mit \(D\) für jedes \(r < 2\). Die beste Reihenfolge hängt deshalb nicht von \(r\) ab, nur die Minuten ändern sich.
Johnson-Regel und untere Schranke
\(Z(\sigma)\) ist die Laufzeit eines Flow-Shops mit zwei Stufen (Löschen, Laden) und den Aufträgen \((u_i, l_i)\). Optimal ist nach Johnson: zuerst die Stapel mit \(u_i \le l_i\) aufsteigend nach \(u_i\), dann die mit \(u_i > l_i\) absteigend nach \(l_i\). Weil jedes Spiel höchstens einen Container löscht und einen lädt, gilt \(D \le \min(U, L)\), also \(Z \ge \max(U, L)\) und für die Zeit:
\[T \ge U + L - (2 - r)\min(U, L)\]
Die App gibt bei bis zu 7 Stapeln eine Gegenprobe, die alle Reihenfolgen durchprobiert und Johnson bestätigt. Die Tests vergleichen Johnson zusätzlich mit einer unabhängigen Zustandssuche über alle Spielfolgen, also auch mit teilweisem Löschen mehrerer Stapel.
Befunde
Alle Zahlen stammen aus den Messungen der Demo und gelten für das Standardszenario: 10 Stapel, 6 Lagen, Entladeanteil 50 %, \(r\) = 1,4. Sie stammen laut README aus der Preset-Abstimmung und der Vorab-Messreihe. Die Kranzeit wird gegenüber „Ohne Doppelspiel“ verglichen; wo der Beladeanteil oder die Bay-Größe abweicht, ist das genannt.
| Frage | Befund |
|---|---|
| Stimmt Johnson? | Johnson liefert das beste Ergebnis über alle 720 Reihenfolgen in 300 von 300 Kleinstbays (6 Stapel). Er ist außerdem gleich dem echten Optimum des Kranmodells (Zustandssuche über alle Spielfolgen) in 60 von 60 Bays mit 4 Stapeln. |
| Was bringt das Doppelspiel? | Kranzeit gespart (Bay-Reihenfolge / kurze Entladung / Johnson): bei 20 % Beladung 14,9 / 15,2 / 16,7 %, bei 50 % 23,7 / 25,4 / 26,7 %, bei 80 % 20,7 / 22,2 / 22,2 %. Am größten, wenn Laden und Löschen ausgewogen sind. |
| Wie viel macht die Reihenfolge aus? | Bei 50 % Beladung: 59,4 Spiele ohne Doppelspiel, 35,9 in Bay-Reihenfolge, 34,2 mit kurzer Entladung, 32,9 mit Johnson. Johnson braucht in 92 % der Bays weniger Spiele als die Bay-Reihenfolge. „Größte Entladung zuerst“ ist schlechter als die Bay-Reihenfolge. |
| Reicht die Faustregel? | Bei viel Beladung (80 %): ja, „kurze Entladung zuerst“ ist gleich Johnson in 200 von 200 Bays. Bei wenig Beladung (20 %) liegt Johnson in 140 von 200 Bays vorn. |
| Erreicht man die untere Schranke? | Bei wenig Beladung fast immer (94 % der Bays), bei ausgewogener Beladung in 18 %, bei 20 × 8 Stapeln in 6 %. Dort ist die Schranke nicht erreichbar, Johnson bleibt das Beste. |
Grenzen
- Vereinfachtes Literaturmodell (Goodchild und Daganzo 2006): Stapel als Aufträge, ein Stapel wird erst ganz geleert, dann beladen.
- Fehlende Teile: keine Fahrzeiten zwischen Stapeln, keine Lukendeckel und keine Trennung von Deck und Unterdeck, keine Stabilität beim Laden; alle Spiele gleich lang.
- Annahme \(r\) = 1,4: Das Verhältnis von Doppel- zu Einzelspiel ist angenommen; die beste Reihenfolge ist für jedes Verhältnis unter 2 dieselbe, nur die Minuten ändern sich.
- Faustregel und Daten: „Kurze Entladung zuerst“ ist eine Wahl des Autors als Faustregel; die Löschzahlen und Ladezahlen sind zufällig gezogen, nicht aus einem echten Stauplan.
- Größenordnungen: Alle Zahlen stammen aus einer Simulation, nicht aus einer Messung an echten Kranspielen.
Quellen
- Johnson (1954): Reihenfolge der Aufträge im Flow-Shop mit zwei Stufen.
- Goodchild und Daganzo (2006): Übertragung auf das Doppelspiel am Kran.
- Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/doppelspiel-demo.
Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo.