Warteschlangentheorie-Simulator (M/M/1)

Ankunftsraten, Bedienraten und Stabilität

Rechenbeispiel — Warteschlangentheorie-Simulator (M/M/1)

Auslastung ρ	0,750
M/M/1-Prognose für L	3,000
Ankunftsrate im Durchlauf	3,0084
W (gemittelt über Kunden)	1,012
Little-Prognose für L	3,045
Gezähltes L (Zeitmittel)	3,044
Differenz dieser beiden Werte	0,0006
Standardfehler von L	0,121

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

die Rho-Klippe 🖖

L = ρ/(1−ρ) wächst nicht gleichmäßig. Die Funktion hat eine vertikale Asymptote bei ρ = 1. Wenn die Auslastung von 90 % auf 99 % kriecht, springt die durchschnittliche Warteschlangenlänge von 9 Personen auf 99. Genau an der Kapazitätsgrenze ist sie unbeschränkt. Das ist die „Rho-Klippe“. Eine Warteschlange fühlt sich bei 80 % Auslastung fast genauso an wie bei 85 %. Treibst du sie jedoch auf 95 %, explodieren die Wartezeiten. W = 1/(μ−λ) hat nämlich dieselbe Singularität. Der Nenner schrumpft gegen null, der Zähler wächst nicht. Darum werden reale Systeme wie Callcenter und Notaufnahmen absichtlich weit unter 100 % Kapazität überdimensioniert. Genau dieser scheinbar verschwendete Puffer nahe der Grenze bewahrt dich vor dem Absturz über die Klippe.

der Zufall baut die Warteschlange 🖖

In M/M/1 stehen die beiden M für „Markow“. Ankünfte erfolgen zufällig (Poisson). Bedienzeiten variieren zufällig (exponentiell). Das Ganze läuft über einen einzigen Server. Der Kerngedanke ist überraschend. Eine Warteschlange kann sich aufbauen, selbst wenn der Server im Durchschnitt schneller ist, als die Kunden eintreffen. Würden alle wie ein Uhrwerk erscheinen und jeder Auftrag gleich lang dauern, würde ein Server mit freien Kapazitäten nie eine Schlange bilden. Warten entsteht durch Variabilität, nicht durch Überlastung. Setzt du λ weit unter μ, flackert trotzdem immer wieder eine Schlange auf. Stellst du beide Muster auf Uhrwerk, verlässt die Kurve oben nie die 0 und 1. Bei identischen Lücken und identischen Aufträgen ist der Server bei jeder Auslastung unter 1 immer fertig, bevor der nächste Kunde eintrifft.

das Gesetz von Little verlangt fast nichts 🖖

Die hier gezeigten L und W sind nicht unabhängig. Sie erfüllen L = λW und ebenso Lq = λWq. Diese Identität setzt fast nichts voraus. John Little hat das 1961 bewiesen. Es braucht dafür nur Folgendes. Eine langfristige Ankunftsrate, die existiert und endlich ist. Dazu eine langfristige mittlere Verweildauer im System, für die das Gleiche gilt. Keine Poisson-Ankünfte. Keine exponentielle Bedienung. Keine Unabhängigkeit. Nicht nur ein Server. Nicht einmal ein stationärer Zustand der Verteilung. In der Tabelle oben siehst du, was das wert ist. Speis ein Uhrwerk- oder ein schubweises Muster in einen der Ströme ein. ρ/(1−ρ) fällt bei einer Einstellung 4-mal zu hoch und bei einer anderen 15-mal zu niedrig aus. λW und das unabhängig gezählte L bleiben hingegen bei jeder der 405 durchgespielten Einstellungen auf 0,011 Kunden zusammen. Dieselbe Beziehung steuert eine Krankenhausstation, den unfertigen Bestand einer Fabrik und das Lager eines Geschäfts. Der durchschnittliche Inhalt entspricht der Ankunftsrate multipliziert mit der durchschnittlichen Verweildauer.

zwei Durchschnitte, und nur einer gehört einem Kunden 🖖

