Warteschlangenentheorie

Warteschlangennetzwerke sind Systeme, in denen einzelne Warteschlangen durch ein Routing -Netzwerk verbunden sind. In diesem Bild werden Server durch Kreise, Warteschlangen durch eine Reihe von Rechtecken und das Routing -Netzwerk durch Pfeile dargestellt. In der Untersuchung von Warteschlangennetzwerken versucht man normalerweise, die zu erhalten Gleichgewichtsverteilung des Netzwerks, wenn auch in vielen Anwendungen die Untersuchung der vorübergehender Zustand ist grundlegend.

Warteschlangenentheorie ist das mathematische Studium von Warteschlangen oder Warteschlangen.^[1] Ein Warteschlangenmodell wird so konstruiert, dass Warteschlangenlängen und Wartezeiten vorhergesagt werden können.^[1] Die Warteschlangentheorie wird allgemein als Zweig von angesehen Unternehmensforschung Weil die Ergebnisse häufig verwendet werden, wenn Geschäftsentscheidungen über die Ressourcen getroffen werden, die für die Bereitstellung eines Dienstes erforderlich sind.

Die Warteschlangentheorie hat ihren Ursprung in der Forschung von Agner Krarup Erlang Als er Modelle erstellte, um das System der Kopenhagen -Telefon Exchange Company, eines dänischen Unternehmens, zu beschreiben.^[1] Die Ideen haben seitdem Anwendungen einschließlich gesehen, einschließlich Telekommunikation, Verkehrstechnik, Computer^[2] und besonders in Wirtschaftsingenieurwesenim Design von Fabriken, Geschäften, Büros und Krankenhäusern sowie im Projektmanagement.^[3][4]

Rechtschreibung

Die Schreibweise "Warteschlange" über "Warteschlangen" tritt typischerweise im Bereich der akademischen Forschung auf. Tatsächlich ist eine der Flaggschiff -Zeitschriften des Feldes Warteschlangensysteme.

Einzelne Warteschlangenknoten

Eine Warteschlange oder ein Warteschlangenknoten kann als fast ein angesehen werden Flugschreiber. Jobs oder "Kunden" kommen in der Warteschlange an, warten Sie möglicherweise einige Zeit, werden einige Zeit in Anspruch nehmen und dann von der Warteschlange abreisen.

Eine schwarze Box. Jobs kommen in die Warteschlange und gehen von der Warteschlange ab und gehen von der Warteschlange ab.

Der Warteschlangenknoten ist jedoch keine reine schwarze Box, da einige Informationen über das Innere des Warteschlangenknotens benötigt werden. Die Warteschlange verfügt über ein oder mehrere "Server", die jeweils mit einem ankommenden Job gepaart werden können, bis er abreist. Danach kann dieser Server frei mit einem anderen ankommenden Job gepaart werden.

Ein Warteschlangenknoten mit 3 Servern. Server a ist untätig und somit wird eine Ankunft zur Verarbeitung gegeben. Server b ist derzeit beschäftigt und dauert einige Zeit, bis es den Dienst seines Jobs abschließen kann. Server c hat gerade den Dienst eines Jobs abgeschlossen und wird daher als nächstes einen ankommenden Job erhalten.

Eine oft verwendete Analogie ist die der Kassiererin in einem Supermarkt. Es gibt andere Modelle, aber dies ist in der Literatur häufig auftreten. Kunden kommen an, werden von der Kassiererin bearbeitet und gehen ab. Jeder Kassierer verarbeitet jeweils einen Kunden, und daher handelt es sich um einen Warteschlangenknoten mit nur einem Server. Eine Einstellung, bei der ein Kunde sofort verlässt, wenn der Kassierer beim Eintreffen des Kunden beschäftigt ist, wird als Warteschlange ohne Puffer (oder ohne "Wartebereich" oder ähnliche Begriffe) bezeichnet. Eine Einstellung mit einer Wartezone für bis zu n Kunden werden als Warteschlange mit einem Größenpuffer bezeichnet n.

Geburts-Todesvorgang

