Analytische Modelle von Warteschlangensystemen. wobei t der gesamte Zeitraum ist, in dem die Wirkung des Ereignisflusses berücksichtigt wird. Jede Untersuchung eines Warteschlangensystems beginnt daher mit der Untersuchung dessen, was bedient werden muss

In der Praxis menschlichen Handelns nehmen Warteschlangenprozesse einen großen Platz ein, die in Systemen entstehen, die zur wiederverwendbaren Verwendung bei der Lösung ähnlicher Probleme vorgesehen sind. Solche Systeme werden Warteschlangensysteme (QS) genannt. Beispiele für solche Systeme sind Telefonsysteme, Computersysteme, Kraftverkehr, Luftfahrt, Reparaturdienstsysteme, Geschäfte, Fahrkartenschalter usw.

Jedes System besteht aus einer bestimmten Anzahl von Serviceeinheiten (Instrumente, Geräte, Geräte, Punkte, Stationen), die als Servicekanäle bezeichnet werden. Basierend auf der Anzahl der Kanäle werden QS-Systeme in Einkanal- und Mehrkanalsysteme unterteilt eines einkanaligen Warteschlangensystems ist in Abb. 6.2 dargestellt.

Bewerbungen an das System treffen in der Regel nicht regelmäßig, sondern zufällig ein und bilden einen zufälligen Fluss von Bewerbungen (Anforderungen). Die Bearbeitung jeder Anfrage selbst kann entweder eine bestimmte Zeitspanne oder, was häufiger vorkommt, eine unbestimmte Zeitspanne in Anspruch nehmen. Die Zufälligkeit führt dazu, dass das QS ungleichmäßig ausgelastet ist: In manchen Zeiträumen häufen sich sehr viele Bewerbungen an (entweder geraten sie in die Warteschlange oder lassen das QS unversorgt), während das QS in anderen Zeiträumen mit Unterlast arbeitet oder im Leerlauf ist .

Reis. 6.2.

Der Zweck der Untersuchung von Warteschlangensystemen besteht darin, die Qualität ihrer Funktionsweise zu analysieren und Möglichkeiten für ihre Verbesserung zu identifizieren. Darüber hinaus wird der Begriff „Funktionsqualität“ im Einzelfall eine eigene spezifische Bedeutung haben und in verschiedenen quantitativen Indikatoren zum Ausdruck kommen. Zum Beispiel quantitative Indikatoren wie die Größe der Warteschlange für den Service, die durchschnittliche Servicezeit, das Warten auf den Service oder das Finden einer Anfrage im Servicesystem, Ausfallzeiten von Servicegeräten; Vertrauen, dass alle vom System empfangenen Anfragen bearbeitet werden.

Unter der Funktionsqualität eines Warteschlangensystems wird daher nicht die tatsächliche Qualität der Ausführung einer bestimmten Aufgabe verstanden, für die eine Anfrage eingegangen ist, sondern der Grad der Befriedigung des Servicebedarfs.

Gegenstand der Warteschlangentheorie ist die Konstruktion mathematischer Modelle, die die gegebenen Betriebsbedingungen des QS (Anzahl der Kanäle, deren Produktivität, Art des Anforderungsflusses etc.) mit Leistungsindikatoren des QS verbinden und seine Leistungsfähigkeit beschreiben um den Strom der Anfragen zu bewältigen.

Klassifizierung von Warteschlangensystemen

Das erste Merkmal, das es uns ermöglicht, Warteschlangenaufgaben zu klassifizieren, ist das Verhalten von Anfragen, die das Wartungssystem zu einem Zeitpunkt erhält, an dem alle Maschinen beschäftigt sind.

In manchen Fällen kann eine Anfrage, die das System zu einem Zeitpunkt erreicht, an dem alle Geräte beschäftigt sind, nicht auf deren Freigabe warten und das System unbeantwortet lassen, d. h. Die Anforderung geht für ein bestimmtes Serviersystem verloren. Solche Wartungssysteme werden als Systeme mit Verlusten bezeichnet, und die darauf basierend formulierten Probleme werden als Wartungsprobleme für Systeme mit Verlusten bezeichnet.

Wenn eine Anforderung, nachdem sie in das System gelangt ist, in eine Warteschlange gelangt und darauf wartet, dass das Gerät verfügbar wird, werden solche Systeme als Systeme mit Wartezeit bezeichnet, und die entsprechenden Aufgaben werden in Systemen mit Wartezeit als Wartungsaufgaben bezeichnet. QS mit Warten wird je nach Organisation der Warteschlange in verschiedene Typen unterteilt: mit begrenzter oder unbegrenzter Warteschlangenlänge, mit begrenzter Wartezeit usw.

QS unterscheiden sich auch in der Anzahl der Anforderungen, die gleichzeitig im Servicesystem vorhanden sein können. Highlight:

• 1) Systeme mit einem begrenzten Anforderungsfluss;
• 2) Systeme mit unbegrenztem Anforderungsfluss.

Abhängig von den Formen der internen Leistungsorganisation im System werden unterschieden:

• 1) Systeme mit angeordneter Wartung;
• 2) Systeme mit gestörtem Dienst.

Ein wichtiger Schritt bei der Untersuchung von QS ist die Auswahl von Kriterien, die den untersuchten Prozess charakterisieren. Die Wahl hängt von der Art der untersuchten Probleme und dem mit der Lösung verfolgten Ziel ab.

In der Praxis gibt es am häufigsten Systeme, in denen der Anforderungsfluss nahezu am einfachsten ist und die Servicezeit einem exponentiellen Verteilungsgesetz folgt. Diese Systeme sind in der Warteschlangentheorie am weitesten entwickelt.

Typische Aufgaben in einer Unternehmensumgebung sind Wartezeiten, eine begrenzte Anzahl von Servern, ein begrenzter Anforderungsfluss und ein ungeordneter Service.

Eine große Klasse von Systemen, die mit analytischen Methoden schwer zu untersuchen sind, die aber mit statistischen Modellierungsmethoden gut untersucht werden können, sind Warteschlangensysteme (QS).

Das QS impliziert, dass dies der Fall ist typische Wege(Dienstkanäle), die sie während des Verarbeitungsprozesses durchlaufen Anwendungen. Es wird allgemein gesagt, dass Anwendungen serviert Kanäle. Kanäle können unterschiedlichen Zweck und Eigenschaften haben und in verschiedenen Kombinationen kombiniert werden. Anwendungen befinden sich möglicherweise in Warteschlangen und warten auf die Bearbeitung. Einige Anwendungen werden möglicherweise von Kanälen bedient, während andere dies möglicherweise ablehnen. Wichtig ist, dass Anfragen aus Sicht des Systems abstrakt sind: Es handelt sich um etwas, das bedient werden möchte, also einen bestimmten Weg im System gehen möchte. Kanäle sind ebenfalls eine Abstraktion: Sie bedienen Anfragen.

Anfragen können ungleichmäßig eingehen, Kanäle können unterschiedliche Anfragen zu unterschiedlichen Zeiten bearbeiten usw. Die Anzahl der Anfragen ist immer sehr groß. All dies macht es schwierig, solche Systeme zu untersuchen und zu verwalten, und es ist nicht möglich, alle Ursache-Wirkungs-Beziehungen in ihnen zu verfolgen. Daher ist es allgemein anerkannt, dass die Wartung in komplexen Systemen zufällig erfolgt.

Beispiele für CMOs (siehe Tabelle 30.1) sind: Buslinien- und Personenbeförderung; Produktionsförderer zur Bearbeitung von Teilen; ein Geschwader von Flugzeugen, die in fremdes Territorium fliegen und von Flugabwehrgeschützen „bedient“ werden; der Lauf und das Horn des Maschinengewehrs, die den Patronen „bedienen“; elektrische Ladungen, die sich in einem Gerät bewegen usw.

Aber alle diese Systeme werden in einer QS-Klasse zusammengefasst, da der Ansatz zu ihrer Untersuchung derselbe ist. Es besteht darin, dass zunächst mit Hilfe eines Zufallszahlengenerators Zufallszahlen gezogen werden, die die ZUFÄLLIGEN Zeitpunkte des Erscheinens von Befehlen und den Zeitpunkt ihrer Zustellung in den Kanälen simulieren. Aber zusammengenommen sind diese Zufallszahlen natürlich untergeordnet statistisch Muster.

Man kann zum Beispiel sagen: „Im Durchschnitt treffen die Bewerbungen in einer Menge von 5 Stück pro Stunde ein.“ Das bedeutet, dass die Zeiten zwischen dem Eintreffen zweier benachbarter Anfragen zufällig sind, zum Beispiel: 0,1; 0,3; 0,1; 0,4; 0,2, wie in Abb. 30,1, aber insgesamt ergeben sie einen Durchschnitt von 1 (beachten Sie, dass dies im Beispiel nicht genau 1, sondern 1,1 ist – aber zu einer anderen Stunde kann diese Summe beispielsweise 0,9 betragen); und nur schon ziemlich lange Der Durchschnitt dieser Zahlen wird bei etwa einer Stunde liegen.

Das Ergebnis (z. B. Systemdurchsatz) wird natürlich auch in einzelnen Zeitintervallen eine Zufallsvariable sein. Über einen längeren Zeitraum gemessen wird dieser Wert aber im Mittel der exakten Lösung entsprechen. Das heißt, zur Charakterisierung des QS sind sie an Antworten im statistischen Sinne interessiert.

Das System wird also mit zufälligen Eingangssignalen getestet, die einem bestimmten statistischen Gesetz unterliegen, und das Ergebnis sind statistische Indikatoren, die über den Betrachtungszeitraum oder über die Anzahl der Experimente gemittelt werden. Zuvor, in Vorträge 21(cm. Reis. 21.1) haben wir bereits ein Schema für ein solches statistisches Experiment entwickelt (siehe Abb. 30.2).

Zweitens werden alle QS-Modelle standardmäßig aus einem kleinen Satz von Elementen (Kanal, Anforderungsquelle, Warteschlange, Anforderung, Servicedisziplin, Stapel, Ring usw.) zusammengestellt, wodurch Sie diese Aufgaben simulieren können typisch Weg. Dazu wird aus einem Konstruktor solcher Elemente ein Systemmodell zusammengesetzt. Es spielt keine Rolle, welches spezifische System untersucht wird. Es ist wichtig, dass das Systemdiagramm aus denselben Elementen zusammengesetzt ist. Natürlich wird der Aufbau der Schaltung immer unterschiedlich sein.

