Auftragsvergabe per Gebot verständlich erklärt

Ein Hafen schreibt jeden Auftrag aus, die Kräne nennen, wann sie damit fertig wären, und der Schnellste bekommt den Zuschlag. Niemand plant den ganzen Tag im Voraus. Das hat einen Preis: Weil jeder Zuschlag endgültig ist, kann es länger dauern, bis alle Aufträge erledigt sind, als bei einem Plan, der alle Aufträge von Anfang an kennt. Die Seite erklärt das erst ohne Formeln, dann für Fachleute mit Formel, Befunden und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

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

Zwei Kräne und eine Ausschreibung

Stellen Sie sich einen Hafen vor. Zwei Kräne, Nord und Süd, holen Container von Stellplätzen entlang der Kaimauer. Die Aufträge treffen nacheinander ein und dauern unterschiedlich lang. Eine zentrale Stelle, die alle Aufträge im Voraus kennt und den Tag durchplant, gibt es nicht.

Stattdessen werden die Aufträge der Reihe nach ausgeschrieben, ähnlich wie bei einer Auktion, nur dass der niedrigste Wert gewinnt. Fachleute nennen das Contract Net Protocol. Jeder Auftrag durchläuft drei Schritte:

• Ankündigen: Ein Ausschreiber, eine Stelle, die nur den nächsten Auftrag bekannt gibt, nennt dessen Dauer.
• Bieten: Jeder Kran rechnet allein: Wann wäre ich fertig, wenn ich diesen Auftrag ans Ende meiner Liste hänge? Diese Zeit ist sein Gebot.
• Zuschlagen: Das niedrigste Gebot gewinnt, danach kommt der nächste Auftrag.

Ein Bild mit erfundenen Zeiten, Fahrzeiten lassen wir weg: Drei Aufträge treffen nacheinander ein, zuerst einer von einer Stunde, dann wieder einer von einer Stunde, zuletzt einer von vier Stunden. Beim ersten bieten beide Kräne eine Stunde, bei Gleichstand bekommt Nord den Zuschlag. Beim zweiten bietet Nord zwei Stunden, Süd eine, also gewinnt Süd. Beim dritten bieten beide fünf Stunden, und Nord bekommt ihn. Nach fünf Stunden ist alles erledigt.

Der Haken: Der Zuschlag gilt für immer

Im Bild wäre es besser gewesen, den langen Auftrag allein Nord zu geben und die beiden kurzen Süd. Dann wäre nach vier Stunden alles erledigt, eine Stunde früher. Das konnte beim ersten Zuschlag niemand wissen, und ein vergebener Auftrag wird nie zurückgenommen.

Ein Plan, der alle Aufträge von Anfang an kennt, hätte es gesehen. Die Demo, ein Programm zum Ausprobieren im Browser, rechnet einen solchen zentralen Plan zum Vergleich und zeigt die beste Lösung, die das Rechenprogramm innerhalb seiner Zeitgrenze findet. Sie ist das beste mögliche Ergebnis, wenn es das belegen kann. Verglichen wird die Fertigstellungszeit, also die Zeit, bis der letzte Kran seinen letzten Auftrag beendet hat. Wie groß der Abstand wird, hängt vom Beispiel ab; die Zahlen aus der Demo stehen weiter unten.

Was hilft, und woran Sie es im Betrieb erkennen

Die Schwäche hängt an zwei Eigenschaften: Spätere Aufträge sind beim Vergeben unbekannt, und ein Zuschlag lässt sich nicht zurücknehmen. Hilfreich kann sein, eine davon zu lockern; ob und wie viel das bringt, zeigt die Demo nicht.

Ein Bild aus dem Betrieb, nicht aus der Demo: Ein Disponent teilt jede eingehende Fahrt sofort dem Fahrer zu, der am frühesten fertig wäre, und ändert danach nichts mehr. Erkennbar ist das daran, dass Zuteilungen nie getauscht werden. Fragen Sie Ihren Planer zweierlei: Wird umverteilt, wenn später ein langer oder ungünstig gelegener Auftrag eintrifft? Können Aufträge getauscht oder gebündelt angeboten werden? Solange die Aufträge nacheinander eintreffen und vorher nicht bekannt sind, kann ein Plan mit Vorwissen schneller fertig sein. Wie viel, zeigt nur Ihr eigener Fall.

Wie ernst ist das Modell zu nehmen?

Die Demo ist stark vereinfacht: Die Kräne behindern sich nicht, und Orte und Dauern sind zufällig erzeugt, nicht in einem Hafen gemessen. Sie zeigt, wie der Mechanismus wirkt, nicht wie viel Zeit ein bestimmter Hafen verliert.

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.

