Containerbrücken-Einsatz verständlich erklärt

Drei Gärtner schneiden eine lange Hecke, und der Weg daneben ist zu schmal zum Überholen. Verteilen sie die Arbeit nach der Faustregel „Das Größte zuerst“, kommen sie einander womöglich in die Quere. Dasselbe gilt für Kräne an einem Containerschiff. Die Seite zeigt, was das kostet und was besser klappt.

Zuletzt aktualisiert: 11. November 2026

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

Drei Gärtner an einer Hecke

Stellen Sie sich eine lange Hecke vor, die in zwölf Abschnitte geteilt ist. Manche Abschnitte sind schnell geschnitten, andere brauchen lange. Drei Gärtner teilen sich die Arbeit. Neben der Hecke führt ein schmaler Weg, auf dem niemand an einem anderen vorbeikommt.

Zwei Regeln kommen dazu. Jeder Abschnitt wird von genau einem Gärtner am Stück geschnitten. Und zwei Gärtner dürfen nur gleichzeitig arbeiten, wenn sie einen Mindestabstand einhalten. Wer zum nächsten Abschnitt geht, verliert Zeit auf dem Weg. Steht ihm ein Kollege im Weg, muss er warten.

Gesucht ist ein Plan, bei dem die Hecke möglichst früh fertig ist. Fertig ist sie erst, wenn der Letzte aufhört.

Genauso läuft es an einem Containerschiff. Es liegt am Kai und ist längs in Abschnitte geteilt, Fachleute sagen Bays dazu. In manchen Abschnitten sind wenige Container zu bewegen, in anderen viele. Die Gärtner sind große Kräne, die auf einer gemeinsamen Schiene am Kai fahren, die Containerbrücken. Sie können einander nicht überholen und müssen Abstand halten, solange beide arbeiten. Gesucht ist, welcher Kran welche Abschnitte übernimmt, damit das Schiff möglichst kurz am Kai liegt. Diese Zeit heißt Liegezeit.

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Ganz unten gibt es zwei Knöpfe: Der erste öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht. Alles hier ist ein vereinfachtes Rechenbild.

Die kluge Regel, die verliert

Die bekannte Faustregel heißt: das Größte zuerst. Der größte Abschnitt geht an den Gärtner, der als Erster Zeit hat. Wenn Arbeiter einander nicht stören, gilt das als bewährt. Es ist wie beim Kofferpacken: erst die großen Stücke, dann füllen die kleinen die Lücken, bis alle Koffer gleich voll sind.

An der Hecke geht sie schief. Die größten Abschnitte liegen verstreut, und jeder Gärtner bekommt Stücke von hier und von dort. Soll der linke Gärtner einen Abschnitt rechts von dem des rechten schneiden, müssten die beiden aneinander vorbei. Sie können dann nicht gleichzeitig arbeiten, und die Zeit, die zwei Gärtner sparen sollten, geht verloren.

Die Demo zeigt das in einem Rechenversuch mit 240 zufälligen Schiffen. Sie haben acht bis sechzehn Abschnitte, zwei bis vier Kräne und einen Mindestabstand von einem Abschnitt. Bei 220 davon fand die Demo für die Verteilung nach der Faustregel keinen Zeitplan, der alle Regeln einhält. Bei einem Mindestabstand von zwei Abschnitten waren es sogar 234. Zum Vergleich diente die einfachste Aufteilung: Jeder Kran bekommt gleich viele benachbarte Abschnitte, ohne auf die Arbeit zu schauen. Sie scheiterte bei einem Abschnitt Abstand in diesem Versuch kein einziges Mal.

Bei 20 Schiffen fanden beide Verfahren einen Plan. Dort war die Faustregel in 12 Fällen länger und in 8 kürzer. Ihre Liegezeit lag im Mittel gut vier Prozent über der einfachen Aufteilung. Ihre Kräne mussten im Mittel warten, die der einfachen Aufteilung nicht. In diesem Versuch verliert die kluge Regel also gegen die einfachste.

Was besser klappt: Schnitte nach Arbeit

