Die M/M/c-Warteschlange verständlich erklärt

Wie viel kürzer wartet ein Lkw, wenn mehrere Spuren eine gemeinsame Schlange teilen, statt dass jede Spur ihre eigene hat? Diese Seite erklärt das zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Die zugehörige Demo ist eine von mehreren zum Thema Warteschlangen und Simulation; sie baut auf der Demo mit nur einer Spur auf.

Zuletzt aktualisiert: 28. Oktober 2026

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

Mehrere Spuren, eine gemeinsame Schlange

Das Gate eines Containerterminals hat hier nicht eine, sondern mehrere gleich schnelle Abfertigungsspuren. Die wartenden Lkw stehen in einer gemeinsamen Schlange und rücken der Reihe nach auf die nächste freie Spur nach. Die Lkw treffen zufällig ein, und jede Abfertigung dauert mal kürzer, mal länger, wie bei einem Gate mit nur einer Spur, das eine andere Demo zum Thema behandelt. Hat das Gate hier nur eine Spur, ist es genau dieser Fall.

Die zugehörige Warteformel heißt Erlang C. Sie gibt unter anderem an, wie wahrscheinlich es ist, dass ein ankommender Lkw warten muss, weil alle Spuren belegt sind. Wichtig ist die Auslastung je Spur: der Anteil der Zeit, in dem eine Spur im Mittel belegt ist.

Was das Zusammenlegen der Schlange bringt

Man kann dieselbe Last auch auf getrennte Schlangen verteilen: Jeder Lkw wird zufällig einer Spur zugeteilt und wartet nur dort. Dann kann ein Lkw hinter einem langsamen stehen, während nebenan eine Spur frei ist. Die gemeinsame Schlange verhindert das. Dieses Zusammenlegen heißt Pooling.

Der Gewinn ist groß und wächst mit der Zahl der Spuren. In den gemessenen Fällen ist der Faktor bei geringerer Auslastung sogar noch größer. Mit nur einer Spur gibt es nichts zusammenzulegen. Bei diesem Vergleich bleibt die Gesamtkapazität gleich: Es ändert sich nur, wie die Lkw sich auf die Spuren verteilen.

Wie viele Spuren braucht ein Gate?

Ein großes Gate darf bei gleichem Service heißer gefahren werden als ein kleines: Es verträgt eine höhere Auslastung je Spur, bevor die mittlere Wartezeit ein vorgegebenes Ziel überschreitet. Große Gates brauchen nur wenige Spuren mehr als das Angebot, also als die Zahl der Spuren, die im Mittel gleichzeitig mit Abfertigen beschäftigt sind.

Eine feste Höchstauslastung als Faustregel trifft das nicht. Für kleine Gates ist sie zu knapp, das Wartezeit-Ziel wird dann verfehlt. Für große Gates ist sie zu großzügig und verlangt mehr Spuren als nötig. Der Spurbedarf rechnet dabei mit der mittleren Wartezeit; andere Ziele führen zu anderen Spurzahlen und sind nicht untersucht.

Verschwinden die Probleme der Simulation bei mehr Spuren?

Die Demo rechnet das Gate auch durch simulierte Lkw. Ein einzelner Simulationslauf ist eine zufällige Stichprobe. Um zu sagen, wie genau er ist, gibt man ein Konfidenzintervall an: einen Bereich um den Simulationswert, der den wahren Wert mit einer vorgegebenen Wahrscheinlichkeit enthalten soll. Das naive Intervall hält dieses Versprechen auch bei mehr Spuren nicht und trifft den wahren Wert viel seltener als versprochen.