Lassen Sie uns einige Grundkonzepte von QS auflisten.

Kanäle sind das, was dient; Es gibt „heiß“ (sie beginnen mit der Bearbeitung einer Anfrage, sobald sie in den Kanal gelangt) und „kalt“ (der Kanal benötigt Zeit zur Vorbereitung, bevor mit der Bearbeitung begonnen wird). Auftragsquellen – Generieren Sie Aufträge zu zufälligen Zeiten gemäß einem vom Benutzer festgelegten statistischen Gesetz. Anwendungen, auch Clients genannt, gelangen in das System (von Anwendungsquellen generiert), durchlaufen seine Elemente (werden bedient) und verlassen es bedient oder unzufrieden. Es gibt ungeduldige Bewerbungen – diejenigen, die es satt haben zu warten oder im System zu sein und die den CMO aus freien Stücken verlassen. Bewerbungen bilden Flüsse – einen Fluss von Bewerbungen am Systemeingang, einen Fluss von bearbeiteten Bewerbungen, einen Fluss von abgelehnten Bewerbungen. Ein Fluss wird durch die Anzahl der Anwendungen einer bestimmten Art charakterisiert, die an einem bestimmten Ort des QS pro Zeiteinheit (Stunde, Tag, Monat) beobachtet werden, d. h. der Fluss ist eine statistische Größe.

Warteschlangen werden durch die Warteschlangenregeln (Servicedisziplin), die Anzahl der Plätze in der Warteschlange (die maximale Anzahl von Clients, die sich in der Warteschlange befinden können) und die Struktur der Warteschlange (die Beziehung zwischen den Plätzen in der Warteschlange) charakterisiert. Es gibt begrenzte und unbegrenzte Warteschlangen. Lassen Sie uns die wichtigsten Wartungsdisziplinen auflisten. FIFO (First In, First Out – First In, First Out): Wenn die Anfrage als Erste in der Warteschlange ankommt, wird sie als Erste zur Bearbeitung weitergeleitet. LIFO (Last In, First Out – zuletzt rein, zuerst raus): Wenn die Anfrage als letzte in der Warteschlange ankam, wird sie als erste zur Wartung weitergeleitet (Beispiel: Patronen im Horn eines Maschinengewehrs). SF (Short Forward): Die Anfragen aus der Warteschlange, die eine kürzere Bearbeitungszeit haben, werden zuerst bearbeitet.

Lassen Sie uns ein eindrucksvolles Beispiel geben, das zeigt, wie Sie durch die richtige Wahl der einen oder anderen Servicedisziplin erhebliche Zeiteinsparungen erzielen können.

Lass es zwei Geschäfte geben. In der Filiale Nr. 1 erfolgt der Service nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“, d. h. hier wird die FIFO-Servicedisziplin umgesetzt (siehe Abb. 30.3).

Servicezeit T Service in Abb. 30.3 zeigt, wie viel Zeit der Verkäufer für die Betreuung eines Käufers aufwenden wird. Es ist klar, dass der Verkäufer beim Kauf eines Stückprodukts weniger Zeit für den Service aufwendet als beispielsweise beim Kauf von Massenprodukten, die zusätzliche Manipulationen erfordern (Kommissionierung, Wiegen, Preisberechnung usw.). Wartezeit T erwartet zeigt an, wie lange es dauert, bis der nächste Käufer vom Verkäufer bedient wird.

Im Geschäft Nr. 2 ist die SF-Disziplin implementiert (siehe Abb. 30.4), was bedeutet, dass Stückgüter seit der Servicezeit außerhalb der Reihe gekauft werden können T Service Ein solcher Kauf ist klein.

Wie aus beiden Abbildungen ersichtlich ist, wird der letzte (fünfte) Käufer ein Stückprodukt kaufen, daher ist seine Servicezeit kurz – 0,5 Minuten. Wenn dieser Kunde in die Filiale Nr. 1 kommt, muss er ganze 8 Minuten in der Schlange stehen, während er in der Filiale Nr. 2 sofort außerhalb der Warteschlange bedient wird. Somit beträgt die durchschnittliche Servicezeit für jeden Kunden in einem Geschäft mit einer FIFO-Servicedisziplin 4 Minuten und in einem Geschäft mit einer HF-Servicedisziplin nur 2,8 Minuten. Und der soziale Nutzen und die Zeitersparnis betragen: (1 – 2,8/4) · 100 % = 30 Prozent! Also 30 % Zeitersparnis für die Gesellschaft – und das liegt nur an der richtigen Wahl der Servicedisziplin.

Der Systemspezialist muss über ein umfassendes Verständnis der Leistungs- und Effizienzressourcen der von ihm entworfenen Systeme verfügen, die in der Optimierung von Parametern, Strukturen und Wartungsdisziplinen verborgen sind. Die Modellierung hilft, diese stillen Reserven zu identifizieren.

Bei der Analyse der Modellierungsergebnisse ist es auch wichtig, Interessen und deren Erfüllungsgrad aufzuzeigen. Dabei wird zwischen den Interessen des Auftraggebers und den Interessen des Anlagenbetreibers unterschieden. Beachten Sie, dass diese Interessen nicht immer übereinstimmen.

Die Leistung des QS kann anhand von Indikatoren beurteilt werden. Die beliebtesten davon:

Wahrscheinlichkeit der Kundenbetreuung durch das System;

Systemdurchsatz;

die Wahrscheinlichkeit, dass einem Kunden der Service verweigert wird;

Nutzungswahrscheinlichkeit jedes Kanals und aller zusammen;

durchschnittliche Belegungszeit jedes Kanals;

Belegungswahrscheinlichkeit aller Kanäle;

durchschnittliche Anzahl belegter Kanäle;

Ausfallwahrscheinlichkeit jedes Kanals;

die Wahrscheinlichkeit eines Ausfalls des gesamten Systems;

die durchschnittliche Anzahl der Bewerbungen in der Warteschlange;

durchschnittliche Wartezeit für eine Bewerbung in der Warteschlange;

durchschnittliche Zeit für die Bearbeitung einer Anwendung;

durchschnittliche Verweildauer einer Anwendung im System.

Die Qualität des resultierenden Systems muss anhand der Gesamtheit der Indikatorwerte beurteilt werden. Bei der Analyse von Modellierungsergebnissen (Indikatoren) ist es auch wichtig, auf die Interessen des Kunden und die Interessen des Systembesitzers zu achten, d. h. der eine oder andere Indikator muss minimiert oder maximiert werden, sowie der Grad ihrer Umsetzung . Beachten Sie, dass die Interessen des Kunden und des Eigentümers meist nicht oder nicht immer übereinstimmen. Wir werden die Indikatoren unten bezeichnen H = { H 1 , H 2 , …} .

Die Parameter des QS können sein: die Intensität des Anfrageflusses, die Intensität des Serviceflusses, die durchschnittliche Zeit, während der eine Anfrage bereit ist, in der Warteschlange auf den Service zu warten, die Anzahl der Servicekanäle, Servicedisziplin usw bald. Parameter beeinflussen die Leistung des Systems. Wir werden die Parameter unten als bezeichnen R = { R 1 , R 2 , …} .

Beispiel. Tankstelle (Tankstelle).

1. Darstellung des Problems. In Abb. Abbildung 30.5 zeigt den Aufbau der Tankstelle. Betrachten wir die Methode zur Modellierung eines QS anhand seines Beispiels und den Plan für seine Forschung. Autofahrer, die unterwegs an Tankstellen vorbeikommen, möchten möglicherweise ihr Fahrzeug auftanken. Nicht alle Autofahrer möchten einen Service in Anspruch nehmen (ihr Auto volltanken); Nehmen wir an, dass aus dem gesamten Autostrom durchschnittlich 5 Autos pro Stunde an der Tankstelle ankommen.

An einer Tankstelle gibt es zwei identische Säulen, deren statistische Leistung jeweils bekannt ist. Die erste Säule bedient durchschnittlich 1 Auto pro Stunde, die zweite durchschnittlich 3 Autos pro Stunde. Der Besitzer der Tankstelle hat einen Platz für Autos geschaffen, wo sie auf den Service warten können. Wenn die Zapfsäulen besetzt sind, können an dieser Stelle weitere Autos auf den Service warten, jedoch nicht mehr als zwei gleichzeitig. Wir betrachten die Warteschlange als allgemein. Sobald eine der Kolonnen frei ist, kann das erste Auto in der Warteschlange seinen Platz auf der Kolonne einnehmen (während das zweite Auto auf den ersten Platz in der Warteschlange rückt). Wenn ein drittes Auto auftaucht und alle Plätze (es sind zwei davon) in der Warteschlange belegt sind, wird ihm die Bedienung verweigert, da das Stehen auf der Straße verboten ist (siehe Verkehrsschilder in der Nähe der Tankstelle). Ein solches Auto verlässt das System für immer und ist als potenzieller Kunde für den Tankstellenbesitzer verloren. Sie können die Aufgabe erschweren, indem Sie die Registrierkasse (einen weiteren Servicekanal, zu dem Sie nach der Wartung in einer der Spalten gelangen müssen) und die Warteschlange daran usw. berücksichtigen. Aber in der einfachsten Version ist es offensichtlich, dass die Flusswege von Anwendungen durch das QS in Form eines äquivalenten Diagramms dargestellt werden können, und indem wir die Werte und Bezeichnungen der Merkmale jedes Elements des QS hinzufügen, haben wir schließlich Erhalten Sie das in Abb. gezeigte Diagramm. 30.6.

2. SMO-Forschungsmethode. In unserem Beispiel wenden wir das Prinzip der sequentiellen Buchung von Bestellungen an (Einzelheiten zu den Prinzipien der Modellierung finden Sie unter Vorlesung 32). Die Idee besteht darin, dass eine Anwendung das gesamte System vom Eingang bis zum Ausgang durchläuft und erst danach die nächste Anwendung modelliert wird.