• Modell: Aufträge \(j = 1, \dots, n\) mit Position \(q_j\) und Dauer \(d_j\) werden streng nacheinander in Ankunftsreihenfolge angekündigt; der Manager (im Einsteigerteil: Ausschreiber) kennt künftige Aufträge nicht. Jeder Agent (Kran) hat eine Position \(p_a\) und eine freie Zeit \(f_a\). Es gibt keine gemeinsame Schiene und keine Non-Crossing-Regel; die Kräne behindern sich nicht.
• Gebot: Jeder Agent bietet rein lokal die Zeit, zu der er fertig wäre, wenn er den Auftrag ans Ende seiner eigenen Warteschlange hängt (Cheapest Insertion am Ende, kein Umsortieren). Das niedrigste Gebot erhält den Zuschlag; ein Gleichstand geht an den Agenten mit der niedrigsten Nummer (Quelltext cn_bidding.py).
• Instanzen: Positionen und Grunddauern werden zufällig erzeugt. Mit einer von der Streuung der Auftragsdauer abhängigen Wahrscheinlichkeit wird ein Auftrag um einen festen Faktor verlängert („Spitzen-Auftrag“); die Startpositionen der Kräne liegen gleichmäßig verteilt (Werte in cn_constants.py, nicht in der README). Regler der App: Zahl der Aufträge, Zahl der Agenten, Streuung der Auftragsdauer, Anfahrtszeit pro Positionseinheit, Zufalls-Seed.
• Zielgröße: der Makespan \(\max_a f_a\), also der Zeitpunkt, zu dem der letzte Kran fertig ist.

Die Formeln

Das Gebot von Agent \(a\) für Auftrag \(j\) ist die eigene freie Zeit plus Anfahrtszeit plus Dauer des Auftrags; \(\tau\) ist die Anfahrtszeit pro Positionseinheit:

\[\text{Gebot}(a, j) = f_a + \underbrace{|p_a - q_j| \cdot \tau}_{\text{Anfahrtszeit}} + d_j\]

Der Zuschlag geht an \(\arg\min_a \text{Gebot}(a, j)\); danach gilt für den Gewinner \(p_a \gets q_j\) und \(f_a \gets \text{Gebot}(a, j)\). Die Zuteilung ist strukturell unumkehrbar: Das Protokoll verarbeitet die Aufträge nacheinander, über \(j+1, \dots, n\) ist bei der Vergabe von \(j\) nichts bekannt, und es gibt keinen Mechanismus, eine getroffene Zuteilung zu revidieren. Es minimiert damit nicht den Makespan \(\max_a f_a\) über alle Aufträge gemeinsam, sondern trifft \(n\) unabhängige, myopische Einzelentscheidungen.

Als zentrale Referenz löst OR-Tools CP-SAT dasselbe Problem mit vollständiger Information: Zuweisung \(x_{j,a} \in \{0,1\}\), Start- und Endzeiten je Auftrag, Sequencing einschließlich Anfahrtszeit zwischen Aufträgen desselben Agenten. Ein lexikografisches Tie-Breaking Minimize(makespan · W + Σ Ende) verhindert willkürlichen Leerlauf unter gleich-optimalen Lösungen.

Contract Net ist ein Online-Algorithmus \(\text{ALG}\), CP-SAT liefert die Offline-Lösung \(\text{OPT}\) mit vollständiger Information (die beste gefundene Lösung, nach der Messreihe der README bis 0,26 % über dem wahren Optimum). Die kompetitive Analyse (Sleator und Tarjan) definiert den kompetitiven Faktor als \(\text{ALG}/\text{OPT}\); nach Standardwissen, nicht aus README oder App, ist das das Supremum dieses Quotienten über alle Eingaben. Die in der App gezeigte Lücke ist \((\text{ALG} - \text{OPT})/\text{OPT}\), also derselbe Quotient minus eins, hier empirisch für eine konkrete Instanz und nicht als bewiesene Schranke über alle Eingaben.

Befunde

Alle Zahlen stammen aus der README der Demo. Es sind einzelne Messungen aus Kalibrierung und Verifikation, keine Messreihe über die Regler; Mittelwerte oder Streuungen der Lücke nennt die README nicht. Die Voraussetzungen stehen jeweils in der Zeile.