Stell beide Muster auf Uhrwerk und lies zwei Zeilen der Tabelle gegeneinander. Die Warteschlange, die ein eintreffender Kunde vorfindet, beträgt 0,000. Der Beobachter, der dieselbe Schlange über die Zeit zählt, erhält 0,751. Jeder Kunde betritt ein leeres System. Der Server ist drei Viertel der Zeit beschäftigt. Beides ist richtig. L gewichtet die Warteschlangenlänge nach der Zeit. Die Sicht des Ankömmlings gewichtet sie nach Kunden. Nichts zwingt zwei verschiedene Gewichtungen zur Übereinstimmung. Das Gesetz von Little paart einen Zeitdurchschnitt mit einem Kundendurchschnitt und behauptet nie, dass sie identisch sind. Bei Poisson-Ankünften fallen sie zusammen. Darum übersieht man den Unterschied so leicht. Eine Ankunft ist zu jedem Zeitpunkt gleich wahrscheinlich. Die Sicht eines Kunden ist also eine faire Stichprobe der Uhr. Das ist die PASTA-Eigenschaft. Sie gehört zu den Ankünften, nicht zur Warteschlange. Wechselst du bei den Ankünften auf schubweise, liefert derselbe Durchlauf 27,011 im Vergleich zu einem Zeitdurchschnitt von 21,482. Ein Schub bedeutet nämlich, dass die meisten Kunden genau dann ankommen, wenn die Schlange am längsten ist.

Aufgaben vollständig gelöst

Eine Warteschlange mit 3 Ankünften pro Stunde und 20 % Anstieg 5 Schritte
Kunden treffen mit 3 pro Stunde ein, und der Server schafft 4 pro Stunde. Der Server ist ein Viertel der Zeit untätig. Das klingt komfortabel. Berechne die entstehende Warteschlange und zeige, was ein Anstieg der Ankünfte um 20 % bewirkt.
1. Die Markow-Kette im Gleichgewicht. Die Rate in jeden Zustand entspricht der Rate hinaus. Das liefert Pₙ = (1 − ρ)ρⁿ. Das ist eine geometrische Verteilung über die Warteschlangenlänge. ρ steht für den Anteil der Zeit, in der der Server beschäftigt ist. Hier ist ρ = 0,75.
  
  $P_{n} = (1 - ρ) ρ^{n}, ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750$
2. Der Mittelwert dieser Verteilung ist ρ/(1 − ρ). Schau dir den Nenner an. Er steht nicht für die freie Kapazität in Kunden pro Stunde, sondern für den freien Anteil. 3 Personen befinden sich durchschnittlich im System bei einem Server, der ein Viertel des Tages stillsteht.
  
  $L = n \geq 0 \sum n P_{n} = \frac{ρ}{1 - ρ} = \frac{0.750}{0.250} = 3.000$
3. Zieh die Person ab, die gerade bedient wird. Sie ist mit der Wahrscheinlichkeit ρ anwesend. Es bleiben 2,25 Wartende.
  
  $L_{q} = L - ρ = 3.000 - 0.750 = 2.250$
4. Das Gesetz von Little verwandelt eine Population in eine Zeit und braucht dafür überhaupt keine Annahme über die Verteilung. Die durchschnittliche Anzahl im System ist die Ankunftsrate mal der durchschnittlichen Verweildauer. 1 Stunde im System, davon 45 Minuten Wartezeit, für einen Auftrag, der 15 Minuten dauert.
  
  $W = \frac{L}{λ} = \frac{3.000}{3} = 1.000, W_{q} = \frac{L _{q}}{λ} = 0.750$
5. Nun erhöhst du λ auf 3,6. Die Auslastung steigt von 0,75 auf 0,90. Das sind 20 % mehr Arbeit. ρ/(1 − ρ) springt von 3 auf 9.
  
  $λ = 3.6 : ρ = 0.90, L = 9; λ = 3.96 : ρ = 0.99, L = 99$
Antwort

Das Tool gibt L = 3,000, L_q = 2,250, W = 1,000, W_q = 0,750 bei 75 % Auslastung aus. Die Lektion steckt im Nenner von ρ/(1 − ρ). Die Warteschlange wird nicht dadurch bestimmt, wie viel freie Kapazität du hast, sondern wie viel dir als Bruchteil bleibt. Diesen Bruchteil verbrauchst du, wenn du Last hinzufügst. 20 % mehr Ankünfte verdreifachen die Schlange. Weitere 10 % obendrauf bringen ρ auf 0,99 und machen daraus 99. Genau deshalb brechen Krankenhäuser, Autobahnen und Festplattencontroller bei hoher Auslastung zusammen, anstatt sanft abzubauen. Und deshalb ist der Satz „Wir sind erst bei 90 % Kapazität“ nicht die Beruhigung, nach der er klingt.