Zur Verdeutlichung erstellen wir ein Zeitdiagramm des QS-Betriebs und reflektieren es auf jeder Linie (Zeitachse). T) der Zustand eines einzelnen Elements des Systems. Es gibt so viele Zeitlinien, wie es unterschiedliche Stellen im QS und in den Flüssen gibt. In unserem Beispiel gibt es 7 davon (einen Anforderungsfluss, einen an erster Stelle in der Warteschlange wartenden Fluss, einen an zweiter Stelle in der Warteschlange wartenden Fluss, einen Dienstfluss in Kanal 1, einen Dienstfluss in Kanal 2 , ein Fluss von Bewerbungen, die vom System bearbeitet werden, ein Fluss von abgelehnten Bewerbungen).

Um die Ankunftszeit von Anfragen zu generieren, verwenden wir die Formel zur Berechnung des Intervalls zwischen den Ankunftszeiten zweier zufälliger Ereignisse (siehe. Vorlesung 28):

In dieser Formel ist der Durchflusswert λ muss angegeben werden (zuvor muss er experimentell in der Anlage als statistischer Mittelwert ermittelt werden), R- zufällige, gleichmäßig verteilte Zahl von 0 bis 1 von RNG oder Tische, bei dem Zufallszahlen hintereinander genommen werden müssen (ohne besondere Auswahl).

Aufgabe. Generieren Sie einen Stream aus 10 zufälligen Ereignissen mit einer Ereignisrate von 5 Stück/Stunde.

Das Problem lösen. Nehmen wir gleichmäßig verteilte Zufallszahlen im Bereich von 0 bis 1 (siehe. Tisch) und berechnen Sie deren natürlichen Logarithmus (siehe Tabelle 30.2).

Die Poisson-Flussformel bestimmt den Abstand zwischen zwei zufälligen Ereignissen wie folgt: T= –Ln(r ðð)/ λ . Dann, wenn man das bedenkt λ = 5, wir haben Abstände zwischen zwei zufälligen benachbarten Ereignissen: 0,68, 0,21, 0,31, 0,12 Stunden. Das heißt, Ereignisse treten auf: zuerst – im Moment der Zeit T= 0, die Sekunde - im Moment der Zeit T= 0,68, Drittel - zum Zeitpunkt der Zeit T= 0,89, vierter - im Moment der Zeit T= 1,20, Fünftel - zum Zeitpunkt der Zeit T= 1,32 und so weiter. Ereignisse – der Eingang von Bestellungen wird in der ersten Zeile angezeigt (siehe Abb. 30.7).

Die erste Anfrage wird angenommen und da in diesem Moment die Kanäle frei sind, wird sie auf die Bedienung des ersten Kanals eingestellt. Anwendung 1 wird auf die Leitung „1 Kanal“ übertragen.

Die Servicezeit im Kanal ist ebenfalls zufällig und wird nach einer ähnlichen Formel berechnet:

Dabei spielt die Größe des Serviceflusses eine Rolle bei der Intensität μ 1 oder μ 2, abhängig davon, welcher Kanal die Anfrage bedient. Wir finden im Diagramm den Zeitpunkt des Endes des Dienstes, verschieben die generierte Dienstzeit ab dem Zeitpunkt, an dem der Dienst beginnt, und senken die Anfrage in die Zeile „Serviert“.

Der Antrag ging bis zum CMO. Nach dem Prinzip der sequentiellen Buchung von Aufträgen ist es nun auch möglich, den Weg des zweiten Auftrags zu simulieren.

Sollte sich irgendwann herausstellen, dass beide Kanäle belegt sind, dann sollte die Anfrage in eine Warteschlange gestellt werden. In Abb. 30.7 ist eine Anfrage mit der Nummer 3. Beachten Sie, dass Anfragen je nach den Bedingungen des Problems im Gegensatz zu Kanälen nicht für eine zufällige Zeit in der Warteschlange stehen, sondern darauf warten, dass einer der Kanäle frei wird. Nach Freigabe des Kanals wird die Anfrage an die Leitung des entsprechenden Kanals gestellt und dort die Bearbeitung organisiert.

Wenn zum Zeitpunkt des Eintreffens der nächsten Bewerbung alle Plätze in der Warteschlange belegt sind, sollte die Bewerbung an die Zeile „Abgelehnt“ weitergeleitet werden. In Abb. 30.7 ist Antragsnummer 6.

Das Verfahren zur Simulation der Anwendungswartung dauert noch einige Beobachtungszeit. T N. Je länger diese Zeit ist, desto genauer werden die Simulationsergebnisse in Zukunft sein. In Wirklichkeit entscheiden sie sich für einfache Systeme T n, entspricht 50-100 oder mehr Stunden, obwohl es manchmal besser ist, diesen Wert anhand der Anzahl der überprüften Bewerbungen zu messen.

In vielen Bereichen der Wirtschaft, des Finanzwesens, der Produktion und des Alltags spielen Systeme, die die wiederholte Ausführung ähnlicher Aufgaben realisieren, eine wichtige Rolle. Solche Systeme heißen Warteschlangensysteme ( SMO ). Beispiele für QS sind: Banken verschiedener Art, Versicherungsorganisationen, Steueraufsichtsämter, Prüfungsdienste, verschiedene Kommunikationssysteme, Be- und Entladekomplexe, Tankstellen, verschiedene Unternehmen und Dienstleistungsorganisationen.

3.1.1 Allgemeine Informationen zu Warteschlangensystemen

Jedes QS ist darauf ausgelegt, einen bestimmten Fluss von Anwendungen (Anforderungen) zu bedienen (zu erfüllen), die meist nicht regelmäßig, sondern zu zufälligen Zeiten am Eingang des Systems eingehen. Die Bearbeitung von Bewerbungen erfolgt auch nicht über eine konstante, vorher festgelegte Zeit, sondern über eine zufällige Zeit, die von vielen zufälligen, manchmal uns unbekannten Gründen abhängt. Nach Bearbeitung der Anfrage ist der Kanal freigegeben und bereit für den Empfang der nächsten Anfrage. Die Zufälligkeit des Antragsflusses und der Zeitpunkt ihrer Bearbeitung führt zu einer ungleichmäßigen Auslastung des QS. In manchen Zeitintervallen kann es zu einer Anhäufung von Anfragen am Eingang des QS kommen, was zu einer Überlastung des QS führt; in manchen anderen Zeitintervallen sind am Eingang des QS keine freien Kanäle (Servicegeräte) vorhanden Anfragen, was zu einer Unterauslastung des QS führt, d.h. zum Stillstand seiner Kanäle. Bewerbungen, die sich am Eingang des QS ansammeln, „reihen“ sich entweder in die Warteschlange ein oder können aus irgendeinem Grund nicht weiter in der Warteschlange bleiben, sondern verlassen das QS unbearbeitet.

Abbildung 3.1 zeigt das QS-Diagramm.

Die Hauptelemente (Merkmale) von Warteschlangensystemen sind:

Serviceeinheit (Block),

Ablauf der Bewerbungen

Warteschlange beim Warten auf den Service (Warteschlangendisziplin).

Serviceeinheit Entwickelt, um Aktionen gemäß den Anforderungen derjenigen durchzuführen, die das System betreten Anwendungen.

Reis. 3.1 Diagramm des Warteschlangensystems

Die zweite Komponente von Warteschlangensystemen ist die Eingabe Fluss der Bewerbungen. Bewerbungen werden nach dem Zufallsprinzip in das System eingegeben. Normalerweise wird davon ausgegangen, dass der Eingabefluss für die Dauer der Intervalle zwischen zwei nacheinander eintreffenden Anforderungen einem Wahrscheinlichkeitsgesetz gehorcht, und es wird angenommen, dass das Verteilungsgesetz über einen längeren Zeitraum unverändert bleibt. Die Zahl der Bewerbungen ist unbegrenzt.

Die dritte Komponente ist Warteschlangendisziplin. Dieses Merkmal beschreibt die Reihenfolge der am Systemeingang eintreffenden Serviceanfragen. Da der Wartungsblock in der Regel über eine begrenzte Kapazität verfügt und Anwendungen unregelmäßig eintreffen, wird regelmäßig eine Warteschlange mit Anwendungen erstellt, die auf den Dienst warten, und manchmal ist das Wartungssystem inaktiv und wartet auf Anwendungen.

Das Hauptmerkmal von Warteschlangenprozessen ist die Zufälligkeit. In diesem Fall gibt es zwei interagierende Parteien: den Bedienten und den Servierenden. Das zufällige Verhalten mindestens einer der Parteien führt zur Zufälligkeit des gesamten Serviceprozesses. Die Quellen der Zufälligkeit in der Interaktion dieser beiden Parteien sind zufällige Ereignisse zweier Art.

1. Erscheinen eines Antrags (Anforderung) für die Zustellung. Der Grund für die Zufälligkeit dieses Ereignisses ist oft die enorme Art des Servicebedarfs.

2. Ende der Wartung der nächsten Anwendung. Die Gründe für die Zufälligkeit dieses Ereignisses liegen sowohl in der Zufälligkeit des Beginns des Dienstes als auch in der zufälligen Dauer des Dienstes selbst.

Diese zufälligen Ereignisse bilden ein System aus zwei Flüssen im QS: dem Eingabefluss von Serviceanträgen und dem Ausgabefluss von betreuten Anwendungen.

Das Ergebnis des Zusammenwirkens dieser Ströme zufälliger Ereignisse ist die Anzahl der aktuell im QS befindlichen Bewerbungen, die üblicherweise aufgerufen werden Zustand des Systems.

Jedes QS verfügt abhängig von seinen Parametern der Art des Bewerbungsflusses, der Anzahl der Servicekanäle und deren Produktivität sowie den Regeln der Arbeitsorganisation über eine bestimmte Betriebseffizienz (Durchsatz), die es ihm ermöglicht, den Bewerbungsfluss erfolgreich zu bewältigen Anwendungen.

Spezialgebiet der angewandten Mathematik MassentheorieWartung (TMO)– befasst sich mit der Prozessanalyse in Warteschlangensystemen. Gegenstand des Studiums der Warteschlangentheorie ist QS.

