Toevalsprocessen/Wachtrijtheorie

Hoofdstukken

De wachtrijtheorie beschrijft, bestudeert en verklaart de verschijnselen die zich voordoen in wachtrijsystemen, systemen waarin klanten moeten wachten op bediening. De wachtrijtheorie wordt onder andere toegepast in de analyse en het ontwerp van computers, telecommunicatiesystemen en productieprocessen. Wachtrijsystemen worden wiskundig met behulp van technieken uit de kansrekening geanalyseerd met het doel de meest effectieve maatregelen te vinden tegen een te lange wachttijd, of het gedrag van deze systemen te kunnen voorspellen en controleren. Wachtrijen leiden vaak tot veel irritatie. De wachtrijtheorie is daarom ook wel bekend als de wiskunde van de ergernis.

De eerste ontwikkelingen in de wachtrijtheorie kwamen uit de telefonie. Erlang, een Deense ingenieur die voor een telefoonmaatschappij in Kopenhagen werkte, publiceerde in 1909 het eerste artikel over wachtrijtheorie.

Wachtrijsystemen

Structuur van een wachtrijsysteem

Een wachtrijsysteem is een systeem waarin klanten een dienstverlening (service) verlangen van een verwerkingseenheid. Indien de tijdstippen waarop de aanvragen gebeuren of de hoeveelheid service die gevraagd wordt onvoorspelbaar is of varieert, kunnen conflicten ontstaan tussen de verschillende klanten, en zal een rij van wachtende klanten ontstaan. De fundamentele reden voor het ontstaan van deze wachtrij is dat er tijdelijk meer aanvragen voor een bepaalde dienst het systeem binnenkomen, dan het systeem op dat moment kan verwerken.

De verwerkingseenheid (in het Engels service unit of service facility) kan bestaan uit een of meer bedieningsstations (servers), aangeduid als kanalen of loketten, die parallel werken. Elk zo'n bedieningsstation kan één klant tegelijk verwerken. Komt een klant aan op een moment dat alle kanalen bezet zijn, dan gaat deze klant in een wachtrij staan tot er voor hem een kanaal vrijkomt. Wanneer er in de wachtrij geen plaats is, wordt de klant geweigerd, en gaat deze voor het systeem 'verloren'.

Modelmatige beschrijving

De wachtrijtheorie bestudeert de wachtrijverschijnselen en -systemen door middel van wiskundige modellen. Daarin worden over de grootheden die het systeem bepalen veronderstellingen gemaakt, die in praktische situaties goed aansluiten bij de werkelijkheid. Die grootheden zijn: het aankomstproces en de verdeling van de bedieningsduren. Daarnaast moet natuurlijk bekend zijn wat de bedieningsstrategie is, wat de capaciteit van de wachtrijbuffer is en of de betrokken objecten mogelijk uit een eindige populatie komen.

Populatie

De bron of populatie van mogelijke klanten voor het systeem kan eindig of oneindig zijn. Een oneindige bron is wiskundig meestal eenvoudiger dan een eindige, aangezien in het eindige geval het aantal klanten die al in het systeem aanwezig zijn, een invloed zal hebben op de aankomststroom van nieuwe klanten.

Aankomstproces

Het aankomstproces beschrijft hoe en met welke snelheid klanten het systeem binnenkomen. Daartoe specificeert men volgens welk patroon de aankomsttijdstippen op de tijdas verdeeld liggen. Meestal beschouwt men de tijd tussen twee opeenvolgende aankomsten, de tussenaankomsttijd, en modelleert deze als een continue stochastische variabele, met een kansverdeling die onafhankelijk is van de betrokken klanten. Veelal worden situaties beschouwd waarin de opeenvolgende tussenaankomsttijden statistisch onafhankelijk zijn. Samengevat beschouwt men dus vaak onafhankelijke gelijk verdeelde tussenaankomsttijden. Complexere systemen zijn echter ook mogelijk.