$L = \frac{ρ}{1 - ρ} blows up at ρ = 1 : + 20% λ ⟹ \times 3 queue$
Dieselben Raten ohne den Zufall 5 Schritte
Lass λ bei 3 pro Stunde und μ bei 4 pro Stunde und nimm jeglichen Zufall heraus. Die Ankünfte erfolgen exakt im Abstand von 20 Minuten. Jeder Auftrag dauert exakt 15 Minuten. Die Auslastung liegt immer noch bei 0,750. Berechne die resultierende Warteschlange und den Abstand von ρ/(1 − ρ) zu diesem Wert.

Öffne diese Aufgabe im Tool
1. Kunde k kommt zur Zeit k/λ an. Da der Server frei ist, geht er zur Zeit k/λ + 1/μ. Der nächste trifft bei (k + 1)/λ ein. Der Server ist rechtzeitig fertig, wann immer 1/μ ≤ 1/λ gilt. Das ist nichts anderes als ρ ≤ 1 umgeschrieben.
  
  $ρ = \frac{λ}{μ} = \frac{3}{4} = 0.750, \frac{1}{λ} = 0.3333 > \frac{1}{μ} = 0.250$
2. Solange die Schlange stabil ist, wartet also niemand. W_q = 0. W ist allein die Bedienzeit, 1/μ = 0,250 Stunden. 15 Minuten im Gebäude, in denen jede Minute für die Bedienung genutzt wird.
  
  $\frac{k}{λ} + \frac{1}{μ} \leq \frac{k + 1}{λ} ⟺ \frac{1}{μ} \leq \frac{1}{λ} ⟺ ρ \leq 1 ⟹ W_{q} = 0$
3. Das Gesetz von Little verwandelt das in eine Population. Es braucht dazu keine Verteilung. L = λW = 3 × 0,250 = 0,750 und L_q = 0. 0,75 Kunden. Das entspricht exakt dem Anteil der Zeit, in der der Server beschäftigt ist.
  
  $W = \frac{1}{μ} = 0.250, L = λW = 3 \times 0.250 = 0.750, L_{q} = λ W_{q} = 0$
4. Nun ist ρ/(1 − ρ) = 0,750 / 0,250 = 3,000. Das ist das 4-Fache der Wahrheit. Der Faktor ist kein Zufall dieser Zahlen. M/M/1 liefert ρ/(1 − ρ), wo das Uhrwerk ρ liefert. Die Übertreibung beträgt also bei jeder Auslastung 1/(1 − ρ).
  
  $ρ 0.50 0.75 0.90 0.95 0.99 ρ / (1 - ρ) 1.000 3.000 9.000 19.000 99.000 ρ 0.500 0.750 0.900 0.950 0.990 1/ (1 - ρ) 241020100$
5. Bei ρ = 0,99 beträgt dieser Faktor 100. M/M/1 platziert 99 Personen im System. Perfekt regelmäßiger Verkehr platziert dort 0,99.
  
  $\frac{ρ / ( 1 - ρ )}{ρ} = \frac{1}{1 - ρ}; ρ = 0.99 : 99.000 ⟷ 0.990$
Antwort

Das Tool gibt W = 0,250 aus. Das Gesetz von Little wandelt das in L = 0,750 um. Dem steht eine M/M/1-Prognose von 3,000 gegenüber. Das ist ein Fehler von +299,6 %. Die Schlange war nie da. Die Rho-Klippe aus dem ersten Erkenntnisblock besteht komplett aus Variabilität. Wenn keine mehr da ist, gibt es auch bei ρ = 0,99 keine Klippe. Abseits dieser Seite liefert das ein starkes Argument für Termine. Zusätzliche Kapazität und weniger Variabilität verkürzen beide eine Warteschlange. 1/(1 − ρ) besagt, dass sich Letzteres genau dort am meisten auszahlt, wo Ersteres am schwersten zu beschaffen ist. Bei 75 % Auslastung bewirkt ein perfekt regelmäßiger Plan eine Reduktion um den Faktor 4. Bei 99 % reduziert er die Schlange um den Faktor 100. Keine echte Klinik arbeitet wie ein Uhrwerk. Dieselben Raten mit schubweisen Ankünften ergeben stattdessen 21,482.

$L_{D / D /1} = ρ = 0.750 ⟷ L_{M / M /1} = \frac{ρ}{1 - ρ} = 3.000, \frac{L _{M / M /1}}{L _{D / D /1}} = \frac{1}{1 - ρ} = 4$

Quellen (1)

Insight block 3 — how little L = λW assumes: J. D. C. Little, "A Proof for the Queuing Formula: L = λW." Operations Research 9(3), 383–387, 1961.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.