Das Verhalten einer einzelnen Warteschlange (auch als "Warteschlangenknoten" bezeichnet) kann durch a beschrieben werden Geburts -Death -Prozess, die die Ankünfte und Abfahrten der Warteschlange beschreibt, zusammen mit der Anzahl der Jobs (auch als "Kunden" oder "Anfragen" oder eine beliebige Anzahl anderer Dinge, je nach Feld) im System. Eine Ankunft erhöht die Anzahl der Arbeitsplätze um 1 und eine Abreise (ein Job, der seinen Service abgeschlossen hat) nimmt ab k um 1.

Ein Geburts -Todesfall. Die Werte in den Kreisen repräsentieren den Zustand des Geburts-Todes. Für ein Warteschlangensystem, k ist die Anzahl der Jobs im System (entweder gewartet oder wartet, wenn die Warteschlange einen Puffer von Wartejobs hat). Das System wechselt zwischen Werten von k durch "Geburten" und "Todesfälle", die mit Raten auftreten, die durch verschiedene Werte von angegeben sind λ_i und μ_i, beziehungsweise. Darüber hinaus wird für eine Warteschlange allgemein angenommen, dass die Ankunftsraten und die Abflugsraten nicht mit der Anzahl der Jobs in der Warteschlange variieren, sodass eine einzige durchschnittliche Ankunfts-/Abflugzeit pro Zeiteinheit in der Warteschlange angenommen wird. Unter dieser Annahme hat dieser Prozess eine Ankunftsrate von λ = λ₁, λ₂, ..., λ_k und eine Abfahrtsrate von μ = μ₁, μ₂, ..., μ_k (Siehe nächste Abbildung).

Eine Warteschlange mit 1 Server, Ankunftsrate λ und Abfahrtsrate μ.

Balance -Gleichungen

Das Gleichgewichtszustand Gleichungen für den Geburts- und Tod, der als das bezeichnet wird Balance -Gleichungen, sind wie folgt. Hier ${\ displayStyle p_ {n}}$ bezeichnet die stationäre Wahrscheinlichkeit, im Zustand zu sein n.

${\ displayStyle \ mu _ {1} p_ {1} = \ lambda _ {0} p_ {0}}$

$oder$

$oder n}}$

Die ersten beiden Gleichungen implizieren

$oder$

und

$oder mu _ {1} p_ {1}-\ lambda _ {0} p_ {0}) = {\ frac {\ lambda _ {1}} {\ mu _ {2}} p_ {1} = {\ frac oder$

Durch mathematische Induktion,

$oder 1} \ cdots \ mu _ {1}}} p_ {0} = p_ {0} \ prod _ {i = 0}^{n-1} {\ frac {\ lambda _ {i} {\ mu _ {i+1}}}.}$

Die Bedingung $oder }^{n-1} {\ frac {\ lambda _ {i}} {\ mu _ {i+1}} = 1}$ führt zu:

$oder _ {i}} {\ mu _ {i+1}}}}},}$

was zusammen mit der Gleichung für ${\ displayStyle p_ {n}}$ ${\ displayStyle (N \ Geq 1)}$beschreibt die erforderlichen stationären Wahrscheinlichkeiten vollständig.

Kendalls Notation

Einzelne Warteschlangenknoten werden normalerweise mit Verwendung beschrieben Kendalls Notation in der Form a/s/c wo A beschreibt die Verteilung der Dauer zwischen jeder Ankunft in die Warteschlange, S Die Verteilung der Servicezeiten für Jobs und c Die Anzahl der Server am Knoten.^[5][6] Für ein Beispiel der Notation die M/M/1 -Warteschlange ist ein einfaches Modell, bei dem ein einzelner Server Jobs bedient, die nach einem ankommen Poisson -Prozess (wo sich die Dauer der Inter-Ursachen befinden exponentiell verteilt) und exponentiell verteilte Servicezeiten haben (der m bezeichnet a Markov -Prozess). In einem (n M/G/1 -Warteschlange, der g steht für "allgemein" und zeigt einen willkürlichen Anteil an Wahrscheinlichkeitsverteilung für Servicezeiten.

Beispielanalyse einer m/m/1 -Warteschlange

Betrachten Sie eine Warteschlange mit einem Server und den folgenden Eigenschaften:

• λ: die Ankunftsrate (die gegenseitige Zeit zwischen jedem Kunden, der z. B. 10 Kunden pro Sekunde ankommt);
• μ: die gegenseitige Servicezeit (die erwartete Anzahl der aufeinanderfolgenden Serviceabschlüsse pro Zeiteinheit, z. B. pro 30 Sekunden);
• n: der Parameter, der die Anzahl der Kunden im System charakterisiert;
• P_n: Die Wahrscheinlichkeit, dass es da ist n Kunden im System im stationären Zustand.

Weiter, lass E_n Darstellen der Häufigkeit, mit der das System in den Zustand eintritt n, und L_n Repräsentieren Sie die Häufigkeit, mit der das System den Zustand verlässt n. Dann für alle n, |E_n − L_n| ∈ {0, 1}. Das heißt, die Häufigkeit, mit der das System einen Zustand verlässtE_n = L_n) oder nicht (|E_n − L_n| = 1).

