Eine Einführung in die Warteschlangentheorie

Warteschlangentheorie ist das mathematische Studium des Wartens oder Wartens in Reihen. Warteschlangen enthalten Kunden (oder „Gegenstände“) wie Personen, Gegenstände oder Informationen. Warteschlangen bilden sich, wenn begrenzte Ressourcen für die Bereitstellung von a Bedienung. Befinden sich beispielsweise 5 Registrierkassen in einem Lebensmittelgeschäft, bilden sich Warteschlangen, wenn mehr als 5 Kunden gleichzeitig für ihre Artikel bezahlen möchten.

Ein Grund Warteschlangensystem besteht aus einem Ankunftsprozess (wie Kunden in der Warteschlange ankommen, wie viele Kunden insgesamt anwesend sind), der Warteschlange selbst, dem Serviceprozess für die Betreuung dieser Kunden und dem Verlassen des Systems.

Mathematisch Warteschlangenmodelle werden häufig in Software und Unternehmen verwendet, um die beste Verwendung begrenzter Ressourcen zu ermitteln. Warteschlangenmodelle können folgende Fragen beantworten: Wie hoch ist die Wahrscheinlichkeit, dass ein Kunde 10 Minuten in der Warteschlange wartet? Was ist die durchschnittliche Wartezeit pro Kunde?

Die folgenden Situationen sind Beispiele dafür, wie die Warteschlangentheorie angewendet werden kann:

Schlange bei einer Bank oder einem Geschäft
Warten auf die Beantwortung eines Anrufs durch einen Kundendienstmitarbeiter, nachdem der Anruf gehalten wurde
Ich warte auf einen Zug
Warten auf einen Computer, der eine Aufgabe ausführt oder antwortet
Warten auf eine automatische Autowäsche, um eine Reihe von Autos zu reinigen

Charakterisierung eines Warteschlangensystems

Warteschlangenmodelle analysieren, wie Kunden (einschließlich Personen, Objekten und Informationen) einen Service erhalten. Ein Warteschlangensystem enthält:

Ankunftsprozess. Der Ankunftsprozess ist einfach, wie Kunden ankommen. Sie können alleine oder in Gruppen in eine Warteschlange geraten und in bestimmten Intervallen oder nach dem Zufallsprinzip eintreffen.
Verhalten. Wie verhalten sich Kunden, wenn sie in der Schlange stehen? Einige könnten bereit sein, auf ihren Platz in der Warteschlange zu warten; andere können ungeduldig werden und gehen. Wieder andere entscheiden sich möglicherweise für eine spätere Wiederaufnahme der Warteschlange, z. B. wenn der Kundendienst angehalten wird, und rufen in der Hoffnung, einen schnelleren Service zu erhalten, zurück.
Wie Kunden betreut werden. Dies umfasst die Zeitspanne, in der ein Kunde bedient wird, die Anzahl der verfügbaren Server, um den Kunden zu helfen, unabhängig davon, ob Kunden einzeln oder in Stapeln bedient werden, und die Reihenfolge, in der Kunden bedient werden Servicedisziplin.
Servicedisziplin bezieht sich auf die Regel, nach der der nächste Kunde ausgewählt wird. Obwohl in vielen Einzelhandelsszenarien die Regel „Wer zuerst kommt, mahlt zuerst“ verwendet wird, erfordern andere Situationen möglicherweise andere Servicetypen. Beispielsweise können Kunden in der Reihenfolge ihrer Priorität bedient werden oder basierend auf der Anzahl der Artikel, die gewartet werden müssen (z. B. in einer Schnellstraße in einem Lebensmittelgeschäft). Manchmal wird der letzte Kunde, der ankommt, zuerst bedient (z. B. in einem Stapel schmutzigen Geschirrs, in dem derjenige oben der erste ist, der gewaschen wird)..
Wartezimmer. Die Anzahl der Kunden, die in der Warteschlange warten dürfen, kann je nach verfügbarem Speicherplatz begrenzt sein.

Mathematik der Warteschlangentheorie

Kendalls Notation ist eine Kurzschreibweise, die die Parameter eines grundlegenden Warteschlangenmodells angibt. Kendalls Notation ist in der Form A / S / c / B / N / D geschrieben, wobei jeder der Buchstaben für verschiedene Parameter steht.

