Wachtrijtheorie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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]

Structuur van een wachtlijnsysteem

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]

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]

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]

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 of interarrivaltijd, en modelleert deze als een continue toevalsgrootheid, 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]

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 continue i.i.d. toevalsgrootheden 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. Tenslotte 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]

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

Verkorte notatie[bewerken]

David G. Kendall introduceerde in 1951 een A|B|m-notatie om wachtlijnsystemen 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:

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
  • SPT : shortest processing time first

Wordt de strategie niet vermeld, dan veronderstelt men vaak FCFS, of is deze 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 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[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 Cn waarbij \tau_{0} = 0.
  • t_n: de tussenaankomsttijd tussen Cn-1 en Cn = \tau_n - \tau_{n-1} , dus t_{1} = \tau_{1}.
  • x_n: de bedieningstijd (servicetijd) die voor Cn 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, 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 tn en xn 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 distributiefuncties 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[bewerken]

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

\bar{N} = \lambda \cdot T

Met de definities van de grootheden zoals hierboven.

1rightarrow blue.svg Zie Stelling van Little voor een uitgebreidere beschrijving van deze stelling

PASTA-eigenschap[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]

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 éé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.

1rightarrow blue.svg Zie Bezettingsgraad voor een uitgebreidere bespreking van deze bezettingsgraad

Netwerken van wachtlijnen[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]

Toepassingen[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 vrije communicatiekanaal wachten, enzovoort.

Externe link[bewerken]

Noten[bewerken]

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