Ziel der Warteschlangentheorie ist es, Empfehlungen für den rationellen Aufbau von QS, die rationelle Organisation ihrer Arbeit und die Regulierung des Anfrageflusses zu entwickeln, um eine hohe Effizienz von QS zu gewährleisten. Um dieses Ziel zu erreichen, werden die Aufgaben der Warteschlangentheorie gestellt, die darin bestehen, die Abhängigkeiten der Wirksamkeit der Funktionsweise des QS von seiner Organisation festzustellen.

Die Probleme der Warteschlangentheorie haben Optimierungscharakter und zielen letztlich darauf ab, eine Version des Systems zu ermitteln, die ein Minimum an Gesamtkosten durch Warten auf den Service, Zeit- und Ressourcenverlust für den Service sowie durch Ausfallzeiten der Serviceeinheit gewährleistet. Die Kenntnis solcher Merkmale liefert dem Manager Informationen, um gezielt Einfluss auf diese Merkmale zu nehmen und so die Effizienz von Warteschlangenprozessen zu steuern.

Als Merkmale der Wirksamkeit des QS-Systems werden üblicherweise die folgenden drei Hauptgruppen von (meist durchschnittlichen) Indikatoren ausgewählt:

Indikatoren für die Wirksamkeit des QS-Einsatzes:

Die absolute Kapazität des QS ist die durchschnittliche Anzahl der Anfragen, die der QS pro Zeiteinheit bedienen kann.

Die relative Kapazität des QS ist das Verhältnis der durchschnittlichen Anzahl der vom QS pro Zeiteinheit bearbeiteten Anträge zur durchschnittlichen Anzahl der im gleichen Zeitraum eingegangenen Anträge.

Durchschnittliche Dauer der Beschäftigungsdauer des CMO.

Die QS-Auslastung ist der durchschnittliche Zeitanteil, in dem der QS mit der Bearbeitung von Anfragen usw. beschäftigt ist.

Qualitätsindikatoren für Serviceanfragen:

Durchschnittliche Wartezeit für eine Bewerbung in der Warteschlange.

Durchschnittliche Verweildauer einer Bewerbung im CMO.

Die Wahrscheinlichkeit, dass einer Anfrage die Bearbeitung ohne Wartezeit verweigert wird.

Die Wahrscheinlichkeit, dass ein eingegangener Antrag sofort zur Zustellung angenommen wird.

Das Gesetz der Verteilung der Zeit, die eine Bewerbung in der Warteschlange bleibt.

Das Gesetz der Verteilung der Verweildauer einer Bewerbung im QS.

Die durchschnittliche Anzahl der Bewerbungen in der Warteschlange.

Durchschnittliche Anzahl der Bewerbungen im CMO usw.

Indikatoren für die Wirksamkeit des Paares „SMO – Verbraucher“, wobei unter „Verbraucher“ die gesamte Reihe von Anwendungen oder einige davon verstanden werden

Zeichnung 0 - 2 Ereignisflüsse (a) und der einfachste Fluss (b)

10.5.2.1. Stationarität

Die Strömung wird als stationär bezeichnet , wenn die Wahrscheinlichkeit, dass eine bestimmte Anzahl von Ereignissen in einem elementaren Zeitraum auftritt Länge τ (

Abbildung 0-2 , A) hängt nur von der Länge des Abschnitts ab und nicht davon, wo genau auf der Achse T Dieser Bereich befindet sich.

Unter stationärer Strömung versteht man ihre Gleichmäßigkeit über die Zeit; Die Wahrscheinlichkeitseigenschaften eines solchen Flusses ändern sich nicht mit der Zeit. Insbesondere muss die sogenannte Intensität (oder „Dichte“) des Ereignisflusses – die durchschnittliche Anzahl von Ereignissen pro Zeiteinheit bei einem stationären Fluss – konstant bleiben. Dies bedeutet natürlich nicht, dass die tatsächliche Anzahl der pro Zeiteinheit auftretenden Ereignisse konstant ist; der Fluss kann lokale Verdichtungen und Verdünnungen aufweisen. Wichtig ist, dass diese Kondensationen und Verdünnungen bei einer stationären Strömung nicht regelmäßiger Natur sind und die durchschnittliche Anzahl der innerhalb eines Zeitraums auftretenden Ereignisse über den gesamten betrachteten Zeitraum konstant bleibt.

In der Praxis kommt es häufig zu Ereignisströmen, die (zumindest für einen begrenzten Zeitraum) als stationär betrachtet werden können. Beispielsweise kann eine Reihe von Anrufen, die beispielsweise zwischen 12 und 13 Stunden bei einer Telefonzentrale eingehen, als Festnetzanrufe betrachtet werden. Der gleiche Fluss wird nicht mehr einen ganzen Tag lang stationär sein (nachts ist die Intensität des Anrufflusses viel geringer als tagsüber). Beachten Sie, dass das Gleiche bei den meisten physikalischen Prozessen der Fall ist, die wir in Wirklichkeit als „stationär“ bezeichnen. Sie sind nur über einen begrenzten Zeitraum stationär und die Erweiterung dieses Bereichs bis ins Unendliche ist nur eine praktische Technik, die zu diesem Zweck verwendet wird der Vereinfachung.

10.5.2.2. Keine Nachwirkung

Ein Strom von Ereignissen wird als Strom ohne Nachwirkung bezeichnet , Wenn für alle nicht überlappenden Zeiträume die Anzahl der Ereignisse, die auf einen von ihnen fallen, nicht davon abhängt, wie viele Ereignisse auf den anderen fallen (oder auf andere, wenn mehr als zwei Abschnitte berücksichtigt werden).

In solchen Strömen treten die Ereignisse, die den Strom bilden, unabhängig voneinander zu aufeinanderfolgenden Zeitpunkten auf. Beispielsweise kann der Zustrom von Passagieren, die eine U-Bahn-Station betreten, als ein Fluss ohne Nachwirkungen betrachtet werden, da die Gründe, die die Ankunft eines einzelnen Passagiers zu einem bestimmten Zeitpunkt und nicht zu einem anderen Zeitpunkt bestimmt haben, in der Regel nicht mit ähnlichen Gründen zusammenhängen andere Passagiere. Tritt eine solche Abhängigkeit auf, ist die Bedingung der Nachwirkungsfreiheit verletzt.

Stellen Sie sich zum Beispiel den Verkehr von Güterzügen entlang einer Eisenbahnstrecke vor. Wenn sie aus Sicherheitsgründen nicht häufiger als in Abständen aufeinander folgen können t 0 , dann besteht eine Abhängigkeit zwischen den Ereignissen im Fluss und die Bedingung der Abwesenheit von Nachwirkung ist verletzt. Wenn jedoch das Intervall t 0 im Vergleich zum durchschnittlichen Abstand zwischen den Zügen klein ist, ist ein solcher Verstoß nicht erheblich.

Zeichnung 0 - 3 Poisson-Verteilung

Betrachten Sie die Achse T der einfachste Ereignisstrom mit der Intensität λ. (Abbildung 0-2 b) . Uns interessiert das zufällige Zeitintervall T zwischen benachbarten Ereignissen in diesem Fluss; Finden wir das Verteilungsgesetz. Suchen wir zunächst die Verteilungsfunktion:

F(t) = P(T ( 0-2)

d.h. die Wahrscheinlichkeit, dass der Wert T wird einen Wert haben, der kleiner ist alsT. Verschieben wir vom Beginn des Intervalls T (Punkte t 0 ) Segment t und finden Sie die Wahrscheinlichkeit, dass das Intervall T es wird weniger sein T . Dazu ist es notwendig, dass für einen Abschnitt Länge T, neben einem Punkt t 0 , Mindestens ein Flow-Ereignis-Treffer. Berechnen wir die Wahrscheinlichkeit dafür F(t) durch die Wahrscheinlichkeit des gegenteiligen Ereignisses (pro Abschnitt). T trifft keine Flow-Ereignisse):

F(t) = 1 – P 0

Wahrscheinlichkeit P 0 wir finden mit Formel (1), vorausgesetztM = 0:

Daher lautet die Verteilungsfunktion des Wertes T:

(0-3)

Um die Verteilungsdichte zu ermitteln f(t) Zufallsvariable T, Es ist notwendig, den Ausdruck (0-1) zu differenzierenT:

0-4)

Das Verteilungsgesetz mit der Dichte (0-4) heißt exponentiell (oder exponentiell ). Die Größe λ wird als Parameter bezeichnet demonstratives Recht.

Abbildung 0 - 4 Exponentielle Verteilung

Lassen Sie uns die numerischen Eigenschaften einer Zufallsvariablen ermitteln T- mathematische Erwartung (Durchschnittswert) M [ t ]= m t , und Varianz Dt.

( 0-5)

Wir haben.

(Teilweise integrieren)

(0-6)

Die Streuung des T-Wertes beträgt: Indem wir die Quadratwurzel der Varianz ziehen, ermitteln wir die Standardabweichung der Zufallsvariablen

T.

Für eine Exponentialverteilung sind also der mathematische Erwartungswert und die Standardabweichung einander gleich und invers zum Parameter λ, wobei λ. Strömungsintensität. M So ist das Aussehen

Ereignisse in einem bestimmten Zeitraum entsprechen der Poisson-Verteilung, und die Wahrscheinlichkeit, dass die Zeitintervalle zwischen Ereignissen kleiner als eine bestimmte vorgegebene Zahl sind, entspricht der Exponentialverteilung. All dies sind lediglich unterschiedliche Beschreibungen desselben stochastischen Prozesses. .

Beispiel SMO-1

Betrachten Sie als Beispiel ein Bankensystem, das in Echtzeit arbeitet und eine große Anzahl von Kunden bedient. Während der Hauptverkehrszeiten bilden Anfragen von Bankangestellten, die mit Kunden arbeiten, einen Poisson-Fluss und gehen durchschnittlich zwei pro Sekunde ein (λ = 2). Der Fluss besteht aus Anfragen, die mit einer Intensität von 2 Anfragen pro Sekunde eingehen. Berechnen wir die Wahrscheinlichkeit P ( Nachrichten in 1 s. Da λ = 2, ergibt sich aus der vorherigen Formel:

Ersetzen von m = 0, 1, 2, 3, wir erhalten die folgenden Werte (mit einer Genauigkeit von vier).Dezimalstellen):

Abbildung 0 - 5 Beispiel für einen einfachen Ablauf