Wenn das System in einem stationären Zustand eintrifft, sollte die Ankunftsrate der Abfahrtsrate entsprechen.

Somit die Balance -Gleichungen

${\ displayStyle \ mu p_ {1} = \ lambda p_ {0}}$

${\ displayStyle \ lambda p_ {0} +\ mu p_ {2} = (\ lambda +\ mu) p_ {1}}$

${\ displaystyle \ lambda p_ {n-1}+\ mu p_ {n+1} = (\ lambda+\ mu) p_ {n}}$

implizieren

${\ displaystyle p_ {n} = {\ frac {\ lambda} {\ mu}} p_ {n-1}, \ n = 1,2, \ ldots}$

Die Tatsache, dass ${\ displayStyle p_ {0}+p_ {1}+\ cdots = 1}$ führt zum Geometrische Verteilung Formel

${\ displayStyle p_ {n} = (1- \ rho) \ rho ^{n}}$

wo ${\ displaystyle \ rho = {\ frac {\ lambda} {\ mu}} <1.}$

Einfache Zwei-Gleichzeit-Warteschlange

Ein gemeinsames grundlegendes Warteschlangensystem wird zugeschrieben Erlangund ist eine Modifikation von Little's Gesetz. Ankunftsrate λ, eine Abbrecherquote σ, und eine Abfahrtsrate μ, Länge der Warteschlange L ist definiert als:

${\ displayStyle l = {\ frac {\ lambda -\ sigma} {\ mu}}.}$

Annahme einer exponentiellen Verteilung für die Tarife, die Wartezeit W Kann definiert als der Anteil der Ankünfte, die bedient werden. Dies entspricht der exponentiellen Überlebensrate derer, die über die Wartezeit nicht aussteigen, und geben:

${\ displaystyle {\ frac {\ mu} {\ lambda}} = e^{-W {\ mu}}}$

Die zweite Gleichung wird üblicherweise als:

$oder$

Das zweistufige Ein-Box-Modell ist in der Epidemiologie häufig.^[7]

Überblick über die Entwicklung der Theorie

Im Jahr 1909, Agner Krarup ErlangEin dänischer Ingenieur, der für die Kopenhagen -Telefonaustausch arbeitete, veröffentlichte das erste Papier über das, was jetzt als Queuing -Theorie bezeichnet wird.^[8][9][10] Er modellierte die Anzahl der Telefonanrufe, die an einem Austausch von a ankamen Poisson -Prozess und löste die M/D/1 -Warteschlange im Jahr 1917 und M/d/k Warteschlange Modell im Jahr 1920.^[11] In Kendalls Notation:

• M steht für Markov oder Memoryless und bedeutet, dass Ankünfte nach einem Poisson -Prozess auftreten;
• D steht für deterministische und bedeutet Arbeitsplätze, die in der Warteschlange ankommen, die eine feste Menge an Service erfordern.
• k beschreibt die Anzahl der Server am Warteschlangenknoten (k = 1, 2, ...).

Wenn es im Knoten mehr Jobs gibt als Server, werden sich die Jobs anstellen und auf den Service warten

Das M/G/1 -Warteschlange wurde von gelöst von Felix Pollaczek 1930,,^[12] Eine Lösung später in probabilistischer Begriffe nach Aleksandr Khinchin und jetzt bekannt als die Pollaczek–Khinchine formula.^[11][13]