Auch die einfachste Aufteilung besteht aus drei zusammenhängenden Stücken, und das hilft schon. Jeder Gärtner bekommt ein Stück für sich. Zwei Gärtner stehen nur an der Grenze nebeneinander und kommen einander sonst nicht in die Quere. Laut Messung der Demo bleibt die Wartezeit bei solchen Aufteilungen meist bei null. Besser wird es, wenn die Schnitte klug gesetzt werden.

Wo wird geschnitten? Nicht so, dass jeder gleich viele Abschnitte hat, sondern so, dass jeder möglichst ähnlich viel Arbeit hat. Gleich viele Abschnitte sind nicht gleich viel Arbeit, denn ein Abschnitt kann viel länger dauern als sein Nachbar. Das Schiff ist erst fertig, wenn der Kran mit der größten Last fertig ist. Ein Rechenverfahren findet darum die Schnitte, bei denen das größte Stück so klein wie möglich ist.

Im Mittel über die 240 Schiffe war das Schiff so gut dreieinhalb Prozent früher fertig als mit der einfachsten Aufteilung. Es hilft aber nicht überall. Bei drei der vier Beispielschiffe, die die Demo fertig eingerichtet anbietet, kam dieselbe Zeit heraus. Der Grund: Dort hatte schon die einfachste Aufteilung die kleinstmögliche größte Last, und Schnitte nach Arbeit konnten daran nichts verbessern.

Wer mehr herausholen will, nimmt eine gute Aufteilung als Start und probiert kleine Änderungen. Zwei Abschnitte tauschen den Kran, oder ein Abschnitt wechselt zu einem anderen Kran. Behalten wird nur, was die Liegezeit verkürzt. So wird das Ergebnis nie schlechter als der Start, denn schlechtere Änderungen werden verworfen. Im Mittel kamen gut sieben Prozent weniger Liegezeit heraus als bei der einfachsten Aufteilung.

Wie nah ist das am Besten?

Ein Rechenprogramm kann nach dem besten Plan suchen und bei genug Zeit beweisen, dass es keinen besseren gibt. Fachleute nennen es exakten Löser. Die Verfahren davor liefern gute, aber nicht bewiesen beste Pläne und heißen Näherungsverfahren. Für drei der vier Beispielschiffe liegt ein Ergebnis des exakten Lösers vor. Der Plan des besten Näherungsverfahrens war dort höchstens eine Minute länger, bei Liegezeiten von gut anderthalb Stunden.

Warum nicht immer der Beweis? Er braucht Zeit, denn mit jedem weiteren Abschnitt kommen viele neue Zuordnungen und Reihenfolgen hinzu. Bei acht Abschnitten dauerte es in der Messung im Median weniger als eine Sekunde. Bei sechzehn Abschnitten gelang in zwölf Sekunden kein Beweis. Beim großen Beispielschiff mit fünf Kränen fand der Rechner in allen drei Versuchen mit zwölf Sekunden Zeit nicht einmal einen Plan.

Häufige Missverständnisse

• „Mehr Kräne bedeuten immer ein früheres Ende.“ Jeder Kran braucht Platz auf der Schiene. In der Demo stehen die Kräne zu Beginn gleichmäßig verteilt. Bei vielen Kränen auf einem kurzen Schiff und großem Mindestabstand sind zwei Kräne schon vor dem ersten Handgriff zu nah beieinander. Die Demo meldet dann, dass es keinen gültigen Plan gibt.
• „Wer nie wartet, ist am schnellsten.“ Wartezeit heißt, dass ein Kran stehen muss, weil ein Nachbar im Weg ist. In einem Extremfall der Demo, mit fünf Kränen und dem größten Mindestabstand, wartete die einfachste Aufteilung weniger als die Aufteilung nach Arbeit und brauchte trotzdem länger. Einige ihrer Kräne hatten mehr zu tun als andere, und das Schiff ist erst fertig, wenn der am stärksten beladene Kran fertig ist.

Woran Sie das im Alltag erkennen