Es ist möglich, mehr als 9 Nachrichten pro Sekunde zu empfangen, die Wahrscheinlichkeit dafür ist jedoch sehr gering (ca. 0,000046).

Die resultierende Verteilung kann in Form eines Histogramms dargestellt werden (siehe Abbildung).

Beispiel SMO-2.

Ein Gerät (Server), das drei Nachrichten pro Sekunde verarbeitet.

Es gebe Geräte, die drei Nachrichten in 1 s verarbeiten können (µ=3). Im Durchschnitt werden zwei Nachrichten pro 1 Sekunde empfangen und gemäß C Poisson-Verteilung. Welcher Anteil dieser Nachrichten wird sofort nach Eingang verarbeitet?

Die Wahrscheinlichkeit, dass die Ankunftsrate kleiner oder gleich 3 s ist, ist gegeben durch

Wenn ein System maximal 3 Nachrichten in 1 s verarbeiten kann, beträgt die Wahrscheinlichkeit, dass es nicht überlastet wird

Mit anderen Worten: 85,71 % der Nachrichten werden sofort zugestellt und 14,29 % werden mit einer gewissen Verzögerung zugestellt. Wie Sie sehen, kommt es selten zu einer Verzögerung bei der Verarbeitung einer Nachricht, die länger als die Verarbeitungszeit von drei Nachrichten dauert. Die Bearbeitungszeit für 1 Nachricht beträgt durchschnittlich 1/3 s. Daher wird eine Verzögerung von mehr als 1 Sekunde selten auftreten, was für die meisten Systeme durchaus akzeptabel ist.

Beispiel SMO- 3

· Wenn ein Bankangestellter 80 % seiner Zeit beschäftigt ist und den Rest seiner Zeit damit verbringt, auf Kunden zu warten, dann kann er als Gerät mit einem Auslastungsfaktor von 0,8 betrachtet werden.

· Wenn ein Kommunikationskanal zum Übertragen von 8-Bit-Symbolen mit einer Rate von 2400 bps verwendet wird, d. h. maximal 2400/8 Symbole werden in 1 s übertragen, und wir bauen ein System auf, in dem die Gesamtdatenmenge 12000 beträgt Symbole, die von verschiedenen Geräten über den Kommunikationskanal pro Minute mit der höchsten Belastung gesendet werden (einschließlich Synchronisation, Nachrichtenendesymbole, Steuerung usw.), dann ist die Auslastungsrate des Kommunikationskanalgeräts während dieser Minute gleich

· Wenn eine Dateizugriffs-Engine während einer Hauptverkehrszeit 9.000 Dateizugriffe durchführt und die durchschnittliche Zeit pro Zugriff 300 ms beträgt, beträgt die Hardware-Auslastungsrate der Zugriffs-Engine zu Spitzenzeiten

Der Begriff der Gerätenutzung wird häufig verwendet. Je näher die Geräteauslastung bei 100 % liegt, desto größer sind die Verzögerungen und desto länger sind die Warteschlangen.

Mit der vorherigen Formel können Sie Tabellen mit Poisson-Funktionswerten erstellen, aus denen Sie die Eintrittswahrscheinlichkeit bestimmen könnenM oder mehr Nachrichten in einem bestimmten Zeitraum. Wenn es beispielsweise durchschnittlich 3,1 Nachrichten pro Sekunde gibt [d. h. e = 3.1], dann beträgt die Wahrscheinlichkeit, in einer bestimmten Sekunde 5 oder mehr Nachrichten zu empfangen, 0,2018 (fürM = 5 in der Tabelle). Oder in analytischer Form

Mithilfe dieses Ausdrucks kann ein Systemanalytiker die Wahrscheinlichkeit berechnen, dass das System ein bestimmtes Lastkriterium nicht erfüllt.

Oft können erste Berechnungen für die Belastungswerte der Ausrüstung durchgeführt werden

ρ ≤ 0,9

Diese Werte können mithilfe von Poisson-Tabellen ermittelt werden.

Auch hier sei die durchschnittliche Nachrichtenankunftsrate λ = 3,1 Nachrichten/s. Aus den Tabellen folgt, dass die Wahrscheinlichkeit, in einer Sekunde 6 oder mehr Nachrichten zu empfangen, 0,0943 beträgt. Daher kann diese Zahl als Belastungskriterium für erste Berechnungen herangezogen werden.

10.6.2. Designaufgaben

Wenn Nachrichten zufällig beim Gerät eintreffen, verbringt das Gerät einen Teil seiner Zeit mit der Verarbeitung oder Bearbeitung jeder Nachricht, was zur Bildung von Warteschlangen führt. Eine Warteschlange bei der Bank wartet auf die Freigabe des Kassierers und seines Computers (Terminals). Eine Nachrichtenwarteschlange im Eingabepuffer des Computers wartet auf die Verarbeitung durch den Prozessor. Eine Warteschlange mit Anfragen nach Datenfeldern wartet darauf, dass Kanäle frei werden usw. An allen Engpässen im System können sich Warteschlangen bilden.

Je höher die Geräteauslastung ist, desto länger sind die resultierenden Warteschlangen. Wie weiter unten gezeigt wird, ist es möglich, ein zufriedenstellend funktionierendes System mit einem Auslastungsfaktor von ρ = 0,7 zu ​​entwerfen, ein Koeffizient über ρ > 0,9 kann jedoch zu einer Verschlechterung der Dienstqualität führen. Mit anderen Worten: Wenn eine Massendatenverbindung eine Auslastung von 20 % aufweist, ist es unwahrscheinlich, dass sich darauf eine Warteschlange befindet. Beim Laden; 0,9 beträgt, bilden sich in der Regel Warteschlangen, teilweise sehr große.

Der Gerätenutzungsfaktor entspricht dem Verhältnis der Belastung des Geräts zur maximalen Belastung, der dieses Gerät standhalten kann, oder entspricht dem Verhältnis der Nutzungszeit des Geräts zur Gesamtbetriebszeit.

Beim Entwurf eines Systems wird üblicherweise der Auslastungsfaktor für verschiedene Gerätetypen geschätzt. Relevante Beispiele werden in den folgenden Kapiteln gegeben. Wenn Sie diese Koeffizienten kennen, können Sie Warteschlangen für die entsprechenden Geräte berechnen.

· Wie lang ist die Warteschlange?

· Wie lange wird es dauern?

Diese Art von Fragen können mithilfe der Warteschlangentheorie beantwortet werden.

10.6.3. Warteschlangensysteme, ihre Klassen und Hauptmerkmale

Für ein QS sind Ereignisströme Anwendungsströme, „Wartungs“-Anwendungsströme usw. Wenn es sich bei diesen Flüssen nicht um Poisson-Ströme (Markov-Prozess) handelt, wird die mathematische Beschreibung der im QS ablaufenden Prozesse ungleich komplexer und erfordert einen umständlicheren Aufwand Eine apparative Umsetzung in analytische Formeln ist nur in den einfachsten Fällen möglich.

Der Apparat der „Markov“-Warteschlangentheorie kann jedoch auch dann nützlich sein, wenn der im QS ablaufende Prozess vom Markovschen Prozess abweicht und mit seiner Hilfe die Leistungsmerkmale des QS näherungsweise beurteilt werden können. Es ist zu beachten, dass die mit der Markov-Theorie erhaltenen Näherungsformeln umso genauer sind, je komplexer das QS ist und je mehr Servicekanäle es hat. Darüber hinaus ist in einer Reihe von Fällen keine genaue Kenntnis aller seiner Merkmale erforderlich, um fundierte Entscheidungen über die Führung des QS-Betriebs zu treffen, sondern häufig sind nur ungefähre, ungefähre Kenntnisse ausreichend.

QS werden in Systeme eingeteilt mit:

· Misserfolge (mit Verlusten). In solchen Systemen erhält eine Anfrage, die zu einem Zeitpunkt eingeht, an dem alle Kanäle belegt sind, eine „Ablehnung“, verlässt das QS und nimmt nicht am weiteren Serviceprozess teil.

· warten (mit einer Warteschlange). In solchen Systemen wird eine Anfrage, die zu einem Zeitpunkt eintrifft, zu dem alle Kanäle belegt sind, in die Warteschlange gestellt und gewartet, bis einer der Kanäle frei wird. Wenn der Kanal freigegeben ist, wird eine der in der Warteschlange befindlichen Anforderungen zur Bearbeitung angenommen.

Service (Warteschlangendisziplin) in einem Wartesystem kann sein

· bestellt (Bewerbungen werden in der Reihenfolge ihres Eingangs bearbeitet),

· ungeordnet(Bewerbungen werden in zufälliger Reihenfolge zugestellt) oder

· gestapelt (Die letzte Anfrage wird zuerst aus der Warteschlange ausgewählt).

· Priorität

O mit statischer Priorität

O mit dynamischer Priorität

(im letzteren Fall vor tet kann sich beispielsweise mit der Dauer des Wartens auf eine Bewerbung erhöhen).

Warteschlangensysteme werden in Systeme unterteilt

· mit unbegrenztem Warten und

· mit begrenzt Warten.

In Systemen mit unbegrenzter Wartezeit wird jede Anfrage, die zu einem Zeitpunkt eintrifft, an dem keine freien Kanäle vorhanden sind, in eine Warteschlange gestellt und „geduldig“ darauf gewartet, dass der Kanal verfügbar wird, und ihn zur Bearbeitung annehmen. Jeder beim CMO eingegangene Antrag wird früher oder später bearbeitet.

In Systemen mit begrenzter Wartezeit gelten bestimmte Einschränkungen für das Verweilen einer Anwendung in der Warteschlange. Diese Einschränkungen können gelten

· Warteschlangenlänge (die Anzahl der Anwendungen gleichzeitig in der Warteschlange in einem System mit begrenzter Warteschlangenlänge),

· die Zeit, die die Anwendung in der Warteschlange verbracht hat (nach einer bestimmten Verweildauer in der Warteschlange verlässt die Anwendung die Warteschlange und das System verlässt das System mit einer begrenzten Wartezeit),

· Gesamtverweildauer des Antrags im CMO

usw.

Abhängig von der Art des QS können bestimmte Werte (Leistungsindikatoren) zur Beurteilung der Wirksamkeit herangezogen werden. Beispielsweise ist für ein QS mit Fehlern eines der wichtigsten Merkmale seiner Produktivität das sogenannte absoluter Durchsatz die durchschnittliche Anzahl der Anfragen, die das System pro Zeiteinheit bedienen kann.