In het eenvoudigste geval komt op elk aankomsttijdstip slechts één klant het systeem binnen; men spreekt dan van een "enkelvoudig aankomstproces". Men kan echter ook "samengestelde aankomstprocessen" beschouwen, waarin op elk aankomsttijdstip meer klanten als groep het systeem binnenkomen. Zo'n groep klanten wordt een "bulk" genoemd. Het aankomstproces wordt dan door zowel de verdeling van de tussenaankomsttijden, als de verdeling van de grootte van de bulk bepaald.

Verwerking

De verwerking wordt gekarakteriseerd door de verwerkingstijd, de tijd die een klant nodig heeft om in de verwerkingseenheid bediend te worden. In veel gevallen worden ook deze tijden als contiue i.i.d. toevalsgrootheden gemodelleerd, maar een differentiëring naar types van klanten is mogelijk. Een andere karakteristiek is het aantal aanwezige kanalen (loketten, bedieningseenheden). Wanneer er meer dan een aanwezig is, kunnen deze volgens dezelfde verdeling werken, maar ook kan elk kanaal een andere verdeling van de verwerkingstijden hebben. Tenslotte is ook de wachtrijdiscipline karakteristiek voor de verwerking. Enkele voorbeelden zijn first-come, first-serve (FCFS), waarbij klanten worden bediend in volgorde van aankomst, last-come, first-serve (LCFS), waarbij de laatste klant eerst bediend wordt en random selection for service (RSS) waarbij elke klant eenzelfde kans heeft aan bod te komen. Daarnaast zijn ook strategieën met prioriteiten mogelijk.

Capaciteit

De capaciteit of bufferruimte geeft aan hoeveel klanten tegelijk in het systeem kunnen aanwezig zijn, dus zowel in verwerking als in de wachtrij. Wanneer men een oneindige capaciteit aanneemt, kan elke klant die aankomt toegelaten worden om bediend te worden of om in een wachtrij te komen. Bij een eindige capaciteit kan overflow optreden.

Verkorte notatie

David G. Kendall introduceerde in 1951 een A|B|m-notatie om wachtrijsystemen en hun karakteristieken te beschrijven.^[1] Deze notatie duidt een wachtrijsysteem aan met m servers, de letters A en B beschrijven de distributies van de interarrivaltijden en de bedieningstijden door volgende symbolen te gebruiken:

M : exponentiële distributie. M is de afkorting van memoryless (geheugenloos) of Markoviaans.
E_r : Erlang-verdeling van de orde r
H_r : hyperexponentiële verdeling met r fasen
D : deterministisch, dus een gegeven waarde zonder toevalsfluctuaties
U : uniforme verdeling
G : algemene distributie (G van general), de verdeling is niet nader gespecifieerd.

Later werd deze notatie uitgebreid. Gebruikt men vijf symbolen in een notatie van de vorm A|B|m|K|M, dan stelt K de opslagcapaciteit van het systeem voor, en M de grootte van de klantenpopulatie. Zijn deze grootheden niet gegeven, dan zijn ze oneindig, of eventueel niet nader bepaald. Men kan nog een zesde component aan de Kendall-notatie toevoegen, namelijk de wachtrijdiscipline die wordt toegepast, zoals:

FCFS : first-come, first-serve
LCFS : last-come, first-serve
RSS : random selection for service
PR : priority
GD : general discipline
PS : processor sharing

Wordt de strategie niet vermeld, dan onderstelt men vaak FCFS, of is deze niet relevant.

De notatie M|G|4|200|800|RSS specifieert bijvoorbeeld een wachtrijsysteem met exponentieel verdeelde tussenaankomsttijden, algemene verwerkingstijden, 4 bedieningsstation, een opslagcapaciteit van 200 klanten, een populatie van 800 mogelijke klanten en een RSS strategie.

Komen klanten in een bulk het systeem binnen, dan kan de Kendall notatie uitgebreid worden als A^(G)|B|m, waarbij G de verwijst naar de verdeling van de bulkgrootte.

Grootheden

De wachtrijtheorie zal systemen die formeel beschreven zijn, analyseren met behulp van enkele wiskundige en statistische grootheden. Bepaalde kenmerken en eigenschappen die men daaruit kan afleiden blijken typerend voor veel wachtrijen. Andere karakteristieken worden slechts voor specifieke gevallen geanalyseerd.