Besser ist die Methode Batch Means: Der Lauf wird in Abschnitte zerlegt, und das Intervall entsteht aus den Abschnittsmitteln. Wenige, lange Abschnitte sind dabei besser als viele kurze. Auch die Streuung eines einzelnen Laufs schrumpft mit mehr Spuren nicht, sie wächst eher. Und bei kurzen Läufen mit hoher Auslastung liegt die Simulation wegen des leeren Starts zu niedrig.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell: gleich schnelle Spuren, eine Schlange ohne Platzgrenze und ohne Prioritäten, zufällige Zeiten ohne Gedächtnis, eine gleichbleibende Ankunftsrate. „Getrennte Schlangen“ heißt hier zufällige Zuteilung. Wählen die Lkw die kürzeste Schlange, liegt das Ergebnis zwischen beiden Fällen; das behandelt eine andere Demo zum Thema. Die Demo zeigt, wie die Mechanik wirkt, nicht wie viele Spuren ein bestimmtes Gate braucht.

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: Poisson-Ankünfte mit Rate \(\lambda\), exponentielle Abfertigung mit Rate \(\mu\) je Spur (3 min Mittel), \(c\) Spuren, eine FIFO-Schlange, unbegrenzt (Kendall-Notation M/M/c). Angebot \(a = \lambda/\mu\), Auslastung je Spur \(\rho = a/c\); ein Gleichgewicht gibt es nur bei \(\rho < 100\,\%\). Mit \(c = 1\) ist es genau die M/M/1-Schlange der Demo mit nur einer Spur.
• Getrennte Schlangen: Jeder Lkw wird zufällig einer Spur zugeteilt (gleichverteilt) und wartet nur dort. Der Vergleich hält die Gesamtkapazität gleich.
• Regler: Spuren (1 bis 16), Auslastung (10 bis 97 %), Lauflänge (1 000 bis 50 000 Lkw), Zufalls-Seed. Voreinstellung: 4 Spuren, ρ = 90 %, 10 000 Lkw.
• Simulation: Ereignisliste mit \(c\) Spuren; der Zufall kommt aus SplitMix64 mit getrennten Strömen für Ankünfte, Bedienzeiten und die Spurzuteilung. Zur Gegenprobe dient die Kiefer-Wolfowitz-Rekursion (FIFO, \(c\) Server, ohne Ereignisliste): Ein ankommender Lkw nimmt die Spur, die am frühesten frei wird. Beide liefern Kunde für Kunde dieselben Wartezeiten.

Erlang C und die Wartezeit

Die Zahl der Lkw im System ist eine Geburts-Sterbe-Kette mit Geburtsrate \(\lambda\) und Sterberate \(\min(n, c)\,\mu\). Mit \(p_0 = \Bigl[\sum_{k<c} \frac{a^k}{k!} + \frac{a^c}{c!\,(1-\rho)}\Bigr]^{-1}\) gilt \(p_n = p_0\,\frac{a^n}{n!}\) für \(n \le c\) und \(p_n = p_0\,\frac{a^n}{c!\,c^{\,n-c}}\) für \(n > c\). Die Wahrscheinlichkeit zu warten (PASTA) ist die Formel von Erlang C:

\[C(c, a) = \sum_{n \ge c} p_n = \frac{a^c/(c!\,(1-\rho))}{\sum_{k<c} a^k/k! + a^c/(c!\,(1-\rho))}.\]

Numerisch stabil rechnet die Demo über die Erlang-B-Rekursion \(B_k = \frac{a B_{k-1}}{k + a B_{k-1}}\) und \(C = \frac{B_c}{1 - \rho(1 - B_c)}\). Die mittlere Wartezeit in der gemeinsamen Schlange ist die Wahrscheinlichkeit zu warten mal die mittlere Wartezeit eines Wartenden, \(1/(c\mu - \lambda)\):

\[W_q = \frac{C(c,a)}{c\mu - \lambda}\]

Weiter gelten \(L_q = \lambda W_q\), \(W = W_q + 1/\mu\), \(L = L_q + a\) (Little’s Gesetz) und \(P(W_q > t) = C\,e^{-(c\mu-\lambda)t}\).

Getrennte Schlangen und Pooling-Faktor

Teilt man den Poisson-Strom zufällig auf \(c\) Spuren auf, entstehen \(c\) unabhängige M/M/1-Schlangen mit Rate \(\lambda/c\):

\[W_q^{\text{getrennt}} = \frac{\rho}{\mu - \lambda/c}\]

Der Pooling-Faktor, den die Befunde unten nennen, ist der Quotient aus der Wartezeit bei getrennten und bei gemeinsamer Schlange:

\[W_q^{\text{getrennt}}/W_q^{\text{gemeinsam}}\]

Der Spurbedarf ist die kleinste ganze Zahl \(c > a\) mit \(W_q(c, a) \le\) Ziel; er wächst ungefähr wie \(a\) plus ein Vielfaches von \(\sqrt a\). Als unabhängige Referenz im Test dient das lineare Gleichungssystem der abgeschnittenen Geburts-Sterbe-Kette mit Sterberate \(\min(n, c)\,\mu\).

Befunde

Alle Zahlen stammen aus den Formeln und Messreihen der Demo (jede steht in deren Tests, tests/test_claims.py) und gelten bei 3 min Abfertigung je Spur. Die vorgerechnete Messreihe umfasst 5 Spurzahlen × 4 Auslastungen × 6 Lauflängen mit je 400 Läufen (Standardfehler einer Abdeckung höchstens 2,5 Prozentpunkte). Ausnahmen sind genannt.