Frage	Befund
Wie groß kann die Lücke zum zentralen Optimum ohne Spitzen-Aufträge werden?	Ein Kalibrierungs-Sweep über 20 Zufalls-Seeds bei duration_variability=0 ergab eine Lücke zwischen 0,0 % und 76,0 %. Die Positions- und Reihenfolge-Struktur allein treibt die Lücke also schon erheblich. Die übrigen Einstellungen des Sweeps nennt die README nicht; das Kalibrierungsskript liegt nicht im Repo, und ob nach der Rasterkorrektur neu gemessen wurde, geht aus der README nicht hervor.
Kann Contract Net das zentrale Optimum schlagen?	In den geprüften Instanzen nie: Contract Net schlägt das CP-SAT-Ergebnis nicht. Gegen eine unabhängige exakte Teilmengen-DP liegt CP-SAT höchstens 0,26 % über dem Optimum (201 + 320 Instanzen). Wegen dieser Abweichung folgt „nie“ nicht zwingend für den ganzen Reglerbereich. Nur außerhalb des Reglerbereichs (n ≤ 2 Aufträge) ist der Zeithorizont des Modells zu knapp.
Warum wird der CP-SAT-Zeitplan nachgerechnet?	CP-SAT rechnet auf einem aufgerundeten 0,1-Minuten-Raster. Der Rasterwert lag vorher bis über 1 % zu hoch und zeigte bei 13 von 120 Zufallsinstanzen im Reglerbereich ein „Contract Net schlägt das Optimum“; die ursprüngliche Messung von -0,8 % war ein Rundungsartefakt. Gemeldet wird deshalb der exakt nachgerechnete Zeitplan.
Kann Contract Net schon mit einem Agenten verlieren?	Bei einer getesteten Instanz ja: Im Ein-Agenten-Fall bearbeitet das Protokoll die Aufträge in reiner Ankunftsreihenfolge, und ein Test findet eine Instanz, in der CP-SAT besser ist (test_single_agent_cnp_can_lose_to_cp_sat_on_ordering_alone). Der Verlust kommt dort allein aus der festen Reihenfolge. Die App erlaubt mindestens zwei Kräne, der Fall ist also nur im Test, nicht im Regler zu sehen.
Wie wurden die Beispiele (Presets) gewählt?	Nach tatsächlich gemessenen Ergebnissen für bestimmte Zufalls-Seeds kalibriert; ein Test hält die Lücken-Bänder der vier Presets als Regression fest. Es sind gewählte Beispiele, keine Stichprobe.

Der Befund zur Lücke ohne Spitzen-Aufträge war nicht vorab angenommen: Die ursprüngliche Erwartung lautete, dass duration_variability=0 durchgehend eine kleine Lücke zeigt und erst höhere Werte sie sichtbar machen.

Grenzen

• Online gegen Offline: Contract Net und CP-SAT lösen nicht dasselbe Problem (Online ohne Kenntnis künftiger Aufträge, Offline mit vollständiger Information). Der Vergleich ist ein Maßstab der kompetitiven Analyse, die Lücke aber eine Stichprobe für eine Instanz und keine Worst-Case-Schranke.
• Bewusst vereinfachtes Vehikel: keine gemeinsame Schiene und keine Non-Crossing-Regel, damit der Koordinationsmechanismus im Vordergrund steht und nicht die physische Kran-Choreographie. Die Instanzen sind zufällig erzeugt, keine Daten eines Terminals.
• Einfachste Gebotsformel: eine Biet-Runde je Auftrag, ein Gebot je Agent, Anhängen am Listenende ohne Umsortieren. Nachverhandlung, Gegengebote, Kommunikationskosten oder Ausfälle von Agenten sind nicht modelliert.
• Referenzlöser: CP-SAT rechnet auf einem aufgerundeten Raster und mit hartem Zeitlimit. Wird es erreicht, zeigt die App die beste gefundene Lösung ohne Optimalitätsbeweis; liefert es nichts, zeigt sie kein Ergebnis.
• Presets: Sie sind für bestimmte Zufalls-Seeds kalibriert und zeigen die Schwäche deshalb bewusst deutlich. Aus ihnen lässt sich keine typische Größe der Lücke ablesen.
• Nicht enthalten: Die App nennt als Fortsetzungen, die die Schwäche jeweils über einen anderen Mechanismus angehen, Kombinatorische Auktionen (Bündel-Gebote), Distributed Constraint Optimization (formaler Nachrichtenaustausch) und Multi-Agent Reinforcement Learning (gelernte Langzeit-Politik). Sie sind nicht Teil dieser Demo.

Quellen

• Smith, R. G. (1980): The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers C-29(12), 1104–1113.
• Sleator, D. D., Tarjan, R. E. (1985): Amortized Efficiency of List Update and Paging Rules. Communications of the ACM 28(2), 202–208 (kompetitive Analyse).
• Quelltext, Tests und Referenzlöser der Demo: github.com/sebastian-hanisch/contract-net-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Smith (1980) steht in der README der Demo, Sleator und Tarjan (1985) in der App; die vollständigen Angaben sind aus dem Gedächtnis ergänzt. Die Aussagen zur Gebotsformel, zu Gleichständen und zur Instanzerzeugung stammen aus dem Quelltext der Demo. Die Zahlen 0,26 %, 201 + 320 Instanzen, 13 von 120 und 76,0 % stehen nur in der README (und 76,0 % in cn_constants.py); die zugehörigen Messreihen und das Kalibrierungsskript liegen nicht im Repo, der Test tests/test_oracle_contract_net.py prüft nur eine kleine Fassung.