Beschouw voor de verklaring van enkele grootheden een algemeen systeem van het type G|G|m. De tussenaankomsttijden en bedieningstijden hebben dus een algemene, niet nader gespecificeerde verdeling. Veronderstel bovendien dat deze onderling ook statistisch onafhankelijk zijn. Het systeem heeft m kanalen en de bedieningsstrategie is willekeurig. De volgende grootheden zijn algemeen kenmerkend voor de systemen in de wachtrijtheorie:

$C_{n}$ = de n-de klant die aankomt bij het systeem.
$\tau _{n}$ = het aankomsttijdstip van C_n waarbij $\tau _{0}=0$ .
$t_{n}$ = de tussenaankomsttijd tussen C_n-1 en C_n = $\tau _{n}-\tau _{n-1}$ , dus $t_{1}=\tau _{1}$ .
$x_{n}$ = de bedieningstijd (servicetijd) die voor C_n nodig is.

Wanneer men aanneemt dat de tussenaankomsttijden onafhankelijke gelijk verdeelde stochastische variabelen zijn, dan kan men hun kansverdeling voorstellen door de cumulatieve kansverdeling:

A(t)=\operatorname {P} [t_{n}\leq t]

met, indien deze bestaat, de bijbehorende kansdichtheid

a(t)={\frac {d}{dt}}A(t)

Men introduceert de grootheid $\lambda$ , de aankomstintensiteit, die het gemiddelde aantal aankomsten per tijdseenheid voorstelt. Stelt men een willekeurige tussenaankomsttijd voor door ${\tilde {t}}$ , dan vindt men via de gemiddelde waarde van deze tussenaankomsttijd:

\operatorname {E} [{\tilde {t}}]={\frac {1}{\lambda }}

Wanneer men analoog de verwerkingstijden i.i.d. onderstelt, kan men hun cumulatieve distributiefunctie aanduiden als:

B(x)=\operatorname {P} [x_{n}\leq x]

met, indien deze bestaat, de bijbehorende kansdichtheid

b(x)={\frac {d}{dx}}B(x)

De grootheid $\mu$ , de verwerkingsintensiteit, geeft het gemiddeld aantal klanten dat een server per tijdseenheid verwerkt, indien deze bezig is. Stelt men een willekeurige tussenaankomsttijd voor door ${\tilde {x}}$ , dan vindt men via de gemiddelde waarde van deze tussenaankomsttijd:

\operatorname {E} [{\tilde {x}}]={\frac {1}{\mu }}

De grootheden t_n en x_n kunnen worden beschouwd als "ingangswaarden" van het systeem, zij bepalen volledig de tijdsevolutie van het wachtrijsysteem. Andere grootheden worden in de wachtrijtheorie van deze grootheden afgeleid. Enkele kunnen zijn:

w_n = de wachttijd van C_n, de tijd die een klant in de wachtrij doorbrengt
s_n = de systeemtijd van C_n, de tijd die een klant in het systeem doorbrengt. Voor elke klant is duidelijk dat s_n = w_n + x_n.

Wanneer een systeem lange tijd in werking is, en de beginvoorwaarden voorbij zijn, kan na zekere tijd een regimetoestand bereikt worden, waarbij de wacht- en systeemtijden van een willekeurige klant aan een distributie zullen voldoen. Men kan deze tijd aanduiden met respectievelijk de toevalsgrootheden ${\tilde {w}}$ en ${\tilde {s}}$ , die de volgende cumulatieve kansverdelingsfuncties bezitten:

W(y)=\operatorname {P} [{\tilde {w}}\leq y]

en

S(y)=\operatorname {P} [{\tilde {s}}\leq y]

de gemiddelde waarden zijn dan

W=\operatorname {E} [{\tilde {w}}]

en

T=\operatorname {E} [{\tilde {s}}]

,

dus:

W = de gemiddelde tijd die een klant doorbrengt in de wachtrij
T = de gemiddelde tijd die een klant doorbrengt in het systeem

N(t) = het aantal klanten in het systeem op het tijdstip t. Deze functie is een stochastisch proces.

