Wachtrijtheorie

De wachtrijtheorie of wachtlijntheorie 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. Agner Erlang, een Deense ingenieur die voor een telefoonmaatschappij in Kopenhagen werkte, publiceerde in 1909 het eerste artikel over wachtrijtheorie.

Wachtrijsystemen[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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 dat al in het systeem aanwezig is, een invloed zal hebben op de aankomststroom van nieuwe klanten.

Aankomstproces[bewerken | brontekst bewerken]

Het aankomstproces beschrijft hoe en met welke intensiteit 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 of interarrivaltijd, 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 i.i.d. 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[bewerken | brontekst bewerken]

De verwerking of bediening wordt gekarakteriseerd door de verwerkingstijd of bedieningstijd, de tijd die een klant nodig heeft om in de verwerkingseenheid bediend te worden. In veel gevallen worden ook deze tijden als continue onderling onafhankelijke toevalsvariabelen gemodelleerd, maar een differentiëring naar type klant 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. Ten slotte is ook de wachtlijndiscipline 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[bewerken | brontekst bewerken]

De capaciteit of bufferruimte geeft aan hoeveel klanten tegelijk in het systeem aanwezig kunnen zijn, dus zowel in verwerking als in de wachtrij. Als 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[bewerken | brontekst bewerken]

David G. Kendall introduceerde in 1951 een notatie in de vorm A/B/m om wachtrijsystemen en hun karakteristieken te beschrijven.^[1] Een A/B/m-systeem duidt een wachtrijsysteem aan met m servers, waarin de letters A en B de verdelingen beschrijven van de tussenaankomsttijden en de bedieningstijden. Voor de letters A en B kunnen de volgende symbolen gebruikt worden:

M : voor de exponentiële verdeling. M is de afkorting van memoryless (geheugenloos) of Markoviaans.
E_r : voor de Erlang-verdeling van de orde r
H_r : voor de hyperexponentiële verdeling met r fasen
D : voor een deterministische of gedegenereerde verdeling
U : voor de uniforme verdeling
G : voor een willekeurige, niet nader gespecificeerde verdeling (G van het Engelse 'general')

Later werd deze notatie uitgebreid door het gebruik van vijf symbolen, dus in de vorm A/B/m/K/M. Daarin 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
SPT : shortest processing time first

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

De notatie M/G/4/200/800/RSS specificeert 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 als bulk het systeem binnen, dan kan de Kendall-notatie uitgebreid worden tot A^(G)/B/m, waarbij G de verwijst naar de verdeling van de bulkgrootte.

Grootheden[bewerken | brontekst bewerken]

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}$ ; $T_{n}=\tau _{n}-\tau _{n-1}$ , dus $T_{1}=\tau _{1}$ .
$X_{n}$ : de bedieningstijd (servicetijd) die voor $C_{n}$ nodig is.

Als men aanneemt dat de tussenaankomsttijden onderling onafhankelijk en gelijkverdeeld zijn, wordt hun kansverdeling gegeven door de enkele verdelingsfunctie:

A(t)=\operatorname {P} (T_{n}\leq t)

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

\operatorname {E} ({\tilde {t}})={\frac {1}{\lambda }}

Als de verwerkingstijden gelijkverdeeld verondersteld worden, hebben alle dezelfde verdelingsfunctie:

B(x)=\operatorname {P} (X_{n}\leq x)

De grootheid $\mu$ , de verwerkingsintensiteit, is het verwachte aantal klanten die een server per tijdseenheid kan verwerken. Voor de verwachte waarde van een tussenaankomsttijd ${\tilde {x}}$ geldt dan:

\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 ontwikkeling in de tijd 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 de $n$ -de klant in de wachtrij doorbrengt
$S_{n}$ : de systeemtijd van $C_{n}$ , de tijd die de $n$ -de 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 stationaire toestand (regimetoestand) bereikt worden, waarbij zowel de wacht- als de systeemtijd van een willekeurige klant een vaste verdeling hebben. Men kan deze tijden aanduiden met respectievelijk de toevalsgrootheden ${\tilde {W}}$ en ${\tilde {S}}$ , met verdelingfuncties:

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

en

F_{\tilde {S}}(s)=\operatorname {P} ({\tilde {S}}\leq s)

Voor de respectievelijke verwachtingswaarden schrijft men wel

W=\operatorname {E} ({\tilde {W}})

en

S=\operatorname {E} ({\tilde {S}}]

,

dus:

$W$ is de verwachte tijd die een klant doorbrengt in de wachtrij
$S$ is de verwachte tijd die een klant doorbrengt in het systeem

Het stochastische proces $N(t)$ is het aantal klanten in het systeem op het tijdstip $t$ .

Bereikt het systeem een stationaire toestand, dan wordt de verdeling van $N(t)$ onafhankelijk van het tijdstip; er wordt een soort tijdsgemiddelde van deze verdeling bereikt. De limiettoevalsgrootheid is dan:

$N$ : de systeembevolking op een willekeurig tijdstip in regimetoestand, de verwachte waarde $\operatorname {E} (N)$ is het verwachte aantal klanten in het systeem.
$U(t)$ : de werkachterstand op tijdstip $t$ , dit is de totale bedieningstijd die nog nodig is om het systeem vrij te maken van alle klanten die op dat tijdstip aanwezig zijn. Indien $U(t)>0$ is het systeem bezet, is $U(t)=0$ , dan is het systeem werkloos of ledig.

Stelling van Little[bewerken | brontekst bewerken]

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

\operatorname {E} (N)=\lambda \cdot T

Met de definities van de grootheden zoals hierboven.

Zie Stelling van Little voor een uitgebreidere beschrijving van deze stelling

PASTA-eigenschap[bewerken | brontekst bewerken]

Een eigenschap die in wachtlijntheorie 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 wachtlijnsystemen.

Bezettingsgraad[bewerken | brontekst bewerken]

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

Zie Bezettingsgraad voor een uitgebreidere bespreking van deze bezettingsgraad

Netwerken van wachtlijnen[bewerken | brontekst bewerken]

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.

Typen[bewerken | brontekst bewerken]

Birth-death-wachtlijnsysteem: zo'n systeem kan beschreven worden met behulp van geboorte- en sterfteproces.

Toepassingen[bewerken | brontekst bewerken]

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 vrij communicatiekanaal wachten, enzovoort.

Externe link[bewerken | brontekst bewerken]

Kennislink filesimulatie

Noten[bewerken | brontekst bewerken]

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

Zie de categorie Queueing theory van Wikimedia Commons voor mediabestanden over dit onderwerp.

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

[1]