Eine Einführung in die Warteschlangentheorie

The best protection against click fraud.

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

Eine grundlegende Warteschlangensystem besteht aus einem Ankunftsprozess (wie Kunden an der Warteschlange ankommen, wie viele Kunden anwesend sind total), die Warteschlange selbst, den Serviceprozess für die Betreuung dieser Kunden und Abfahrten von der System.

Mathematisch Warteschlangenmodelle werden häufig in Software und Unternehmen verwendet, um festzustellen, wie begrenzte Ressourcen am besten genutzt werden können. Warteschlangenmodelle können Fragen beantworten wie: Wie hoch ist die Wahrscheinlichkeit, dass ein Kunde 10 Minuten in der Schlange steht? Was ist die durchschnittliche Wartezeit pro Kunde?

instagram viewer

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

  • Schlangestehen 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, um eine Aufgabe auszuführen oder zu antworten
  • Warten auf eine automatische Autowäsche, um eine Reihe von Autos zu reinigen

Charakterisierung eines Warteschlangensystems

Warteschlangenmodelle analysieren, wie Kunden (einschließlich Personen, Objekte 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 zufällig ankommen.
  • 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 dafür, sich später wieder der Warteschlange anzuschließen, z. B. wenn sie mit dem Kundendienst in die Warteschleife gestellt werden, und beschließen, in der Hoffnung auf einen schnelleren Service zurückzurufen.
  • Wie Kunden bedient werden. Dies beinhaltet die Zeitdauer, in der ein Kunde gewartet wird, die Anzahl der verfügbaren Server, um den Kunden zu helfen, ob Kunden einzeln oder in Chargen bedient werden, und die Reihenfolge, in der Kunden bedient werden, wird ebenfalls genannt 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" angewendet wird, können in anderen Situationen andere Arten von Diensten erforderlich sein. Beispielsweise können Kunden in der Reihenfolge ihrer Priorität oder basierend auf der Anzahl der Artikel bedient werden, die sie warten 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 der darüber liegende zuerst 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 unterschiedliche Parameter steht.

  • Der Begriff A beschreibt, wann Kunden an der Warteschlange ankommen - insbesondere die Zeit zwischen Ankünften oder Interarrival Zeiten. Mathematisch gibt dieser Parameter die an Wahrscheinlichkeitsverteilung dass 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 gewartet wird, nachdem er die Warteschlange verlassen hat. Mathematisch gibt dieser Parameter die Wahrscheinlichkeitsverteilung an, die 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 mit dem obigen S-Begriff beschrieben werden können.
  • Der B-Begriff gibt die Gesamtzahl der Elemente an, die sich im System befinden können, und umfasst Elemente, die sich noch in der Warteschlange befinden und die gewartet werden. Obwohl viele Systeme in der realen Welt eine begrenzte Kapazität haben, ist das Modell einfacher zu analysieren, wenn diese Kapazität als unendlich angesehen wird. Wenn folglich die Kapazität eines Systems groß genug ist, wird allgemein angenommen, dass das System unendlich ist.
  • Der N-Term gibt die Gesamtzahl potenzieller 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 Begriff D gibt die Servicedisziplin des Warteschlangensystems an, z. B. "Wer zuerst kommt, mahlt zuerst" oder "Wer zuerst kommt, mahlt zuerst".

Das Gesetz von Little, der zuerst vom Mathematiker John Little bewiesen wurde, gibt an, dass die durchschnittliche Anzahl von Elementen in einer Warteschlange sein kann berechnet durch Multiplizieren der durchschnittlichen Rate, mit der die Artikel im System ankommen, mit der durchschnittlichen Zeitdauer, in der sie ankommen darin verbringen.

  • In der mathematischen Notation lautet das Little'sche Gesetz: L = λW
  • L ist die durchschnittliche Anzahl von Elementen, λ ist die durchschnittliche Ankunftsrate der Elemente im Warteschlangensystem und W ist die durchschnittliche Zeit, die die Elemente im Warteschlangensystem verbringen.
  • Das Gesetz von Little geht davon aus, dass sich das System in einem „stationären Zustand“ befindet - die mathematischen Variablen, die das System charakterisieren, ändern sich im Laufe der Zeit nicht.

Obwohl das Little'sche Gesetz nur drei Eingaben benötigt, ist es ziemlich allgemein und kann auf viele angewendet werden Warteschlangensysteme, unabhängig von der Art der Elemente in der Warteschlange oder der Art und Weise, wie Elemente in der Warteschlange verarbeitet werden Warteschlange. Das Gesetz von Little kann hilfreich sein, um zu analysieren, wie sich eine Warteschlange im Laufe der Zeit entwickelt hat, oder um schnell zu beurteilen, wie sich eine Warteschlange derzeit verhält.

Beispiel: Ein Schuhkartonhersteller möchte die durchschnittliche Anzahl der Schuhkartons ermitteln, die in einem Lagerhaus gelagert 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 Warteschlangens oder des Wartens in Warteschlangen.
  • Warteschlangen enthalten „Kunden“ wie Personen, Objekte oder Informationen. Warteschlangen bilden sich, wenn nur begrenzte Ressourcen für die Bereitstellung eines Dienstes vorhanden sind.
  • Die Warteschlangentheorie kann auf Situationen angewendet werden, die vom Schlangestehen im Lebensmittelgeschäft bis zum Warten auf die Ausführung einer Aufgabe durch einen Computer reichen. Es wird häufig in Software- und Geschäftsanwendungen verwendet, um den besten Weg zur Verwendung begrenzter Ressourcen zu ermitteln.
  • Mit der Kendall-Notation können die Parameter eines Warteschlangensystems angegeben werden.
  • Das Little'sche 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. E. "Warteschlangentheorie."
  • Boxma, O. J. J. "Stochastische Leistungsmodellierung." 2008.
  • Lilja, D. Messen der Computerleistung: Ein Leitfaden für Praktiker, 2005.
  • Little, J. und Graves, S. "Kapitel 5: Das Gesetz von Little." Im Intuition aufbauen: Erkenntnisse aus grundlegenden Operations Management-Modellen und -Prinzipien. Springer Science + Business Media, 2008.
  • Mulholland, B. "Das Gesetz von Little: Wie Sie Ihre Prozesse analysieren (mit Stealth-Bombern)."Process.st, 2017.
instagram story viewer