Nach den 1940er Jahren wurde die Warteschlangentheorie für Mathematiker zu einem Bereich des Forschungsinteresses.^[13] 1953 David George Kendall löste den GI/m/k Warteschlange^[14] und stellte die moderne Notation für Warteschlangen ein, die jetzt als bekannt als bekannt als Kendalls Notation. 1957 untersuchte Pollaczek den GI/g/1 mit einem integrale Gleichung.^[15] John Kingman gab eine Formel für die meine Wartezeit in einem G/G/1 -Warteschlange: Kingmans Formel.^[16]

Leonard Kleinrock arbeitete an der Anwendung der Warteschlangentheorie auf Speichervermittlung in den frühen 1960er Jahren und Paketschaltung In den frühen 1970er Jahren. Sein ursprünglicher Beitrag zu diesem Bereich war seine Doktorarbeit am Massachusetts Institute of Technology 1962, veröffentlicht 1964 in Buchform. Seine theoretischen Arbeiten, die in den frühen 1970er Jahren veröffentlicht wurden Arpanet, ein Vorläufer ins Internet.

Das Matrix Geometrische Methode und Matrixanalysemethoden Warteurwettbewerbe mit erlaubt haben Phasentyp verteilt Inter-Arrival- und Servicenzeitverteilungen zu berücksichtigen.^[17]

Systeme mit gekoppelten Umlaufbahnen sind ein wichtiger Bestandteil der Warteschlangentheorie in der Anwendung auf drahtlose Netzwerke und Signalverarbeitung. ^[18]

Probleme wie Leistungsmetriken für die M/g/k Warteschlange ein offenes Problem bleiben.^[11][13]

Service -Disziplinen

Zuerst im ersten Out (FIFO) Warteschlangenbeispiel.

Verschiedene Planungsrichtlinien können an Warteschlangenknoten verwendet werden:

Als Erster rein, als erster raus

Auch genannt Wer zuerst kommt, mahlt zuerst (FCFS),^[19] Dieses Prinzip besagt, dass Kunden nacheinander bedient werden und dass der Kunde, der am längsten wartet, zuerst zugestellt wird.^[20]

Zuletzt rein, zuerst raus

Dieses Prinzip dient den Kunden auch einzeln, aber der Kunde mit dem kürzesten Wartezeit wird zuerst serviert.^[20] Auch bekannt als a Stapel.

Prozessorfreigabe

Die Servicekapazität wird gleichermaßen zwischen Kunden geteilt.^[20]

Priorität

Kunden mit hoher Priorität werden zuerst serviert.^[20] Priority Warteschlangen können zwei Arten sein, nicht vorbeugend (wo ein Dienst im Dienst nicht unterbrochen werden kann) und vorbeugend (wo ein Dienst im Dienst durch einen Job mit höherer Priorität unterbrochen werden kann). In keinem Modell geht es verloren.^[21]

Kürzester Job zuerst

Der nächste Job ist derjenige mit der kleinsten Größe^[22]

Präventiv kürzester Job zuerst

Der nächste Job ist der mit der ursprünglichen kleinsten Größe^[23]

Kürzeste verbleibende Verarbeitungszeit

Der nächste Auftrag ist derjenige mit der kleinsten verbleibenden Verarbeitungsanforderung.^[24]

Serviceeinrichtung

• Single Server: Kunden richten sich und es gibt nur einen Server
• Mehrere parallele Server - Single -Warteschlange: Kunden stimmen auf und es gibt mehrere Server
• Mehrere Server - Severale Warteschlangen: Es gibt viele Zähler und Kunden können sich entscheiden, wohin sich anstellen können

Unzuverlässiger Server

Serverausfälle treten gemäß einem stochastischen Prozess (normalerweise Poisson) auf und folgen von den Setup -Perioden, in denen der Server nicht verfügbar ist. Der unterbrochene Kunde bleibt im Servicebereich, bis der Server festgelegt ist.^[25]

Das Verhalten des Kunden des Wartens

