Markowsche Warteschlangen

Eine Markowsche Warteschlange weist Poisson-Ankünfte und exponentielle Bedienzeiten auf, wodurch die Anzahl der Kunden eine kontinuierliche Markow-Kette bildet, deren Gleichgewicht explizit gelöst werden kann.

Definition

Eine Markowsche Warteschlange ist ein Servicesystem, in dem Kunden gemäß einem Poisson-Prozess ankommen und unabhängige exponentielle Bedienzeiten benötigen, sodass sich die Anzahl im System als eine kontinuierliche Markow-Kette vom Geburts- und Todesprozess-Typ entwickelt, mit expliziten stationären und Wartezeitverteilungen.

Scope

Dieses Thema behandelt Kendalls Notation für Warteschlangensysteme, die M/M/1-Warteschlange mit einem Server und ihre geometrische stationäre Verteilung, Mehrserver-M/M/c- und Verlustsysteme, die Erlang-B- und C-Formeln, Stabilität und Verkehrsintensität sowie die Ableitung von mittlerer Warteschlangenlänge, Wartezeit und Größen der Auslastungsperiode aus dem zugrunde liegenden Geburts- und Todesprozess.

Core questions

• Wie entsteht die M/M/1-Warteschlange als Geburts- und Todesprozess und was ist ihre stationäre Verteilung?
• Welche Bedingung an die Verkehrsintensität gewährleistet die Stabilität der Warteschlange?
• Wie werden die mittlere Warteschlangenlänge und Wartezeit ermittelt und wie wird Little's Gesetz angewendet?
• Wie verändern mehrere Server und endliche Kapazität die Erlang-Formeln?

Key theories

M/M/1 stationäre Verteilung und Stabilität

Die Anzahl in einer M/M/1-Warteschlange hat eine geometrische stationäre Verteilung mit einem Parameter, der der Verkehrsintensität entspricht, dem Verhältnis von Ankunfts- zu Bedienrate, und die Warteschlange ist genau dann stabil, wenn dieses Verhältnis kleiner als eins ist.

Erlang-Verlust- und Verzögerungsformeln

Für Mehrserversysteme gibt die Erlang-B-Formel die Blockierungswahrscheinlichkeit in einem Verlustsystem an und die Erlang-C-Formel die Wartezeitwahrscheinlichkeit in einem Verzögerungssystem, beide abgeleitet aus den Geburts- und Todes-Gleichgewichtsgleichungen und zentral für die Kapazitätsplanung.

Clinical relevance

Markowsche Warteschlangen sind die grundlegenden Modelle für die Dimensionierung von Telefon-Bündelgruppen, Callcenter-Personal, Serverfarmen und Serviceschaltern, wobei die Erlang-Formeln die angebotene Last und die angestrebten Servicelevel in die Anzahl der benötigten Server umrechnen.

History

Erlang leitete zwischen 1909 und 1917 die Verlust- und Verzögerungsformeln für den Telefonverkehr ab, Kendall führte 1953 die systematische Ankunfts-/Bedienungs-/Server-Notation und die eingebettete Kettenanalyse ein, und Kleinrocks Abhandlung aus den 1970er Jahren wandte die Theorie auf Computer- und Kommunikationsnetzwerke an.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

Was bedeutet M/M/1?

In Kendalls Notation bezeichnet das erste M Markowsche (Poisson-)Ankünfte, das zweite M exponentielle Bedienzeiten und die 1 einen einzelnen Server.

Wann ist eine Markowsche Warteschlange stabil?

Wenn die Verkehrsintensität, die Ankunftsrate geteilt durch die gesamte Bedienrate, kleiner als eins ist; andernfalls wächst die Warteschlange unbegrenzt und es existiert keine stationäre Verteilung.