Zusammen mit dem Absoluten wird es oft berücksichtigt relativer Durchsatz QS ist der durchschnittliche Anteil der vom System bearbeiteten eingehenden Bewerbungen (das Verhältnis der durchschnittlichen Anzahl der vom System pro Zeiteinheit bearbeiteten Bewerbungen zur durchschnittlichen Anzahl der während dieser Zeit eingegangenen Bewerbungen).

Neben dem absoluten und relativen Durchsatz können uns bei der Analyse eines QS mit Fehlern je nach Forschungsproblem auch andere Merkmale interessieren, zum Beispiel:

· durchschnittliche Anzahl belegter Kanäle;

· durchschnittliche relative Ausfallzeit des Gesamtsystems und eines einzelnen Kanals

usw.

Fragen mit Erwartung haben leicht unterschiedliche Eigenschaften. Offensichtlich verlieren bei einem QS mit unbegrenztem Warten sowohl der absolute als auch der relative Durchsatz ihre Bedeutung, da jeder die Anfrage früh erhieltoder es wird später serviert. Wichtige Merkmale für ein solches QS sind:

· durchschnittliche Anzahl der Bewerbungen in der Warteschlange;

· durchschnittliche Anzahl von Anwendungen im System (in der Warteschlange und in Bearbeitung);

· durchschnittliche Wartezeit für eine Bewerbung in der Warteschlange;

· durchschnittliche Verweildauer einer Anwendung im System (in der Warteschlange und in Bearbeitung);

sowie andere Erwartungsmerkmale.

Für ein QS mit begrenzter Wartezeit sind beide Gruppen von Merkmalen von Interesse: sowohl der absolute als auch der relative Durchsatz und die Wartemerkmale.

Um den im QS ablaufenden Prozess zu analysieren, ist es wichtig, die Hauptparameter des Systems zu kennen: die Anzahl der Kanäle P, Intensität des Bewerbungsflussesλ , die Leistung jedes Kanals (die durchschnittliche Anzahl der vom Kanal pro Zeiteinheit bedienten Anfragen μ), Bedingungen für die Bildung einer Warteschlange (ggf. Einschränkungen).

Abhängig von den Werten dieser Parameter werden die Leistungsmerkmale des QS ausgedrückt.

10.6.4. Formeln zur Berechnung der Eigenschaften des QS für den Servicefall mit einem Gerät

Abbildung 0 - 6 Modell eines Warteschlangensystems mit einer Warteschlange

Solche Warteschlangen können durch Nachrichten am Prozessoreingang entstehen, die auf die Verarbeitung warten. Sie können während des Betriebs von Teilnehmerpunkten auftreten, die an einen Mehrpunkt-Kommunikationskanal angeschlossen sind. Ebenso bilden sich an Tankstellen Autoschlangen. Wenn jedoch mehr als ein Serviceeingang vorhanden ist, entsteht eine Warteschlange mit vielen Geräten und die Analyse wird komplizierter.

Betrachten wir den Fall des einfachsten Ablaufs von Serviceanfragen.

Der Zweck der vorgestellten Warteschlangentheorie besteht darin, die durchschnittliche Warteschlangengröße sowie die durchschnittliche Zeit zu ermitteln, die Nachrichten in Warteschlangen verbringen. Es empfiehlt sich auch abzuschätzen, wie oft die Warteschlange eine bestimmte Länge überschreitet. Anhand dieser Informationen können wir beispielsweise die erforderliche Menge an Pufferspeicher für die Speicherung von Nachrichtenwarteschlangen und entsprechenden Programmen, die erforderliche Anzahl von Kommunikationsleitungen, die erforderlichen Puffergrößen für Hubs usw. berechnen. Es wird möglich sein, Antwortzeiten abzuschätzen.

Jedes der Merkmale variiert je nach den verwendeten Mitteln.

Stellen Sie sich eine Warteschlange mit einem Server vor. Beim Entwurf eines Computersystems werden die meisten Warteschlangen dieser Art anhand der angegebenen Formeln berechnet. Variationskoeffizient der Dienstzeit

Die Chinchin-Polacek-Formel wird zur Berechnung der Warteschlangenlängen beim Entwurf von Informationssystemen verwendet. Es wird im Fall einer exponentiellen Verteilung der Ankunftszeit für jede Verteilung der Servicezeit und jede Kontrolldisziplin verwendet, sofern die Wahl der nächsten Nachricht für den Service nicht von der Servicezeit abhängt.

Beim Entwerfen von Systemen gibt es Situationen, in denen Warteschlangen entstehen, wenn die Verwaltungsdisziplin zweifellos von der Servicezeit abhängt. Beispielsweise können wir in manchen Fällen kürzere Nachrichten für den vorrangigen Service auswählen, um eine kürzere durchschnittliche Servicezeit zu erreichen. Bei der Steuerung einer Kommunikationsleitung können Sie Eingangsnachrichten eine höhere Priorität zuweisen als Ausgangsnachrichten, da erstere kürzer sind. In solchen Fällen ist die Verwendung der Chinchin-Gleichung nicht mehr erforderlich

Die meisten Servicezeiten in Informationssystemen liegen irgendwo zwischen diesen beiden Fällen. Wartungszeiten gleich einem konstanten Wert sind selten. Selbst die Zugriffszeit auf die Festplatte ist aufgrund der unterschiedlichen Positionen der Datenfelder auf der Oberfläche nicht konstant. Ein Beispiel für den Fall einer konstanten Dienstzeit ist die Belegung einer Kommunikationsleitung zur Übertragung von Nachrichten fester Länge.

Andererseits ist die Streuung der Dienstzeit nicht so groß wie bei ihrer willkürlichen oder exponentiellen Verteilung, d.h.σs erreicht selten Wertets. Dieser Fall wird manchmal als der „schlimmste Fall“ angesehen und daher werden Formeln verwendet, die sich auf die exponentielle Verteilung der Servicezeiten beziehen. Eine solche Berechnung kann zu leicht überhöhten Warteschlangen und Wartezeiten führen, aber dieser Fehler ist zumindest nicht gefährlich.

Eine exponentielle Verteilung der Servicezeiten ist in der Realität natürlich nicht der schlimmste Fall. Wenn sich jedoch herausstellt, dass die aus Warteschlangenberechnungen ermittelten Servicezeiten schlechter verteilt sind als exponentiell verteilte Zeiten, ist dies häufig ein Warnsignal für den Designer. Wenn die Standardabweichung größer als der Durchschnitt ist, müssen die Berechnungen normalerweise angepasst werden.

Betrachten Sie das folgende Beispiel. Es gibt sechs Arten von Nachrichten mit den Servicezeiten 15, 20, 25, 30, 35 und 300. Die Anzahl der Nachrichten ist bei jedem Typ gleich. Die Standardabweichung der angegebenen Zeiten liegt etwas über ihrem Durchschnitt. Der letzte Servicezeitwert ist viel höher als bei anderen. Dies führt dazu, dass Nachrichten deutlich länger in der Warteschlange verbleiben, als wenn die Servicezeiten in der gleichen Größenordnung wären. In diesem Fall empfiehlt es sich, bei der Planung Maßnahmen zur Reduzierung der Warteschlangenlänge zu ergreifen. Wenn sich diese Zahlen beispielsweise auf die Nachrichtenlänge beziehen, kann es sich lohnen, sehr lange Nachrichten in Teile aufzuteilen.

10.6.6. Berechnungsbeispiel

Bei der Gestaltung eines Bankensystems ist es wünschenswert, die Anzahl der Kunden zu kennen, die während der Hauptverkehrszeiten in der Warteschlange für einen Kassierer stehen müssen.

Die Systemreaktionszeit und ihre Standardabweichung werden unter Berücksichtigung der Zeit der Dateneingabe am Arbeitsplatz, des Druckens und der Dokumentausführung berechnet.

Die Aktionen der Kassiererin waren zeitlich begrenzt. Die Servicezeit ts entspricht der Gesamtzeit, die der Kassierer beim Kunden verbringt. Der Auslastungsgrad ρ des Kassierers ist proportional zur Zeit, mit der er beschäftigt ist. Wenn λ die Anzahl der Kunden während der Hauptverkehrszeiten ist, dann ist ρ für den Kassierer gleich

Nehmen wir an, dass es zu Spitzenzeiten 30 Kunden pro Stunde gibt. Im Durchschnitt verbringt ein Kassierer 1,5 Minuten pro Kunde. Dann

ρ =(1,5 * 30) / 60 = 0,75

d.h. die Kasse ist zu 75 % ausgelastet.

Mithilfe von Grafiken lässt sich die Anzahl der Personen in der Schlange schnell abschätzen. Daraus folgt, dass wenn ρ = 0,75, dann die durchschnittliche Anzahl nq der Menschenin einer Kassenzeile liegt je nach Standardabweichung für zwischen 1,88 und 3,0 ts .

Nehmen wir die Standardabweichungsmessung für t anS ergab einen Wert von 0,5 min. Dann

σ s = 0,33 t s

Aus der Grafik in der ersten Abbildung ergibt sich, dass nq = 2,0, d. h. im Durchschnitt warten zwei Kunden an der Kasse.

Die Gesamtzeit, die ein Kunde an der Kasse verbringt, lässt sich ermitteln als

t ∑ = t q + t s = 2,5 Min. + 1,5 Min. = 4 Min

wo es ist berechnet nach der Chinchin-Polacek-Formel.

10.6.7. Gewinnfaktor

Wenn wir die in den Abbildungen gezeigten Kurven analysieren, sehen wir, dass die Kurven besorgniserregend ansteigen, wenn die Geräte, die die Warteschlange bedienen, zu mehr als 80 % ausgelastet sind. Diese Tatsache ist beim Entwurf von Datenübertragungssystemen sehr wichtig. Wenn wir ein System mit einer Hardwareauslastung von mehr als 80 % entwerfen, kann ein geringfügiger Anstieg des Datenverkehrs dazu führen, dass die Leistung des Systems sinkt oder es sogar abstürzt.

Anstieg des eingehenden Datenverkehrs um eine kleine Zahl x %. führt zu einer Erhöhung der Warteschlangengröße um ca