• Kräfte: Kunden, die sich entscheiden, sich nicht der Warteschlange anzuschließen, wenn es zu lang ist
• Jockeying: Kunden wechseln zwischen Warteschlangen, wenn sie glauben, dass sie dabei schneller serviert werden
• Reneging: Kunden verlassen die Warteschlange, wenn sie zu lange auf Service gewartet haben

Die ankommenden Kunden, die nicht bedient werden (entweder aufgrund der Warteschlange ohne Puffer oder aufgrund von Kräfte oder Wiederholungen durch den Kunden) sind auch als Abbrecher bezeichnet, und die durchschnittliche Ausfallrate ist ein signifikanter Parameter, der eine Warteschlange beschreibt.

Warteschlangennetzwerke

Netzwerke von Warteschlangen sind Systeme, in denen eine Reihe von Warteschlangen durch das, was als Kundenrouting bezeichnet wird, verbunden ist. Wenn ein Kunde an einem Knoten bedient wird, kann er einem anderen Knoten und einer Warteschlange für den Dienst beitreten oder das Netzwerk verlassen.

Für Netzwerke von m Knoten kann der Status des Systems von einem beschrieben werden m–Dimensionaler Vektor (x₁, x₂, ..., x_m) wo x_i repräsentiert die Anzahl der Kunden an jedem Knoten.

Das einfachste nicht triviale Netzwerk von Warteschlangen wird genannt Tandem -Warteschlangen.^[26] Die ersten signifikanten Ergebnisse in diesem Bereich waren Jackson -Netzwerke,^[27][28] für die effizient Produkt-Form Stationäre Verteilung existiert und die Mittelwertanalyse^[29] Dadurch können durchschnittliche Metriken wie Durchsatz und Aufenthaltszeiten berechnet werden.^[30] Wenn die Gesamtzahl der Kunden im Netzwerk konstant bleibt, wird das Netzwerk als geschlossenes Netzwerk bezeichnet und hat auch nachgewiesen, dass eine stationäre Verteilung von Produkten in der Gordon -Newell Theorem.^[31] Dieses Ergebnis wurde auf die erweitert BCMP -Netzwerk^[32] Wenn ein Netzwerk mit sehr allgemeiner Servicezeit, Regimen und Kundenrouting auch eine stationäre Produktverteilung aufweist. Das Normalisierung der Konstante kann mit dem berechnet werden Buzens Algorithmus, vorgeschlagen 1973.^[33]

Kundennetze wurden ebenfalls untersucht, Kelly Networks Wenn Kunden unterschiedlicher Klassen an verschiedenen Servicetodes unterschiedliche Prioritätsniveaus haben.^[34] Eine andere Art von Netzwerk sind G-Networks zuerst vorgeschlagen von Erol Gelenbe 1993:^[35] Diese Netzwerke nehmen keine exponentiellen Zeitverteilungen wie das klassische Jackson -Netzwerk an.

Routing -Algorithmen

In diskreten Zeitnetzwerken, in denen eine Einschränkung für Serviceknoten jederzeit aktiv sein kann, wählt der maximale Planungsalgorithmus eine Service-Richtlinie, um einen optimalen Durchsatz zu erzielen, wenn jeder Job nur einen einzelnen Serviceknoten besucht.^[19] In dem allgemeineren Fall, in dem Jobs mehr als einen Knoten besuchen können, Backdruck -Routing gibt einen optimalen Durchsatz. EIN Netzwerkplaner Muss a wählen Warteschlangenalgorithmus, was die Eigenschaften des größeren Netzwerks beeinflusst. Siehe auch Stochastische Planung Weitere Informationen zur Planung von Warteschlangensystemen.

Mittelfeldgrenzen