• In der Küche arbeiten zwei Personen an einer schmalen Arbeitsfläche. Eine dritte Person hilft dort nicht automatisch, weil auch sie Platz braucht.
• Beim Umzug holen Helfer Kartons aus wechselnden Zimmern und stehen im engen Flur einander im Weg, weil dort niemand vorbeikommt.

Wie ernst ist das Rechenbild zu nehmen?

Die Schiffe sind zufällig erzeugt, alle Kräne sind gleich schnell, und jeder Abschnitt wird von einem Kran am Stück erledigt. Das Rechenbild zeigt, wie sich die Verfahren zueinander verhalten, nicht, wie ein echter Hafen arbeitet.

Was Sie mitnehmen

• Fragen Sie bei jeder Arbeitsteilung auch, wo die Arbeit liegt und wer wem im Weg steht.
• Prüfen Sie eine bewährte Faustregel an dem, was in Ihrem Fall dazukommt. Bei den Kränen war es die enge Schiene.
• Ein Ergebnis ist erst dann das beste, wenn jemand es bewiesen hat. Davor ist es nur gut.

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. Betrachtet wird das Quay Crane Scheduling Problem (QCSP) mit Nichtüberholen, ein klassisches Planungsproblem der Containerterminals (Kim und Park, European Journal of Operational Research, 2004; Übersichtsartikel von Bierwirth und Meisel, 2010/2015). Die Demo modelliert nur einen Ausschnitt, ohne Reihenfolgebeziehungen zwischen Bays. Alle Messungen laufen auf zufällig erzeugten Schiffen; echte Daten fließen nicht ein.

• Schiff: \(n\) Bays \(i = 0, \dots, n-1\); der Bay-Index ist zugleich die Position entlang der Schiffsseite (Bay 0 liegt am weitesten links). Die Bearbeitungsdauer \(d_i\) ist Moves mal Zeit je Move und hängt nicht vom Kran ab. Die Moves je Bay werden zufällig um einen Mittelwert gestreut (Voreinstellung 14 Moves ± 40 %, 2,0 min je Move). Die Größen reichen bis 24 Bays.
• Kräne: \(k\) Kräne \(c = 0, \dots, k-1\) auf einer gemeinsamen Schiene, bis 5 Kräne, in fester Reihenfolge (Kran 0 ist immer der linkeste). Jeder Kran hat eine feste Startposition \(p_c\), gleichmäßig über das Schiff verteilt: \(p_c = (c + \tfrac12)\,n/k\). Ein Kran braucht \(\tau\) Minuten je Bay Abstand (Voreinstellung 0,5 min). Der Sicherheitsabstand \(s\) wird in Bays gemessen und lässt sich bis 3 einstellen; die meisten Messungen unten laufen mit \(s = 1\).
• Plan: Jede Bay wird von genau einem Kran in einem Stück bearbeitet, im Intervall \([t_i,\, t_i + d_i]\). Ein Kran bearbeitet eine Bay zur Zeit. Wechselt er von Bay \(i\) zu Bay \(j\), vergeht mindestens \(\tau\,|i-j|\) Minuten Fahrzeit; die Reihenfolge je Kran ist frei.
• Nichtüberholen: Zwei verschiedene Kräne \(c < c'\) bearbeiten die Bays \(i\) und \(j\). Hat der linke Kran die linkere Bay (\(i < j\), konsistente Zuordnung), muss bei zeitlicher Überlappung \(i + s \le j\) gelten (der Abstand ist die Differenz der Bay-Indizes: bei \(s = 1\) dürfen Kräne an benachbarten Bays gleichzeitig arbeiten). Hat der linke Kran die rechtere Bay (gekreuzte Zuordnung), ist jede zeitliche Überlappung verboten, unabhängig von \(s\), weil Kräne sich nicht überholen können. Dasselbe wird für Fahrten und Wartephasen geprüft. Beim exakten Löser und bei der Prüfung fertiger Pläne ohne gespeicherte Abfahrt gilt: Ein Kran wartet an seiner Position und fährt im letztmöglichen Moment los; die Heuristiken speichern ihre gewählte, frühestmögliche sichere Abfahrt.
• Ziel und Kennzahlen: Minimiert wird die Liegezeit (Makespan) \(\max_i (t_i + d_i)\). Weitere Kennzahlen: die Wartezeit durch Interferenz (die Zeit über die reine Fahrt hinaus, die ein Kran warten muss, weil ein Nachbar im Weg ist, summiert über alle Kräne), die gesamte Fahrzeit und das Lastungleichgewicht (größte minus kleinste Summe der Dauern \(d_i\) der Bays eines Krans).

Die Verfahren

• Gleichmäßige Aufteilung (Referenz): Jeder Kran bekommt gleich viele zusammenhängende Bays (bei Rest die ersten Kräne eine mehr), unabhängig von der Arbeitslast.
• Listenscheduling nach Dauer (LPT, Longest Processing Time first): Die Bays werden nach absteigender Dauer vergeben, jede an den Kran mit der frühesten geschätzten Fertigstellung (nur Fahrzeit, ohne Rücksicht auf Interferenz). Für parallele Maschinen ohne gegenseitige Behinderung ist das eine bewährte Heuristik mit einer Gütegarantie von etwa \(4/3 - 1/(3m)\) bei \(m\) identischen Maschinen, gemessen an der Fertigstellung der letzten Aufgabe. Eine räumliche Variante vergibt die Bays in Schiffsreihenfolge, wählt den Kran aber ebenfalls adaptiv.
• Zonenbalance: Das Schiff wird in \(k\) zusammenhängende, nichtleere Zonen geschnitten, sodass die größte Zonenlast minimal ist (dynamische Programmierung, \(O(n^2 k)\)); jede Zone gehört einem Kran. Das setzt \(n \ge k\) voraus.
• Greedy + lokale Suche: Start ist die beste von drei Konstruktionen (Zonenbalance, LPT, räumliches Listenscheduling), bewertet an der Liegezeit des zugehörigen Zeitplans. Dann folgt ein Hill-Climbing mit zwei Zugtypen: Tausch der Kräne zweier Bays und Verlagerung einer Bay auf einen anderen Kran. Angenommen wird nur eine echte Verkürzung der Liegezeit; das Zugbudget ist 400. Das Ergebnis ist nie länger als der Start.
• Zeitplan aus einer Zuordnung: Aus einer Zuordnung mit fester Reihenfolge je Kran baut die Demo den Zeitplan Aufgabe für Aufgabe (die Einfügereihenfolge der Zuordnungsliste legt je Kran die Bearbeitungsreihenfolge fest, bei LPT absteigend nach Dauer) und prüft jede Platzierung gegen die bereits eingeplanten Bewegungen der anderen Kräne. Findet sie keinen zulässigen Zeitpunkt, wird die Zuordnung abgelehnt; die Demo weicht dann auf die Zonenbalance, die gleichmäßige Aufteilung oder zuletzt den exakten Löser aus.
• Exakter Löser: CP-SAT aus Google OR-Tools mit Variablen \(x_{ic} \in \{0, 1\}\) (Kran \(c\) bearbeitet Bay \(i\)) und ganzzahligen Startzeiten \(t_i \ge 0\). Gerechnet wird im Raster von 0,1 min, Zeiten werden aufgerundet. Das Zeitlimit ist 12 s; ein Ergebnis ohne Optimalitätsbeweis wird als beste gefundene Lösung gekennzeichnet. In der Demo bekommt er das Ergebnis von Greedy + lokale Suche als Startlösung (Hint); die Laufzeittabelle unten wurde ohne Startlösung gemessen. Ein Hint ist nur ein Vorschlag, den der Löser erst als zulässig bestätigen muss.

Die Formeln

Jede Bay gehört genau einem Kran: \(\sum_c x_{ic} = 1\) für jede Bay \(i\). Gehören \(i\) und \(j\) demselben Kran, dürfen sich ihre Intervalle nicht überlappen, und dazwischen liegt die Fahrzeit: \(t_i + d_i + \tau\,|i-j| \le t_j\) oder \(t_j + d_j + \tau\,|i-j| \le t_i\). Die Nichtüberholen-Bedingung steht oben in Worten. Das Ziel ist die Liegezeit mit einem Zusatzziel auf die Summe der Endzeiten:

\[\min \; \Big(\max_i \; (t_i + d_i)\Big) \cdot W \;+\; \sum_i (t_i + d_i)\]

Dabei ist \(W\) ein Gewicht (in der Demo \(n\) mal die Zeitobergrenze des Modells plus 1, also größer als jede mögliche Summe der Endzeiten), das so groß gewählt ist, dass eine Verbesserung der Summe der Endzeiten nie eine Verschlechterung der Liegezeit aufwiegen kann. Der zweite Term drückt jede Aufgabe so früh wie möglich. Ohne ihn kann der Löser unter gleich guten Plänen einen mit unnötigem Leerlauf zurückgeben, und die ausgewiesene Wartezeit schwankt von Lauf zu Lauf. Mit dem Zusatzziel war sie in fünf Läufen mit 30 s Zeitlimit bei dem Fall 12 Bays, 3 Kräne, Abstand 1 immer null bei derselben, bewiesen optimalen Liegezeit von 106,0 min. Daraus folgt nicht, dass das Zusatzziel Wartezeit allgemein verschwinden lässt.

Warum die größte Last zählt

Dieser Abschnitt ist eine Rechnung dieser Seite, keine Messung der Demo. Er erklärt, worauf die Zonenbalance schaut und was daraus nicht folgt.

• Schritt 1, untere Schranke: Ein Kran bearbeitet seine Bays nacheinander. Hat Kran \(c\) die Bays \(B_c\), ist seine Last \(L_c = \sum_{i \in B_c} d_i\), und die Liegezeit ist mindestens \(\max_c L_c\); Fahrt und Warten kommen nur hinzu. Weil sich die Lasten zur Gesamtarbeit addieren, ist die Liegezeit außerdem mindestens \(\tfrac{1}{k} \sum_i d_i\).
• Schritt 2, was die Zonenbalance minimiert: Mit den Teilsummen \(P_i = \sum_{l < i} d_l\) und \(D_c(i)\) als kleinster erreichbarer größter Zonenlast für die ersten \(i\) Bays bei \(c\) Zonen gilt \(D_c(i) = \min_{j < i} \max\bigl(D_{c-1}(j),\, P_i - P_j\bigr)\) mit \(D_0(0) = 0\). So wird unter allen Zerlegungen in \(k\) zusammenhängende, nichtleere Zonen die mit der kleinsten größten Last gefunden. Fahrzeit und Abstand kommen in dieser Größe nicht vor.
• Schritt 3, ein Beispiel von Hand: Fünf Bays mit den Dauern 4, 1, 1, 1 und 1 min und zwei Kräne, Fahrt und Abstand außer Acht gelassen. Die gleichmäßige Aufteilung gibt dem ersten Kran drei Bays, dem zweiten zwei: Lasten 6 und 2, die Liegezeit ist mindestens 6 min. Die Zonenbalance schneidet nach der ersten Bay: Lasten 4 und 4, gleich der Schranke aus Schritt 1 (Summe 8 geteilt durch 2).
• Schritt 4, was daraus nicht folgt: Die Zonenbalance minimiert die größte Last, nicht die Liegezeit. Mit Fahrt, Abstand und Wartezeit kann eine lastgleiche Aufteilung länger dauern als eine ungleichere. Beide Aufteilungen können zusammenfallen, wenn schon die gleichmäßige die kleinste größte Last hat. Nachgerechnet mit dem Code der Demo auf denselben Schiffen wie in den Befunden: Beide waren auf denselben 240 Schiffen in gut der Hälfte der Fälle gleich lang, die Zonenbalance in den meisten übrigen kürzer, in sechs Fällen länger.

Warum das Listenscheduling nach Dauer scheitert

LPT wählt den Kran nur nach geschätzter Fertigstellung, ohne die Lage der Bay zu berücksichtigen. Weil der Bay-Index zugleich die Position auf der Schiene ist, verstreut das die Bays eines Krans über das Schiff. Viele Paare sind dann gekreuzt zugeordnet: Der linke Kran hat die rechtere Bay. Für solche Paare ist jede zeitliche Überlappung verboten, ein Teil der Parallelität geht verloren, und bei engem Sicherheitsabstand kann die Zuordnung ganz unplanbar werden. Die Gütegarantie von LPT gilt für Maschinen ohne gegenseitige Behinderung; hier kann die Randbedingung eine Zuordnung unzulässig machen. Das ist die Erklärung der Demo, einzeln belegt ist die Häufigkeit der Ablehnung in den Befunden. Die räumlich sortierte Variante milderte das in der Messung nicht zuverlässig, weil auch sie zwischen Kränen hin- und herspringen kann.

Befunde

Alle Zahlen stammen aus Läufen mit festen Zufallsschiffen; die Voraussetzungen stehen in der Tabelle.

Frage	Befund
Wie oft wird die LPT-Zuordnung abgelehnt? (240 Zufallsschiffe: 8, 10, 12 oder 16 Bays, 2, 3 oder 4 Kräne, je 20 Schiffe, Abstand 1, 14 Moves ± 40 %, 2,0 min je Move, 0,5 min Fahrzeit je Bay)	220 von 240 (92 %); die gleichmäßige Aufteilung nie. Bei Abstand 2: LPT 234 von 240, die gleichmäßige Aufteilung 7.
Wie schneidet LPT ab, wo beide einen Plan haben? (20 Schiffe, Abstand 1)	In 12 länger, in 8 kürzer als die gleichmäßige Aufteilung; im Mittel 4,3 % länger (Mittel der Verhältnisse je Schiff), Wartezeit im Mittel 12,5 min gegen 0,0 min.
Ist die Ablehnung strukturell? (30 abgelehnte LPT-Zuordnungen, Abstand 1, Bays/Kräne: 8/2, 10/3, 12/3, 12/4; der exakte Löser prüfte mit fest vorgegebener Zuordnung)	Bei 13 ist die Zuordnung für jede Zeitplanung unzulässig (der Löser fand mit fest vorgegebener Zuordnung keinen zulässigen Plan und bewies das); bei 17 gibt es einen zulässigen Zeitplan, nur die Konstruktion mit fester Reihenfolge je Kran findet ihn nicht. Über andere Zuordnungen sagt das nichts.
Wie viel kürzer sind Zonenbalance und Greedy + lokale Suche als die gleichmäßige Aufteilung? (dieselben 240 Schiffe, Abstand 1, Zeitplan jeweils zulässig)	Im Mittel 3,6 % bzw. 7,1 % kürzer (Mittel der Verhältnisse je Schiff; als Verhältnis der Summen der Liegezeiten etwas kleiner, Rechnung dieser Seite).
Ein kleines Schiff (8 Bays, 2 Kräne, Abstand 1, 12 Moves ± 30 %)	Gleichmäßige Aufteilung 102,5 min ohne Wartezeit; LPT 105,5 min mit 2,0 min Wartezeit; die räumliche Variante 111,5 min mit 17,5 min Wartezeit.
Rundung im exakten Modell (10 Bays, 3 Kräne, Abstand 1, 14 Moves ± 40 %)	Greedy + lokale Suche 104,8 min, exakt 104,9 min. Das exakte Modell rechnet im Raster von 0,1 min und rundet auf, sein Ergebnis liegt bei diesen Einstellungen höchstens 0,1 min über dem stetigen Optimum; bei anderen Reglerwerten summieren sich die Aufrundungen.
Ist Wartezeit ein Gütemaß? (18 Bays, 5 Kräne, Abstand 3, 12 Moves)	Gleichmäßige Aufteilung 114,4 min bei 4,3 min Wartezeit; Zonenbalance und Greedy + lokale Suche je 99,0 min bei 10,3 min Wartezeit: mehr Wartezeit, kürzere Liegezeit.
Zulässigkeit bei Abstand 3 (6 bis 24 Bays, 1 bis 5 Kräne, je 5 Zufallsschiffe: 475 Kombinationen)	90 sind als Szenario unlösbar, 385 lösbar; für alle 385 meldet die Prüfung bei jedem gelieferten Zeitplan keine Verletzung. Abgelehnte Zuordnungen: gleichmäßige Aufteilung 19, Zonenbalance 17, Greedy + lokale Suche 7 von 385; die Demo weicht dann aus.

Liegezeiten von vier Beispielschiffen in min (nur das exakte Modell rechnet im Raster von 0,1 min, die Zeiten der Heuristiken sind nicht gerastert). Für das dritte Schiff fand der exakte Löser in 12 s keinen Plan; ob beim vierten der Optimalitätsbeweis gelang, ist nicht angegeben.

Schiff	gleichmäßig	Zonenbalance	Greedy + lokale Suche	exakt
8 Bays, 2 Kräne, Abstand 1	102,5	102,5	101,5	101,0
12 Bays, 3 Kräne, Abstand 1	112,5	112,5	107,0	106,0
20 Bays, 5 Kräne, Abstand 1	150,5	150,5	145,0	kein Plan in 12 s
Großer Abstand (Sicherheitsabstand 3)	116,85 (6,3 min Wartezeit)	112,85	110,05	109,2

Laufzeit des exakten Lösers: Median über je drei Zufallsschiffe, Abstand 1, Zeitlimit 12 s, 8 Suchpfade auf einem Windows-Rechner mit 16 Kernen, ohne Startlösung; die Zeiten hängen von der Hardware ab.

Bays	2 Kräne	3 Kräne	4 Kräne
8	0,5 s (3/3 optimal)	0,7 s (3/3 optimal)	0,5 s (3/3 optimal)
12	Zeitlimit (0/3 optimal, Lösung vorhanden)	8,9 s (3/3 optimal)	4,9 s (3/3 optimal)
16	Zeitlimit (0/3 optimal, Lösung vorhanden)	Zeitlimit (0/3 optimal, Lösung vorhanden)	Zeitlimit (0/3 optimal, Lösung vorhanden)
20	Zeitlimit, 0/3 mit Lösung	Zeitlimit, 0/3 mit Lösung	Zeitlimit, 0/3 mit Lösung

Mit der Startlösung von Greedy + lokale Suche lieferte der Löser beim Schiff mit 20 Bays und 5 Kränen in 3 von 3 Läufen innerhalb von 12 s keine Lösung. Konstruktion samt Zeitplan dauerte bei 24 Bays und 5 Kränen im Mittel 0,46 ms (gleichmäßig, Maximum 0,7 ms), 0,64 ms (Zonenbalance, Maximum 1,1 ms) und 114 ms (Greedy + lokale Suche mit 400 Zügen, Maximum 130 ms), jeweils über 10 Zufallsschiffe, Abstand 1, auf demselben Windows-Rechner; die Zeiten hängen von der Hardware ab.

Was die Messung zeigt und wo ihre Grenzen liegen

Das zeigt die Messung:

• Die Zahlen gelten für feste Zufallsschiffe mit den genannten Einstellungen und sind dafür wiederholbar. Für diese Seite wurden die Anteile der Ablehnung bei Abstand 1 und 2, die beiden Mittelwerte der Verkürzung und die Zählungen der Zulässigkeit mit dem Code der Demo nachgerechnet; sie stimmen (Rechnung dieser Seite).
• Auf einigen kleinen Zufallsschiffen (höchstens sechs Bays) stimmt die Liegezeit des exakten Lösers mit einer unabhängigen Suche im Zeitraster überein, und keine der drei Heuristiken unterbietet sie.

Das zeigt sie nicht:

• Modellgrenzen: Zufällige Schiffe, alle Kräne gleich schnell, Dauer je Bay unabhängig vom Kran, Bays unteilbar, keine Reihenfolgebeziehungen zwischen Bays (etwa Stapel oder Ladefolge), keine Ausfälle, ein eindimensionales Gleis. Aussagen zu echten Terminals oder Größen jenseits von 24 Bays und 5 Kränen gibt es nicht.
• Mittelwerte verdecken: Die Verkürzung durch die Zonenbalance kommt aus den Schiffen, in denen sie etwas ändert (siehe die Rechnung oben). Sie ist nicht überall kürzer, denn sie minimiert die größte Last, nicht die Liegezeit.
• Greedy + lokale Suche ist nicht überall besser als die Referenz: Sie ist nie länger als ihr Start, aber die gleichmäßige Aufteilung ist kein Startkandidat. In einem Raster aus Abständen 1 bis 3 mit den Größen 8, 10, 12, 16 Bays und 2, 3, 4 Kränen war sie in acht von sechshundertdreiunddreißig Instanzen länger als die gleichmäßige Aufteilung (je 20 Zufallsschiffe; gezählt nur Instanzen, die als Szenario lösbar sind und in denen gleichmäßige Aufteilung, Zonenbalance und Greedy + lokale Suche einen zulässigen Plan haben, von sechshundertsechzig lösbaren; Rechnung dieser Seite, keine Messung der Demo).
• Wartezeit ist kein Gütemaß allein: Die Aussage, zusammenhängende Zonen vermieden Interferenz fast vollständig, stimmt bei Abstand 1; die Nachrechnung dieser Seite ergab dort im Mittel keine Wartezeit, weder bei der gleichmäßigen Aufteilung noch bei der Zonenbalance. Bei Abstand 3 und 5 Kränen (Tabelle) wartet die Zonenbalance mehr als die gleichmäßige Aufteilung und ist trotzdem kürzer, weil bei der gleichmäßigen Aufteilung die Last ungleicher verteilt ist: Der am stärksten belastete Kran hatte dort ein Sechstel mehr Arbeit als bei der Zonenbalance (Rechnung dieser Seite).
• Der exakte Löser: Rundung auf das Raster von 0,1 min, Zeitlimit, ab 16 Bays in der Messung kein Optimalitätsbeweis. Dass mehr Kräne das Modell bei gleicher Bayzahl leichter machen (12 Bays), beruht auf drei Zufallsschiffen je Zelle und ist keine allgemeine Aussage; eine Erklärung dafür ist nicht geprüft. Dass der Löser beim Schiff mit 20 Bays trotz Startlösung keinen Plan lieferte, zeigt, dass schon die Bestätigung einer Startlösung im Zeitlimit scheitern kann.
• Unlösbare Kombinationen: Die Demo erklärt Kombinationen vorab für unlösbar, bei denen zwei benachbarte Startpositionen enger liegen als der Sicherheitsabstand. Den kleinsten Abstand benachbarter Startpositionen liefert die Formel für \(p_c\): \(n/k\) Bays.

Erweiterungen und Verweise

Nicht modelliert sind unterschiedlich schnelle Kräne, Reihenfolgebeziehungen zwischen Bays, Ausfälle und die Bearbeitung einer Bay durch mehrere Kräne. Dasselbe mathematische Modell, Nichtüberholen auf einer gemeinsamen Bahn, steckt laut Beschreibung der Demo in jeder Aufgabe, bei der sich Ressourcen gegenseitig behindern, etwa bei mehreren Kommissionierern in schmalen Gängen; dort wäre das Gangnetz zweidimensional, und eine Erweiterung in diese Richtung ist offen.

Quellen

• Kim und Park, European Journal of Operational Research, 2004 (Quay Crane Scheduling mit Nichtüberholen); Bierwirth und Meisel, Übersichtsartikel 2010 und 2015.
• Quelltext, Messungen und Tests der Demo: github.com/sebastian-hanisch/quaycrane-demo.
• Löser: CP-SAT aus Google OR-Tools.

Autoren, Zeitschrift und Jahre der Literatur stehen so in der Beschreibung der Demo; Titel und Seiten sind nicht nachgeschlagen. Der Gütefaktor von LPT ist aus dem Gedächtnis ergänzt. Die Rechnungen dieser Seite sind keine Messungen der Demo.