Wenn die Geräteauslastung 50 % beträgt, entspricht dieser Anstieg 4 ts % für die exponentielle Verteilung der Servicezeit. Wenn die Hardwareauslastung jedoch 90 % beträgt, beträgt die Vergrößerung der Warteschlangengröße 100 ts %, also das 25-fache. Eine leichte Erhöhung der Auslastung bei einer Geräteauslastung von 90 % führt zu einer 25-fachen Vergrößerung der Warteschlangengrößen im Vergleich zu einer Geräteauslastung von 50 %.

Ebenso erhöht sich die in der Warteschlange verbrachte Zeit um

Bei einer exponentiell verteilten Servicezeit beträgt dieser Wert 4 t s 2 für einen Ausrüstungsnutzungsgrad von 50 % und 100 t s 2 bei einem Koeffizienten von 90 %, also nochmals 25-mal schlechter.

Darüber hinaus ist bei niedrigen Geräteauslastungsraten die Auswirkung von Änderungen in σs auf die Warteschlangengröße vernachlässigbar. Bei großen Koeffizienten ändert sich jedoch σ S wirkt sich stark auf die Warteschlangengröße aus. Daher ist es beim Entwurf von Systemen mit hoher Geräteauslastung wünschenswert, genaue Informationen über den Parameter zu erhaltenσ S. Ungenauigkeit der Annahme bezüglich der Exponentialität der t-VerteilungSmacht sich am deutlichsten bei großen Werten von ρ bemerkbar. Wenn sich außerdem die Servicezeit plötzlich erhöht, was in Kommunikationskanälen bei der Übertragung langer Nachrichten möglich ist, bildet sich bei großen ρ eine erhebliche Warteschlange.

Der in der vorherigen Vorlesung besprochene Markov-Zufallsprozess mit diskreten Zuständen und kontinuierlicher Zeit findet in Warteschlangensystemen (QS) statt.

Warteschlangensysteme – Hierbei handelt es sich um Systeme, die zu zufälligen Zeiten Serviceanfragen empfangen und die empfangenen Anfragen über die dem System zur Verfügung stehenden Servicekanäle bearbeitet werden.

Beispiele für Warteschlangensysteme sind:

• Barausgleichseinheiten in Banken und Unternehmen;
• Personalcomputer, die eingehende Anwendungen oder Anforderungen zur Lösung bestimmter Probleme bedienen;
• Autowerkstätten; Tankstelle;
• Wirtschaftsprüfungsgesellschaften;
• Steuerkontrollabteilungen, die für die Annahme und Überprüfung der aktuellen Berichterstattung von Unternehmen zuständig sind;
• Telefonzentralen usw.

Betrachten wir das Funktionsdiagramm des QS (Abb. 1). Das System besteht aus einem Anforderungsgenerator, einem Dispatcher und einer Serviceeinheit, einer Fehlerabrechnungseinheit (Terminator, Order Destroyer). Im Allgemeinen kann ein Dienstknoten über mehrere Dienstkanäle verfügen.

Reis. 1

1. Anwendungsgenerator – Objekt generierende Anfragen: Straße, Werkstatt mit installierten Einheiten. Die Eingabe ist Fluss der Bewerbungen(Kundenstrom zum Laden, Strom kaputter Einheiten (Maschinen, Maschinen) zur Reparatur, Besucherstrom zur Garderobe, Autostrom zur Tankstelle usw.).
2. Dispatcher – eine Person oder ein Gerät, die weiß, was mit der Anwendung zu tun ist. Ein Knoten, der Anfragen reguliert und an Servicekanäle weiterleitet. Dispatcher:

• nimmt Bewerbungen entgegen;
• bildet eine Warteschlange, wenn alle Kanäle belegt sind;
• leitet sie an Servicekanäle weiter, sofern es freie gibt;
• lehnt Bewerbungen ab (aus verschiedenen Gründen);
• empfängt vom Dienstknoten Informationen über freie Kanäle;
• überwacht die Betriebszeit des Systems.

1. Warteschlange – Anwendungsakkumulator. Möglicherweise gibt es keine Warteschlange.
2. Servicecenter besteht aus einer endlichen Anzahl von Servicekanälen. Jeder Kanal hat 3 Zustände: frei, beschäftigt, funktioniert nicht. Wenn alle Kanäle ausgelastet sind, können Sie eine Strategie entwickeln, an wen die Anfrage weitergeleitet werden soll.
3. Ablehnung Der Dienstabbruch erfolgt, wenn alle Kanäle belegt sind (einige davon funktionieren möglicherweise nicht).

Zusätzlich zu diesen Grundelementen im QS heben einige Quellen auch die folgenden Komponenten hervor:

Terminator – Zerstörer von Transaktionen;

Lager – Lagerung von Ressourcen und Fertigprodukten;

Buchhaltungskonto – zur Durchführung von Transaktionen des Typs „Buchung“;

Manager – Ressourcenmanager;

Klassifizierung von SMO

Erste Division (basierend auf dem Vorhandensein von Warteschlangen):

• QS mit Ausfällen;
• SMO mit einer Warteschlange.

IN QS mit Ausfällen Ein Antrag, der zu einem Zeitpunkt eingeht, an dem alle Kanäle belegt sind, wird abgelehnt, verlässt das QS und wird in Zukunft nicht mehr bearbeitet.

IN Warteschlange mit Warteschlange Eine Anwendung, die zu einem Zeitpunkt eintrifft, an dem alle Kanäle ausgelastet sind, verlässt die Anwendung nicht, sondern stellt sich in eine Warteschlange und wartet auf die Bereitstellung der Gelegenheit.

QS mit Warteschlangen werden je nach Organisation der Warteschlange in verschiedene Typen unterteilt - begrenzt oder unbegrenzt. Einschränkungen können sowohl die Länge der Warteschlange als auch die Wartezeit betreffen, „Servicedisziplin“.

So kommen beispielsweise folgende QS in Betracht:

• CMO mit ungeduldigen Anfragen (Warteschlangenlänge und Servicezeit sind begrenzt);
• QS mit vorrangiger Bedienung, d. h. einige Anfragen werden außerhalb der Reihe bearbeitet usw.

Arten von Warteschlangenbeschränkungen können kombiniert werden.

Eine andere Klassifizierung unterteilt die CMO nach der Quelle der Anträge. Anwendungen (Anforderungen) können vom System selbst oder von einer externen Umgebung generiert werden, die unabhängig vom System existiert.

Natürlich hängt der Fluss der vom System selbst generierten Anwendungen vom System und seinem Zustand ab.

Darüber hinaus werden SMOs unterteilt in offen CMO und geschlossen SMO.

In einem offenen QS hängen die Eigenschaften des Bewerbungsflusses nicht vom Zustand des QS selbst ab (wie viele Kanäle sind belegt). In einem geschlossenen QS sind sie darauf angewiesen. Wenn beispielsweise ein Arbeiter eine Gruppe von Maschinen bedient, die von Zeit zu Zeit angepasst werden müssen, hängt die Intensität des „Anforderungsflusses“ von den Maschinen davon ab, wie viele von ihnen bereits betriebsbereit sind und auf eine Anpassung warten.

Ein Beispiel für ein geschlossenes System: Ein Kassierer, der in einem Unternehmen Löhne ausgibt.

Basierend auf der Anzahl der Kanäle werden QSs unterteilt in:

• einkanalig;
• Mehrkanal.

Merkmale eines Warteschlangensystems

Die Hauptmerkmale aller Arten von Warteschlangensystemen sind:

• Eingabestrom eingehender Anforderungen oder Serviceanfragen;
• Warteschlangendisziplin;
• Servicemechanismus.

Eingabeanforderungen-Stream

Um den Eingabestream zu beschreiben, müssen Sie ihn angeben ein Wahrscheinlichkeitsgesetz, das die Abfolge der Zeitpunkte bestimmt, in denen Serviceanfragen eingehen, und geben Sie die Anzahl dieser Anforderungen in jeder weiteren Quittung an. Dabei operieren sie in der Regel mit dem Konzept der „wahrscheinlichen Verteilung der Zeitpunkte des Bedarfseingangs“. Hier können sie Folgendes tun: Einzel- und Gruppenanforderungen (die Anzahl solcher Anforderungen in jeder regulären Quittung). Im letzteren Fall sprechen wir normalerweise von einem Warteschlangensystem mit paralleler Gruppenbedienung.

A i– Ankunftszeit zwischen Anforderungen – unabhängige identisch verteilte Zufallsvariablen;

E(A)– durchschnittliche (MO) Ankunftszeit;

λ=1/E(A)– Intensität des Forderungseingangs;

Eigenschaften des Eingabestreams:

1. Ein probabilistisches Gesetz, das die Reihenfolge der Zeitpunkte bestimmt, in denen Serviceanfragen eingehen.
2. Die Anzahl der Anfragen bei jedem nächsten Eingang für Gruppenflüsse.

Disziplin in der Warteschlange

Warteschlange – eine Reihe von Anforderungen, die auf ihre Zustellung warten.

Die Warteschlange hat einen Namen.

Disziplin in der Warteschlange definiert das Prinzip, nach dem am Eingang des bedienenden Systems eintreffende Anforderungen aus der Warteschlange mit der Serviceprozedur verbunden werden. Die am häufigsten verwendeten Warteschlangendisziplinen werden durch die folgenden Regeln definiert:

• Wer zuerst kommt, mahlt zuerst;

First-In-First-Out (FIFO)

die häufigste Art von Warteschlange.

Welche Datenstruktur eignet sich zur Beschreibung einer solchen Warteschlange? Das Array ist fehlerhaft (begrenzt). Sie können eine LIST-Struktur verwenden.

Die Liste hat einen Anfang und ein Ende. Die Liste besteht aus Einträgen. Ein Eintrag ist eine Listenzelle. Die Anwendung kommt am Ende der Liste an und wird vom Anfang der Liste für den Service ausgewählt. Der Datensatz besteht aus Merkmalen der Anwendung und einem Link (Indikator dafür, wer dahinter steckt). Wenn die Warteschlange außerdem eine Wartezeitbegrenzung hat, muss auch die maximale Wartezeit angegeben werden.