Mittelfeldmodelle Betrachten Sie das einschränkende Verhalten der empirische Maßnahme (Anteil der Warteschlangen in verschiedenen Zuständen) als Anzahl der Warteschlangen (Warteschlangen (m oben) geht in Unendlichkeit. Die Auswirkungen anderer Warteschlangen auf eine bestimmte Warteschlange im Netzwerk werden durch eine Differentialgleichung angenähert. Das deterministische Modell konvergiert die gleiche stationäre Verteilung wie das ursprüngliche Modell.^[36]

Starke Verkehrs-/Diffusionsnäherungen

In einem System mit hohen Belegungsraten (Auslastung in der Nähe von 1) kann eine starke Verkehrsnäherung verwendet werden reflektierte die Brownsche Bewegung,^[37] Ornstein -Uhlenbeck -Prozess, oder allgemeiner Diffusionsprozess.^[38] Die Anzahl der Dimensionen des Brownschen Prozesses entspricht der Anzahl der Warteschlangenknoten, wobei die Diffusion auf den nicht negativen Begriff beschränkt ist orthant.

Flüssigkeitsgrenzen

Flüssigkeitsmodelle sind kontinuierliche deterministische Analoga von Warteschlangennetzwerken, die durch Einnahme der Grenze beim Skalieren des Prozesses zeitlich und räumlich erhalten werden und heterogene Objekte ermöglichen. Diese skalierte Trajektorie konvergiert zu einer deterministischen Gleichung, die es ermöglicht, die Stabilität des Systems nachgewiesen zu werden. Es ist bekannt, dass ein Warteschlangennetzwerk stabil sein kann, aber eine instabile Flüssigkeitsgrenze aufweist.^[39]

Siehe auch

Verweise

Weitere Lektüre

• Gross, Donald; Carl M. Harris (1998). Grundlagen der Queuing -Theorie. Wiley. ISBN 978-0-471-32812-4. Online
• Zukerman, Moshe (2013). Einführung in die Warteschlangtheorie und stochastische Teletaffic -Modelle (PDF). Arxiv:1307.2968.
• Deitel, Harvey M. (1984) [1982]. Eine Einführung in Betriebssysteme (Revisited First Ed.). Addison-Wesley. p.673. ISBN 978-0-201-14502-1. Kap. 15, S. 380–412
• Gelenbe, Erol; Isi Mitrani (2010). Analyse und Synthese von Computersystemen. World Scientific 2. Ausgabe. ISBN 978-1-908978-42-4.
• Newell, Gordron F. (1. Juni 1971). Anwendungen der Warteschlangentheorie. Chapman und Hall.
• Leonard Kleinrock, Informationsfluss in großen Kommunikationsnetzen, (MIT, Cambridge, 31. Mai 1961) Vorschlag für einen Ph.D. These
• Leonard Kleinrock. Informationsfluss in großen Kommunikationsnetzen (RLE Quarterly Progress Report, Juli 1961)
• Leonard Kleinrock. Kommunikationsnetze: Stochastischer Nachrichtenfluss und Verzögerung (McGraw-Hill, New York, 1964)
• Kleinrock, Leonard (2. Januar 1975). Warteschlangensysteme: Band I - Theorie.New York: Wiley Interscience.pp.417. ISBN 978-0471491101.
• Kleinrock, Leonard (22. April 1976). Warteschlangensysteme: Volume II - Computeranwendungen.New York: Wiley Interscience.pp.576. ISBN 978-0471491118.
• Lazowska, Edward D.;John Zahorjan;G. Scott Graham;Kenneth C. Sevcik (1984). Quantitative Systemleistung: Computersystemanalyse mithilfe von Queuing -Netzwerkmodellen. Prentice-Hall, Inc. ISBN 978-0-13-746975-8.
• Jon Kleinberg;Éva tardos (30. Juni 2013). Algorithmus Design. Pearson. ISBN 978-1-292-02394-6.

Externe Links

• Warteschlangentheorierechner
• Teknomos Queuing -Theorie -Tutorial und Taschenrechner
• Evakuierungssimulation des Bürobrandes an Youtube
• Virtamos Queuing -Theoriekurs
• Myron Hlynkas Queuing -Theorie Seite
• Queuing -Theorie -Grundlagen
• Ein kostenloses Online -Tool zur Lösung einiger klassischer Warteschlangensysteme
• JMT: Eine grafische Open -Source -Umgebung für die Warteschlangenentheorie
• Linie: Ein allgemeiner Motor zur Lösung von Warteschlangenmodellen
• Was Sie am meisten hassen, um in der Schlange zu warten: (Es ist nicht die Länge des Wartens.), von Seth Stevenson, Schiefer, 2012 - Bevölkerung Einführung