Bereikt het systeem een regimetoestand, dan wordt de verdeling van N(t) onafhankelijk van de precieze t-waarde, of wordt een soort tijdsgemiddelde van deze verdeling bereikt. De limiettoevalsgrootheid is dan:

N = de systeembevolking op een willekeurig tijdstip in regimetoestand, de gemiddelde waarde ${\bar {N}}=\operatorname {E} [N]$ is het gemiddeld aantal klanten in het systeem.

U(t) = de werkachterstand op tijdstip t, dit is te totale bedieningstijd die nog nodig is om het systeem vrij te maken van alle klanten die op dat tijdstip t aanwezig zijn. Indien U(t) > 0 is het systeem bezet, is U(t) = 0, dan is het systeem werkloos of ledig.

Stelling van Little

Een fundamenteel resultaat in de wachtrijtheorie is de Stelling van Little, die luidt:

{\bar {N}}=\lambda \cdot T

Met de definities van de grootheden zoals hierboven.

PASTA-eigenschap

Een eigenschap die in wachtrijtheorie vaak wordt gebruikt, is de PASTA-eigenschap, wat staat voor Poisson Arrivals See Time Averages. Deze eigenschap zegt dat de verdeling van het aantal klanten in een systeem bij aankomst van een nieuwe klant gelijk is aan de verdeling van het aantal klanten op een willekeurig tijdstip. De PASTA-eigenschap is een belangrijk hulpmiddel in de analyse van veel wachtrijsystemen.

Bezettingsgraad

Een belangrijke parameter in het onderzoek omtrent wachtrijsystemen is de gemiddelde bezettingsgraad ρ van een systeem. Deze bezettingsgraad heeft de verhouding van de hoeveelheid werk die een systeem gemiddeld binnenkomt, tot de maximale hoeveelheid werk die het systeem kan uitvoeren. Is deze bezettingsgraad kleiner dan één, dan is het systeem stabiel, en kan het het binnenkomend werk aan, is de bezettingsgraad groter dan één, dan is het systeem instabiel en zal werk zich opstapelen.

Netwerken van wachtrijen

Wachtrijen kunnen aan elkaar gekoppeld worden, zodat netwerken gevormd worden. Klanten die vertrekken uit één wachtrijsysteem gaan vervolgens naar de wachtrij van een volgend wachtrijsysteem. De netwerken kunnen in twee klassen verdeeld worden: open en gesloten netwerken. Open netwerken hebben een externe ingang en klanten hebben een externe eindbestemming. Bij gesloten netwerken komt er terugkoppeling voor en staat het netwerk volledig op zichzelf. De klanten blijven dan binnen het netwerk circuleren.

Deze netwerken zijn vaak moeilijk analytisch te berekenen. Een belangrijke klasse zijn Jackson netwerken, waar men via decompositietechnieken toch relatief eenvoudig eigenschappen kan afleiden.

Toepassingen

De wachtrijtheorie heeft tal van voorbeelden en praktische toepassingen. Een overbekend voorbeeld is het postkantoor, waar klanten aanschuiven aan loketten. Men kan met wiskundige modellen bijvoorbeeld berekenen hoeveel extra kassa's een supermarkt nodig heeft, of wat de beste afstelling van een verkeerslicht is.

Bij de inrichting van computersystemen, communicatienetwerken en productiesystemen kent de wachtrijtheorie een belangrijke toepassing. Inwendig kunnen in computersystemen de aanvragen voor input/output-verwerking, of voor taken die wachten op processortijd als een wachtrij gemodelleerd worden. In de telecommunicatie treden wachtrijen op bij telefoonoproepen die op een vrije lijn in de centrale wachten, digitale berichten die op een vrije communicatiekanaal wachten, enzovoort.

Externe link

Kennislink filesimulatie

↑ Arnold O. Allen, Probability, Statistics and Queueing Theory with Computer Science Applications, 2de uitgave Academic Press 1990, ISBN: 0-12-051051-0.

[1] Arnold O. Allen, Probability, Statistics and Queueing Theory with Computer Science Applications, 2de uitgave Academic Press 1990, ISBN: 0-12-051051-0.

[1]