Als Programmierer sollten Sie in der Lage sein, bidirektionale und einseitige Listen zu erstellen.

Aktionen auflisten:

• in den Schwanz einführen;
• von Anfang an nehmen;
• nach Ablauf des Timeouts aus der Liste entfernen.
• Wer als Letzter ankommt, wird als Erster bedient LIFO (Patronenclip, Sackgasse an einem Bahnhof, in ein überfülltes Auto gelaufen).

Eine Struktur, die als STACK bekannt ist. Kann durch eine Array- oder Listenstruktur beschrieben werden;

• zufällige Auswahl der Bewerbungen;
• Auswahl der Bewerbungen nach Prioritätskriterien.

Jede Bewerbung zeichnet sich unter anderem durch ihre Prioritätsstufe aus und wird bei Eingang nicht am Ende der Warteschlange, sondern am Ende ihrer Prioritätsgruppe platziert. Der Dispatcher sortiert nach Priorität.

Warteschlangeneigenschaften

• EinschränkungWartezeit der Zeitpunkt der Zustellung (es gibt eine Warteschlange mit einer begrenzten Wartezeit auf die Zustellung, was mit dem Konzept der „zulässigen Warteschlangenlänge“ verbunden ist);
• Warteschlangenlänge.

Servicemechanismus

Servicemechanismus wird durch die Merkmale des Serviceverfahrens selbst und die Struktur des Servicesystems bestimmt. Zu den Merkmalen des Wartungsverfahrens gehören:

• Anzahl der Servicekanäle ( N);
• Dauer des Servicevorgangs (probabilistische Verteilung der Zeit für Serviceanforderungen);
• die Anzahl der in jedem dieser Verfahren erfüllten Anforderungen (bei Gruppenanträgen);
• Wahrscheinlichkeit eines Dienstkanalausfalls;
• Struktur des Dienstleistungssystems.

Um die Merkmale eines Servicevorgangs analytisch zu beschreiben, wird das Konzept der „probabilistischen Zeitverteilung für Serviceanforderungen“ verwendet.

S i– Servicezeit ich-te Anforderung;

E(S)– durchschnittliche Servicezeit;

μ=1/E(S)– Geschwindigkeit der Bearbeitung von Anfragen.

Es ist zu beachten, dass die für die Wartung einer Anwendung erforderliche Zeit von der Art der Anwendung selbst oder den Anforderungen des Kunden sowie vom Zustand und den Fähigkeiten des Wartungssystems abhängt. In manchen Fällen ist es auch notwendig, dies zu berücksichtigen Wahrscheinlichkeit eines Dienstkanalausfalls nach einer bestimmten begrenzten Zeitspanne. Dieses Merkmal kann als Strom von Fehlern modelliert werden, die in das QS eingehen und Vorrang vor allen anderen Anfragen haben.

QS-Auslastungsgrad

N·μ – Servicegeschwindigkeit im System, wenn alle Servicegeräte beschäftigt sind.

ρ=λ/( Nμ) – genannt Auslastungskoeffizient von QS , zeigt an, wie viele Systemressourcen verwendet werden.

Struktur des Servicesystems

Die Struktur des Servicesystems wird durch die Anzahl und relative Anordnung der Servicekanäle (Mechanismen, Geräte usw.) bestimmt. Zunächst sollte betont werden, dass ein Servicesystem mehr als einen Servicekanal haben kann, aber mehrere; Diese Art von System ist in der Lage, mehrere Anforderungen gleichzeitig zu erfüllen. In diesem Fall bieten alle Servicekanäle die gleichen Dienste an, und daher kann man argumentieren, dass dies der Fall ist Paralleldienst .

Beispiel. Registrierkassen im Laden.

Das Servicesystem kann aus mehreren unterschiedlichen Arten von Servicekanälen bestehen, die jede bediente Anforderung durchlaufen muss, d. h. im Servicesystem Awerden konsequent umgesetzt . Der Wartungsmechanismus bestimmt die Eigenschaften des ausgehenden (bedienten) Anforderungsflusses.

Beispiel. Medizinische Kommission.

Kombinierter Service – Einlagenverwaltung in der Sparkasse: zuerst der Controller, dann der Kassierer. In der Regel 2 Controller pro Kassierer.

Also, Die Funktionalität eines Warteschlangensystems wird durch die folgenden Hauptfaktoren bestimmt :

• Wahrscheinlichkeitsverteilung der Zeitpunkte des Eingangs von Serviceanfragen (einzeln oder gruppenweise);
• Macht der Anforderungsquelle;
• Wahrscheinlichkeitsverteilung der Dienstdauer;
• Konfiguration des Bereitstellungssystems (paralleler, sequentieller oder parallel-sequentieller Dienst);
• Anzahl und Produktivität der Servicekanäle;
• Warteschlangendisziplin.

Die Hauptkriterien für die Wirksamkeit der Funktionsweise des QS

Als Hauptkriterien für die Wirksamkeit von Warteschlangensystemen Abhängig von der Art des zu lösenden Problems kann Folgendes angezeigt werden:

• Wahrscheinlichkeit der sofortigen Bearbeitung einer eingehenden Anfrage (P obsl = K obs / K post);
• Wahrscheinlichkeit der Ablehnung einer eingehenden Bewerbung (P offen = K offen / K post);

Offensichtlich ist P obsl + P open =1.

Abläufe, Verzögerungen, Wartung. Pollacheck-Khinchin-Formel

Verzögerung – Eines der Kriterien für die Bedienung des QS ist die Zeit, die die Anwendung auf die Bedienung wartet.

D i– Verzögerung in der Anforderungswarteschlange ich;

W i =D i + S i– benötigte Zeit im System ich.

(mit Wahrscheinlichkeit 1) – die ermittelte durchschnittliche Verzögerung einer Anfrage in der Warteschlange;

(mit Wahrscheinlichkeit 1) – die ermittelte durchschnittliche Verweildauer der Anforderung im QS (Wartezeit).

Q(T) - Anzahl der Anfragen gleichzeitig in der Warteschlange T;

L(T)– Anzahl der Anforderungen gleichzeitig im System T(Q(T) plus die Anzahl der Anforderungen, die gleichzeitig bedient werden T.

Dann die Indikatoren (falls vorhanden)

(mit Wahrscheinlichkeit 1) – die stationäre durchschnittliche Anzahl der Anfragen in der Warteschlange im Laufe der Zeit;

(mit Wahrscheinlichkeit 1) – die stationäre durchschnittliche Anzahl der Anforderungen im System über die Zeit.

Beachten Sie, dass ρ<1 – обязательное условие существования d, w, Q Und L in einem Warteschlangensystem.

Wenn wir uns daran erinnern, dass ρ= λ/( Nμ), dann ist klar, dass wenn die Intensität des Bewerbungseingangs größer ist als Nμ, dann ist ρ>1 und es ist natürlich, dass das System einem solchen Antragsstrom nicht gewachsen ist und wir daher nicht über die Mengen sprechen können d, w, Q Und L.

Zu den allgemeinsten und notwendigsten Ergebnissen für Warteschlangensysteme gehören Erhaltungsgleichungen

Es ist zu beachten, dass die oben genannten Kriterien zur Bewertung der Systemleistung für Warteschlangensysteme analytisch berechnet werden können M/M/N(N>1), also Systeme mit Markov-Flüssen von Anfragen und Diensten. Für M/G/ l für jede Distribution G und für einige andere Systeme. Im Allgemeinen müssen die Verteilung der Ankunftszeit, die Servicezeitverteilung oder beide exponentiell sein (oder eine Art exponentielle Erlang-Verteilung k-ter Ordnung), damit eine analytische Lösung möglich ist.

Darüber hinaus können wir auch über Merkmale sprechen wie:

• absolute Systemkapazität – А=Р obsl *λ;
• relative Systemkapazität –

Ein weiteres interessantes (und anschauliches) Beispiel einer analytischen Lösung – Berechnen der stationären durchschnittlichen Verzögerung in einer Warteschlange für ein Warteschlangensystem M/G/ 1 nach der Formel:

.

In Russland ist diese Formel als Pollacek-Formel bekannt – Chinchin, im Ausland ist diese Formel mit dem Namen Ross verbunden.

Also, wenn E(S) größer ist, dann die Überlast (in diesem Fall gemessen als). D) wird größer sein; was zu erwarten ist. Die Formel offenbart auch eine weniger offensichtliche Tatsache: Auch die Überlastung nimmt zu, wenn die Variabilität der Servicezeitverteilung zunimmt, selbst wenn die durchschnittliche Servicezeit gleich bleibt. Intuitiv lässt sich dies wie folgt erklären: Die Varianz der Zufallsvariablen der Servicezeit kann einen großen Wert annehmen (da sie positiv sein muss), d. h. das einzige Servicegerät wird lange Zeit beschäftigt sein, was dazu führt eine Vergrößerung der Warteschlange.

Das Thema der Warteschlangentheorie besteht darin, eine Beziehung zwischen den Faktoren herzustellen, die die Funktionalität des Warteschlangensystems und die Effizienz seines Betriebs bestimmen. In den meisten Fällen sind alle Parameter, die Warteschlangensysteme beschreiben, Zufallsvariablen oder Funktionen, daher gehören diese Systeme zu stochastischen Systemen.

Die Zufälligkeit des Bewerbungsflusses (Anforderungen) sowie im allgemeinen Fall der Leistungsdauer führt dazu, dass im Warteschlangensystem ein zufälliger Prozess stattfindet. Aufgrund der Natur des Zufallsprozesses , die im Warteschlangensystem (QS) auftreten, werden unterschieden Markovianische und nicht-markovianische Systeme . In Markov-Systemen sind der eingehende Fluss von Anforderungen und der ausgehende Fluss von bedienten Anforderungen (Anwendungen) Poisson. Poisson-Flüsse erleichtern die Beschreibung und Konstruktion eines mathematischen Modells eines Warteschlangensystems. Für diese Modelle gibt es relativ einfache Lösungen, weshalb die meisten bekannten Anwendungen der Warteschlangentheorie das Markov-Schema verwenden. Bei Nicht-Markov-Prozessen werden die Probleme bei der Untersuchung von Warteschlangensystemen deutlich komplizierter und erfordern den Einsatz statistischer Modellierung und numerischer Methoden am Computer.