Der Begriff A beschreibt, wann Kunden in der Warteschlange eintreffen - insbesondere die Zeit zwischen dem Eintreffen oder interarrival Zeiten. Mathematisch gibt dieser Parameter die Wahrscheinlichkeitsverteilung an, der die Interarrival-Zeiten folgen. Eine gebräuchliche Wahrscheinlichkeitsverteilung, die für den A-Term verwendet wird, ist die Poisson-Verteilung.
Der Begriff S beschreibt, wie lange es dauert, bis ein Kunde die Warteschlange verlassen hat. Mathematisch gibt dieser Parameter die Wahrscheinlichkeitsverteilung an, mit der diese Servicezeiten Folgen. Die Poisson-Verteilung wird auch häufig für den S-Term verwendet.
Der Begriff c gibt die Anzahl der Server im Warteschlangensystem an. Das Modell geht davon aus, dass alle Server im System identisch sind, sodass sie alle durch den obigen S-Begriff beschrieben werden können.
Der Begriff B gibt die Gesamtzahl der Elemente an, die sich im System befinden können, und schließt Elemente ein, die sich noch in der Warteschlange befinden, sowie Elemente, die bearbeitet werden. Obwohl viele Systeme in der realen Welt eine begrenzte Kapazität haben, ist das Modell leichter zu analysieren, wenn diese Kapazität als unendlich angesehen wird. Wenn folglich die Kapazität eines Systems groß genug ist, wird das System üblicherweise als unendlich angenommen.
Der Begriff N gibt die Gesamtzahl der potenziellen Kunden an - d. H. Die Anzahl der Kunden, die jemals in das Warteschlangensystem eintreten könnten -, die als endlich oder unendlich angesehen werden können.
Der D-Begriff gibt die Servicedisziplin des Warteschlangensystems an, z. B. "Wer zuerst kommt, mahlt zuerst" oder "Wer zuerst mahlt".

Das kleine Gesetz, Wie der Mathematiker John Little erstmals bewiesen hat, kann die durchschnittliche Anzahl der Elemente in einer Warteschlange berechnet werden, indem die durchschnittliche Rate, mit der die Elemente im System ankommen, mit der durchschnittlichen Zeit multipliziert wird, die sie in der Warteschlange verbringen.

In der mathematischen Notation lautet das Little'sche Gesetz: L = λW
L ist die durchschnittliche Anzahl von Gegenständen, λ ist die durchschnittliche Ankunftsrate der Gegenstände im Warteschlangensystem, und W ist die durchschnittliche Zeitdauer, die die Gegenstände im Warteschlangensystem verbringen.
Das Little'sche Gesetz geht davon aus, dass sich das System im „stationären Zustand“ befindet - die mathematischen Variablen, die das System charakterisieren, ändern sich nicht über die Zeit.

Obwohl das Little'sche Gesetz nur drei Eingaben benötigt, ist es recht allgemein und kann auf viele Warteschlangensysteme angewendet werden, unabhängig von der Art der Elemente in der Warteschlange oder der Art, wie Elemente in der Warteschlange verarbeitet werden. Das Little'sche Gesetz kann hilfreich sein, um die Leistung einer Warteschlange über einen bestimmten Zeitraum zu analysieren oder um die aktuelle Leistung einer Warteschlange schnell zu beurteilen.

Beispiel: Ein Schuhkartonhersteller möchte die durchschnittliche Anzahl der Schuhkartons ermitteln, die in einem Lagerhaus aufbewahrt werden. Das Unternehmen weiß, dass die durchschnittliche Ankunftsrate der Kartons im Lager 1.000 Schuhkartons pro Jahr beträgt und dass die durchschnittliche Zeit, die sie im Lager verbringen, etwa 3 Monate oder ein Vierteljahr beträgt. Die durchschnittliche Anzahl der Schuhkartons im Lager ergibt sich somit aus (1000 Schuhkartons / Jahr) x (¼ Jahr) oder 250 Schuhkartons.

Die zentralen Thesen

Die Warteschlangentheorie ist das mathematische Studium des Wartens oder Wartens in Reihen.
Warteschlangen enthalten „Kunden“ wie Personen, Objekte oder Informationen. Warteschlangen entstehen, wenn nur begrenzte Ressourcen für die Bereitstellung eines Dienstes zur Verfügung stehen.
Die Warteschlangentheorie kann auf Situationen angewendet werden, die vom Schlangestehen im Lebensmittelgeschäft bis zum Warten auf einen Computer reichen, um eine Aufgabe auszuführen. Es wird häufig in Software und Geschäftsanwendungen verwendet, um die beste Verwendung begrenzter Ressourcen zu ermitteln.
Mit der Kendall-Notation können die Parameter eines Warteschlangensystems angegeben werden.
Das Little-Gesetz ist ein einfacher, aber allgemeiner Ausdruck, der eine schnelle Schätzung der durchschnittlichen Anzahl von Elementen in einer Warteschlange liefern kann.

Quellen

Beasley, J. E. "Warteschlangentheorie."
Boxma, O. J. "Stochastic Performance Modeling". 2008.
Lilja, D. Messen der Computerleistung: Ein Leitfaden für Praktiker, 2005.
Little, J., und Graves, S. "Kapitel 5: Das Gesetz von Little." Aufbau von Intuition: Einblicke in grundlegende Operations Management-Modelle und -Prinzipien. Springer Science + Business Media, 2008.
Mulholland, B. "Little's Gesetz: Wie Sie Ihre Prozesse analysieren (mit Stealth-Bomber)." Process.st, 2017.

Wissenschaft