Frage	Befund
Was sagt Erlang C?	4 Spuren, ρ = 80 %: 60 % der Lkw warten, im Mittel 2,2 min. 4 Spuren, ρ = 90 %: 79 % warten, 5,9 min. 16 Spuren, ρ = 95 %: 78 % warten, 2,9 min.
Was bringt die gemeinsame Schlange?	Wartezeit bei c getrennten gegen eine gemeinsame Schlange, ρ = 90 %: c = 2 2,1-fach, c = 4 4,6-fach, c = 8 10-fach, c = 16 24-fach. Bei ρ = 50 %: c = 2 3-fach, c = 4 11,5-fach, c = 8 68-fach. Mit einer Spur gibt es nichts zu poolen (Faktor 1).
Wie viele Spuren braucht ein Gate (Ziel: im Mittel höchstens 1 min Wartezeit)?	Angebot a = 2: 4 Spuren (Auslastung 50 %), a = 5: 7 (71 %), a = 10: 12 (83 %), a = 20: 22 (91 %), a = 50: 53 (94 %), a = 100: 103 (97 %), a = 200: 203 (98 %). Große Gates brauchen nur wenige Spuren mehr als das Angebot (a = 100: 3, a = 200: 3, a = 2: 2).
Und die Faustregel „höchstens 80 % Auslastung“?	Für kleine Gates zu knapp: a = 2 ergibt 3 Spuren und 1,3 min Wartezeit (Ziel 1 min verfehlt); a = 5 trifft genau (7 Spuren). Für große Gates zu großzügig: a = 10: 13 statt 12, a = 20: 25 statt 22, a = 50: 63 statt 53, a = 100: 125 statt 103.
Trifft das 95-%-Intervall bei mehr Spuren?	Das naive Intervall trifft in keiner der 120 Zellen häufiger als in 51 % der Fälle; bei ρ = 90 % und 10 000 Lkw für c = 1, 2, 4, 8, 16 in 8 bis 11 % der Fälle. Batch Means mit 20 Batches: 81 bis 84 % für alle Spurzahlen bei ρ = 90 % und 10 000 Lkw, 83 bis 87 % bei ρ = 95 % und 50 000 Lkw. 5 Batches sind in 117 von 120 Zellen mindestens so gut wie 20.
Schrumpft die Streuung eines Laufs mit mehr Spuren?	Nein, sie wächst: relative Standardabweichung der Wartezeit bei ρ = 90 % und 10 000 Lkw 21 % (c = 1), 21 %, 21 %, 24 % (c = 8), 31 % (c = 16).

Grenzen

• Gleiche Last je Spur: Die Auslastung gilt je Spur; bei gleichem Angebot ändert sich mit \(c\) also die Zahl der Spuren und nicht die Last je Spur. Der Vergleich „eine gemeinsame gegen \(c\) getrennte“ hält die Gesamtkapazität gleich.
• Zufällige Zuteilung: „Getrennte Schlangen“ heißt hier zufällige Zuteilung. Wählen Kunden die kürzeste Schlange, liegt das Ergebnis zwischen beiden Fällen; das ist nicht Gegenstand dieser Demo, sondern der Demo zu Power-of-d-Choices.
• Annahmen: Alle Spuren sind gleich schnell, die Schlange ist FIFO ohne Prioritäten. Zu unterschiedlich schnellen Spuren gibt es keine weitere Demo.
• Mittlere Wartezeit: Der Spurbedarf rechnet mit der mittleren Wartezeit; Ziele wie „95 % der Lkw warten höchstens 5 min“ führen zu anderen Spurzahlen (nicht untersucht).
• Startverzerrung: Die Läufe starten bewusst leer und werten alles aus, ohne Einschwingzeit. Bei ρ = 95 % und 1 000 Lkw liegt der Mittelwert für alle Spurzahlen 27 bis 33 % unter der Formel, bei 50 000 Lkw im Rauschen. Bei ρ = 90 % und 10 000 Lkw sind es höchstens 2,5 % (Standardfehler des Mittels rund 1 Prozentpunkt), bei 1 000 Lkw 9 bis 16 %. Die Anzeige „simuliert gegen Formel“ liegt bei kurzen Läufen hoher Auslastung deshalb zu niedrig.
• Messreihe: Sie läuft bei vier Auslastungen (50, 80, 90, 95 %) und fünf Spurzahlen (1, 2, 4, 8, 16); die App zeigt für andere Werte die nächste gemessene Zelle und sagt das. Die Live-Ansicht rechnet einen Lauf; Intervalle über viele Läufe stehen nur in den vorgerechneten Messreihen.

Quellen

• Erlang, A. K. (1917): Løsning af nogle Problemer fra Sandsynlighedsregningen af Betydning for de automatiske Telefoncentraler. Elektroteknikeren (Kopenhagen); enthält die Formeln für Verlust und Wartezeit.
• Kiefer, J., Wolfowitz, J. (1955): On the theory of queues with many servers. Transactions of the American Mathematical Society 78, 1–18.
• Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/mmc-queue-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo.