Wachtrijtheorie Hester Vogels en Franziska van Dalen 11 juni 2013
1
1
Inleiding
Een mens wacht gemiddeld 15.000 uur in zijn leven. Dit is bijvoorbeeld in de rij bij de kassa van een winkel, aan de telefoon bij een informatienummer, in de rij voor een autowasstraat, maar ook in de wachtkamer van een ziekenhuis. De wiskunde doet uitspraken over wachtrijen met als doel de wachttijd te verkleinen. Voor klanten is lang wachten namelijk vervelend, maar ook bedrijven willen bijvoorbeeld hun personeel het meest effici¨ent inzetten, want tijd is geld. In dit dictaat wordt de basis van wachtrijtheorie behandeld. Er wordt vooral ingegaan op de begrippen die nodig zijn om een model van een wachtrijsysteem te beschrijven. Verder wordt er met die begrippen en een aantal stellingen duidelijk gemaakt hoe bijvoorbeeld de gemiddelde wachttijd berekend kan worden. In het eerste deel wordt duidelijk welke raakvlakken wachtrijtheorie met de kansrekening heeft. De Poissonverdeling wordt hierbij nog eens herhaald. Daarna wordt er een aantal variabelen ge¨ıntroduceerd en wordt er duidelijk hoe er met behulp van evenwichtskansen gemiddelden van deze variabelen bepaald kunnen worden. In het tweede deel wordt er nog een nieuwe variabele ge¨ıntroduceerd, waarmee de berekeningen eenvoudiger worden. Verder wordt het verschil tussen wachtrijen met een eindige en oneindige capaciteit uitgelegd. Ook wordt het duidelijk waarom kassameisjes vaak 20 procent van de tijd niets te doen hebben. Ten slotte wordt bewezen dat het gemiddelde aantal klanten in een eindige wachtrij kleiner is dan in een oneindige wachtrij.
2
2
Modelmatige beschrijving van een wachtrij
In de wachtrijtheorie beschrijft men met behulp van een wiskundig model een wachtrijsysteem en bestudeert daarmee verschillende verschijnselen die zich in een wachtrij voordoen. In een wachtrijsysteem is er een groep klanten die een dienstverlening verwacht van een verwerkingseenheid. De klanten komen op verschillende tijdstippen aan en de verwerkingseenheid handelt die klanten in een bepaalde tijdsduur af. Wanneer er meer klanten aankomen dan de verwerkingseenheid kan verwerken, ontstaan er wachtrijen. Schematisch ziet een wachtrijsysteem er als volgt uit:
De verwerkingseenheid kan uit ´e´en of meerdere bedieningsstations bestaan. Bij een postkantoor zijn deze bedieningsstations bijvoorbeeld de loketten. Deze bedieningsstations kunnen allemaal ´e´en klant per keer helpen en werken parallel. Als alle bedieningsstations bezet zijn moet de klant in de wachtrij staan. De lengte van een wachtrij is afhankelijk van twee processen: het aankomstproces en het verwerkingsproces. Het aankomstproces beschrijft hoeveel klanten er per tijdseenheid binnenkomen. Vaak wordt er gekeken naar de tijd die tussen twee opeenvolgende aankomsten zit, de tussenaankomsttijd. Het verwerkingsproces beschrijft hoeveel tijd een verwerkingseenheid per klant nodig heeft, de verwerkingstijd. Deze processen worden allebei als een kansverdeling gemodelleerd. Er wordt dus uitgegaan van een gemiddelde tussenaankomsttijd en verwerkingstijd. Men zoekt vervolgens naar een kansverdeling die goed aansluit bij de werkelijkheid. Een ander aspect bij wachtrijtheorie is de capaciteit. Waar bij een oneindige capaciteit een wachtrij oneindig lang kan worden, kan bij een eindige capaciteit een overflow optreden. Om de karakteristieken van een wachtrijsysteem de beschrijven, wordt een verkorte notatie gebruikt: de A|B|S|N -notatie. De A staat voor de kansverdeling van de tussenaankomsttijden, de B voor de kansverdeling van de verwerkingstijden, de S is het aantal bedieningsstations en de N de capaciteit van de wachtruimte. Indien N oneindig is wordt deze weggelaten. De A en de B kunnen allerlei kansverdelingen aannemen, zoals de exponenti¨ele verdeling, de Erlangverdeling en de uniforme verdeling. In dit dictaat wordt er gekeken naar wachtrijsystemen waarbij de tussenaankomsttijden en verwerkingstijden (negatief) exponentieel verdeeld zijn.
3
3
Kansverdelingen
In dit hoofdstuk wordt duidelijk waarom de exponenti¨ele verdeling een logische kansverdeling is voor de processen bij wachtrijen. Als eerste wordt ingegaan op de Poissonverdeling en vanuit daar wordt de overstap gemaakt naar de exponenti¨ele verdeling. De Poissonverdeling klinkt de lezer waarschijnlijk bekend in de oren van het tweedejaarsvak Kansrekening. Deze verdeling beschrijft situaties waarin bepaalde voorvallen zich met enige gemiddelde regelmaat voordoen. Hierbij wordt uitgegaan van een gegeven tijdsinterval, volume, afstand, oppervlakte et cetera. Voorbeelden van dit soort situaties zijn het aantal telefoontjes dat iemand op een dag krijgt, het aantal naaldbomen in een stuk bos en het aantal typefouten op een pagina. Ook het aantal klanten dat per uur een winkel binnenkomt kan worden beschreven met een Poissonverdeling. In de wachtrijtheorie is er sprake van situaties met een gegeven tijdsinterval. Bij deze situaties kan men wiskundig kansmodel opstellen voor het aantal voorvallen in dat gegeven tijdsinterval, zodat men bijvoorbeeld de kans kan bepalen dat er op een koopavond meer dan honderd klanten de winkel bezoeken. Om een situatie met een Poissonverdeling te beschrijven moet er bekend zijn wat het gemiddelde aantal voorvallen is; dit wordt dan bijvoorbeeld empirisch bepaald. Men kan ervan uit gaan dat het gemiddelde aantal voorvallen evenredig is met de lengte van het tijdsinterval. Als er bijvoorbeeld per uur gemiddeld zes klanten binnenkomen, komen er per twee uur gemiddeld twaalf klanten binnen. Het gemiddelde aantal voorvallen in een tijdsinterval van lengte τ is dus gelijk aan λτ , waarbij λ de evenredigheidsfactor is. Deze λτ korten we af als α. Als X de stochastische variabele is die het aantal voorvallen telt, dan is volgens de Poissonverdeling de kans dat er precies k voorvallen plaatsvinden (met k een natuurlijk getal): αk −α e k! Dat de Poissonverdeling soms zeer goed met de werkelijkheid overeen blijkt te komen, is te zien aan het volgende voorbeeld. Er is over een periode van 20 jaar door 10 legercorpsen jaarlijks het aantal dodelijke slachtoffers door de trap van een paard gemeld. De 200 meldingen zijn in de volgende tabel gerangschikt naar de gemelde aantallen doden: P (X = k) =
k 0 1 2 3 4 ≥5
n(k) 109 65 22 3 1 0
Met deze tabel kunnen we het gemiddelde aantal slachtoffers bepalen: 1 (0 · 109 + 1 · 65 + 2 · 22 + 3 · 3 + 4 · 1) = 0.61 200 Als we nu de Poissonverdeling nemen met α = 0.61 als parameter en we deze kansen vermenigvuldigen met 200, zien we dat deze aantallen zeer goed overeenkomen met de geregistreerde gegevens: α=
4
k 0 1 2 3 4 ≥5
n(k) 109 65 22 3 1 0
200 · P (X = k) 108.7 66.3 20.2 4.1 0.6 0.1
Aangezien de Poissonverdeling alleen afhankelijk is van α, noemen we de verdeling geheugenloos. Dat betekent dat het aantal voorvallen dat in het verleden is opgetreden geen invloed heeft op het aantal voorvallen dat in het heden optreedt. In plaats van het aantal voorvallen per tijdseenheid, kunnen we ook kijken naar de tijdsduur tussen twee voorvallen. Zo is bijvoorbeeld de kans dat er in een uur gemiddeld nul voorvallen plaatsvinden gelijk aan de kans dat de tijd tussen twee voorvallen groter is dan een uur. Als we uitgaan van een Poissonverdeling met een gemiddeld aantal voorvallen µ gedurende een tijdsinterval van lengte t, dan geldt in het algemeen: P (T > t) = P (X = 0) =
µt0 −µt e = e−µt 0!
Dan: P (T ≤ t) = 1 − P (T > t) = 1 − e−µt Dit is de negatief-exponenti¨ele verdeling met parameter µ. In plaats van bijvoorbeeld het gemiddeld aantal klanten per uur te beschrijven met de Poissonverdeling, beschrijven we nu de gemiddelde tijdsduur tussen twee klanten. De tussenaankomsttijd van arriverende klanten kan dus beschreven worden met de negatief-exponenti¨ele verdeling. Ook de verwerkingstijd aan een loket is te beschrijven met deze kansverdeling. De tijd die nodig is om een klant te bedienen duurt niet altijd even lang. Veel klanten kunnen snel afgehandeld worden, maar er zijn ook klanten die meer tijd vragen. De kansverdeling is daarom niet evenwichtig zoals een normale verdeling. Intu¨ıtief kunnen we ons voorstellen dat de klanten op bepaalde tijdstippen het loket verlaten wanneer ze bediend zijn. Het voorval dat een klant het loket verlaat kan weer beschreven worden met een Poissonverdeling. De tijd tussen twee klanten die het loket verlaten kan dan beschreven worden met de negatief-exponenti¨ele verdeling. Deze tijd komt overeen met de tijd die het loket nodig heeft om een klant te helpen, als de loketbediende nooit stil zit. Daarom is ook de verwerkingstijd te beschrijven met de negatief-exponenti¨ele verdeling. We zien dus dat we zowel het aankomstproces als het verwerkingsproces kunnen beschrijven met de negatief-exponenti¨ele verdeling. Aan de hand hiervan kan een wiskundig model worden opgesteld om uitspraken te doen over de lengte van de wachtrij, de gemiddelde verblijfsduur van een klant in het systeem, et cetera.
5
4
Het overgangsdiagram
In de wachtrijtheorie gebruikt men een overgangsdiagram om aan te geven in welke toestanden een systeem zich kan bevinden en met welke snelheid het systeem in een bepaalde toestand overgaat. Een overgangsdiagram ziet er als volgt uit:
De toestanden zijn 0, 1, 2, 3, enzovoorts, wat wil zeggen dat er 0, 1, 2, 3, ... klanten aanwezig zijn in het systeem. Van deze klanten wordt er ´e´en klant geholpen terwijl de rest in de wachtrij staat. Als het systeem zich in toestand 3 bevindt, wordt er dus ´e´en klant geholpen en zijn er twee wachtenden. Het systeem verandert continu van toestand. Als er bijvoorbeeld niemand aanwezig is bevindt het systeem zich in toestand 0 en zodra er iemand binnen komt lopen bevindt het zich in toestand 1. Zodra die klant geholpen is en weer vertrekt, terwijl er ondertussen niemand binnen is gekomen, gaat het systeem weer naar toestand 0, en zo verder. De variabelen λ en µ bij de pijlen geven de snelheid van de toestandsverandering weer. De kans dat er in een klein tijdsinterval ∆t een toestandsverandering plaatsvindt is niet zo groot. Bij een groter interval is de kans een stuk groter. Stel dat er in een winkel gemiddeld tien klanten per uur binnenkomen. Als je dan gedurende ´e´en minuut bijhoudt hoeveel klanten een winkel binnenkomen, zouden dat nul klanten kunnen zijn, maar als je het tien minuten bijhoudt is de kans een stuk groter dat je ´e´en of twee klanten telt. De kans dat het systeem in een tijdsinterval ∆t van toestand k naar toestand k + 1 overgaat is evenredig met de lengte van het interval, waarbij de evenredigheidsconstante het gemiddelde aantal klanten dat per tijdseenheid binnenkomt is (λ). Men noemt λ ook wel de mate waarmee het systeem van toestand k naar toestand k + 1 wil. Er wordt verondersteld dat deze mate voor elke toestand gelijk is. Dit is vanwege de geheugenloosheid van het proces: het aantal klanten dat aankomt hangt niet af van het aantal klanten dat al in het systeem aanwezig is. Bij het vertrekproces (verwerkingsproces) is µ het gemiddelde aantal klanten dat per tijdseenheid vertrekt en daarom is µ de mate waarmee het systeem van toestand k naar toestand k − 1 wil. We gaan nu een overgangsdiagram maken bij het wachtsysteem van een bepaalde informatiebalie. Bij deze informatiebalie kunnen er maximaal drie wachtenden zijn, de vierde wachtende wordt verzocht om later terug te komen. Gemiddeld komen er vier klanten per uur binnen en elke klant doet er gemiddeld 10 minuten over om de informatie te verkrijgen die hij of zij nodig had. Om het overgangsdiagram te maken kiezen we eerst de tijdseenheid, in dit geval een uur. Omdat er maximaal drie wachtenden zijn en er ondertussen ´e´en klant geholpen wordt, kan het systeem kan zich in de volgende toestanden bevinden: 0, 1, 2, 3 of 4. We weten dat λ = 4, want er komen gemiddeld vier klanten per uur binnen. Per uur kunnen er verder gemiddeld 6 klanten worden afgehandeld, dus µ = 6. Het overgangsdiagram ziet er dan als volgt uit:
6
4.1
Stationaire toestanden en evenwichtskansen
Bij wachtrijen ontstaat er vaak een evenwichtssituatie: een stationaire toestand. Dat betekent dat de toestanden waarin het systeem zich bevindt met elkaar in evenwicht zijn. De kans dat je het systeem in een bepaalde toestand aantreft is dan constant. We illustreren dit met een voorbeeld. We bekijken een autowasstraat met de volgende overgangsdiagram:
Per uur komen er gemiddeld 3 auto’s aan en er vetrekken gemiddeld 6 auto’s. Een wasbeurt duurt dus gemiddeld 10 minuten. Het systeem kan zich in de toestanden 0, 1 of 2 bevinden, dus er is slechts plek voor ´e´en wachtende. Als er een auto aankomt terwijl er al een andere auto staat te wachten, zal deze auto moeten doorrijden. We gaan nu de kansen berekenen waarmee het systeem zich in toestand 0, 1 of 2 bevindt. Deze kansen noemen we respectievelijk P0 , P1 en P2 . Dit kun je ook zien als fracties van de tijd waarin het systeem zich in die toestand bevindt. In een evenwichtssituatie geldt dat de stroom uit toestand 0 gelijk is aan de stroom die toestand 0 binnenkomt. Hetzelfde geldt voor de toestanden 1 en 2. De stroom uit toestand 0 is het aantal keer dat het systeem per uur van toestand 0 naar toestand 1 overgaat. Dat is in dit voorbeeld het aantal auto’s per uur dat de wasstraat leeg aantreft. Aangezien er gemiddeld 3 auto’s per uur aankomen en de wasstraat in een fractie P0 van de tijd leeg is, is dit aantal gelijk aan 3 · P0 . De stroom die toestand 0 binnenkomt is het aantal keer dat het systeem per uur van toestand 1 naar toestand 0 overgaat. In dit voorbeeld is dat het aantal auto’s per uur dat de wasstraat leeg achterlaat. Aangezien er gemiddeld 6 auto’s per uur vertrekken en er in de wasstraat in een fractie P1 van de tijd ´e´en auto is, is dit aantal gelijk aan 6 · P1 . De in- en uitstroom moeten gelijk zijn, dus er moet gelden: 3 · P0 = 6 · P1 Zo’n evenwichtsvergelijking kunnen we ook voor de toestanden 1 en 2 maken. Voor toestand 1 zijn er twee in- en twee uitstromen. De vergelijkingen worden: 3 · P1 + 6 · P1 = 3 · P0 + 6 · P2 6 · P2 = 3 · P1 Er geldt echter dat een evenwicht van de toestanden 0 en 2 automatisch leidt tot een evenwicht van toestand 1. We kunnen dus alleen de eerste en derde vergelijking gebruiken. Daarnaast 7
zijn de evenwichtskansen uiteraard samen gelijk aan 1. Hieruit ontstaat een stelsel vergelijkingen met drie onbekenden: 3 · P0 = 6 · P1 6 · P2 = 3 · P1 P0 + P1 + P2 = 1 Deze vergelijkingen kunnen we oplossen en we vinden dan: 4 7 2 P1 = 7 1 P2 = 7 P0 =
We weten nu dat het systeem zich in 47 deel van de tijd zich in toestand 0 bevindt. Anders gezegd is de kans 47 dat een auto de wasstraat leeg aantreft. In het algemeen kunnen we bij elke overgangsdiagram de evenwichtsvergelijkingen opstellen en zo de evenwichtskansen vinden.
5
De Stellingen van Little
Twee stochastische variabelen die bij wachtrijtheorie van belang zijn, zijn L en W . L is het aantal klanten in het systeem, en W is de gemiddelde doorlooptijd. Hiermee wordt de gemiddelde tijd die een klant in een systeem doorbrengt bedoeld. Wanneer de subscript q bij de letter staat wordt niet het hele systeem, maar alleen de wachtrij bedoeld. Dus Lq is het aantal klanten in de wachtrij en Wq de gemiddelde wachttijd in de wachtrij. De verwachtingen van deze variabelen zijn E(L) en E(W ) en deze kun je ook als gemiddelden beschouwen. De eerste stelling van Little beschrijft de relatie tussen deze gemiddelden wanneer een wachtsysteem zich in een stationaire toestand bevindt: E(L) = λ · E(W ) E(Lq ) = λ · E(Wq ) De variabele λ is hier weer het gemiddelde aantal klanten dat per tijdseenheid het systeem binnenkomt. Om deze stelling aannemelijk te maken bekijken we een voorbeeld. Stel dat er een rij klanten in de rij voor een pashokje staat en dat er gemiddeld 6 klanten per uur aankomen. Een klant staat gemiddeld een kwartier in de wachtrij en is een kwartier aan het passen. In totaal brengt de klant dus een half uur in het systeem door. Met als tijdseenheid een uur geldt dus E(W ) = 12 . In een half uur zijn er gemiddeld 3 klanten binnengekomen (want λ = 6) en omdat het systeem zich in een stationaire toestand bevindt zijn er ook gemiddeld 3 klanten weggegaan. Per half uur wordt dus de gehele klantenpopulatie in het systeem vernieuwd. Daaruit kunnen we concluderen dat er gemiddeld 3 klanten in het systeem aanwezig zijn. Volgens de stelling geldt E(L) = λ · E(W ) = 6 · 12 = 3 dus het klopt. Een andere relatie is de relatie tussen E(W ) en E(Wq ). Deze relatie is erg vanzelfsprekend, 8
namelijk: de gemiddelde doorlooptijd is de som van de gemiddelde tijd in de wachtrij en de gemiddelde verwerkingstijd. De gemiddelde verwerkingstijd is gelijk aan µ1 aangezien µ het gemiddelde aantal klanten is dat per tijdseenheid verwerkt wordt. De gemiddelde doorlooptijd is dus: 1 E(W ) = E(Wq ) + µ Om te laten zien wat we met deze stellingen kunnen, kijken we nog eens naar het voorbeeld van de wasstraat. De evenwichtskansen in de wachtstraat waren P0 = 74 , P1 = 27 en P2 = 17 . Hieruit kunnen we het gemiddelde aantal auto’s in het systeem uitrekenen: E(L) = 0 · P0 + 1 · P1 + 2 · P2 = 0 + 1 ·
2 1 4 +2· = 7 7 7
Er kwamen gemiddeld 3 auto’s per uur aan, maar daarmee geldt niet dat λ = 3. Er komt namelijk een aantal auto’s de wasstraat niet binnen omdat deze bezet is. De kans dat een auto de wasstraat vol aantreft is P2 = 17 . Per uur vertrekken er dus gemiddeld 17 · 3 = 37 auto’s zonder wasbeurt. Daaruit volgt dat λ = 3 − 73 = 18 7 . We weten nu E(L) en λ en met de Stelling van Little kunnen we nu E(W ) uitrekenen: E(W ) =
E(L) = λ
4 7 18 7
=
2 9
Met een tijdseenheid van een uur is de gemiddelde doorlooptijd dus 29 · 60 = 13 13 . We weten dat een wasbeurt gemiddeld 10 minuten duurt, dus de gemiddelde tijd in de wachtrij volgt met de andere stelling: E(Wq ) = E(W ) − 10 = 3 31 minuut.
6
M/M/1
In dit hoofdstuk behandelen we het wachtrijsysteem M/M/1. Ter herinnering: deze afkorting betekent dat zowel het aankomstproces als het verwerkingsproces negatief-exponentieel verdeeld is en dat er 1 loket is. Daarnaast is er een oneindige capaciteit maar zoals eerder verteld noteren we dit niet. Eerst willen we nog een nieuw begrip introduceren, namelijk de bezettingsgraad ρ. De bezettingsgraad geeft het volgende aan: 1. De kans dat het loket bezet is. 2. De fractie van de tijd dat het loket bezet is. 3. Het gemiddelde aantal klanten aan het loket. In het M/M/1-systeem geldt dat ρ = µλ . Stel namelijk dat er per tijdseenheid gemiddeld λ klanten aankomen en er per tijdseenheid gemiddeld µ klanten geholpen kunnen worden, dan is de kans dat het loket bezet is µλ . Verder geldt er dat 1 − ρ de fractie van de tijd is dat het loket vrij is. We kunnen nu ook het gemiddelde aantal klanten aan het loket bepalen, namelijk: 0 · (1 − ρ) + 1 · ρ = ρ. Daarom is de bezettingsgraad ook te interpreteren als het gemiddelde aantal klanten aan het loket.
9
6.1
Evenwichtskansen
We gaan de evenwichtsvergelijkingen zoals behandeld in paragraaf 4.1 hier omschrijven naar een algemenere vorm. We stellen dat Pk de kans is dat het systeem in de evenwichtssituatie in de toestand k verkeert, dit betekent dat er k klanten in het systeem aanwezig zijn. We krijgen de volgende evenwichtsvergelijkingen: 0 1 2 .. .
in µP1 λP0 + µP2 λP1 + µP3 .. .
k .. .
λPk−1 + µPk+1 .. .
= = = .. .
uit λP0 λP1 + µP1 λP2 + µP2 .. .
⇒ ⇒ ⇒ .. .
λP0 λP1 λP2 .. .
= = = .. .
µP1 µP2 µP3 .. .
= .. .
λPk + µPk .. .
⇒ .. .
λPk .. .
= .. .
µPk+1 .. .
We vinden nu de volgende evenwichtskansen: P0 , P1 = ρP0 , . . . , Pk = ρk P0 , . . . We zien dus dat als P0 bekend is, alle evenwichtskansen bekend zijn. De kans P0 kunnen we berekenen uit het feit dat de som van alle evenwichtskansen gelijk moet zijn aan 1. Dit geeft: P0 + P1 + P2 + . . . = 1 P0 + ρP0 + ρ2 P0 + . . . = 1 P0 (1 + ρ + ρ2 + . . .) = 1 1 P0 = 1 1−ρ P0 = 1 − ρ Er geldt dus dat P0 = 1 − ρ, dit hebben we hierboven ook al gezien. Immers geldt er dat 1 − ρ de fractie van de tijd is dat het loket vrij is en dit is precies de kans dat er 0 klanten in het systeem zijn.
6.2
Wachtrij en wachttijden
Om de wachtrij en wachttijden te bepalen, hebben we nog enkele gegevens nodig. Deze gaan we in dit hoofdstuk behandelen. Zoals al eerder gezien, wordt het gemiddelde aantal klanten in het systeem aangeduid met E(L). We kunnen dit gemiddelde als volgt uitrekenen. Als de bezettingsgraad gelijk is aan ρ = µλ , dan geldt er dat: E(L) = 0P0 + 1P1 + 2P2 + . . . = ρP0 + 2ρ2 P0 + . . . = ρP0 (1 + 2ρ + . . .) = ρ(1 − ρ)(1 + 2ρ + . . .) = ρ(1 + ρ + ρ2 + . . .) 10
ρ 1−ρ λ µ−λ
= =
Nu we E(L) kennen, is het met de relaties van Little gemakkelijk om E(Lq ), E(W ) en E(Wq ) te bepalen. In een systeem met 1 loket en onbegrensde capaciteit geldt E(Lq ) = E(W ) = E(Wq ) =
λ2 µ2 − λµ 1 µ−λ λ 2 µ λµ
Voorbeeld: In een fabriek worden door de medewerkers defecte exemplaren van een bepaald apparaat van de lopende band genomen. Deze exemplaren worden vervolgens naar de afdeling kwaliteitszorg gestuurd. Gemiddeld worden 5 defecte exemplaren per uur van de band genomen. De afdeling kwaliteitszorg kan gemiddeld 8 defecte exemplaren per uur inspecteren. 1. Hoeveel procent van de tijd heeft de afdeling kwaliteitszorg niets te doen? • Er geldt: ρ = µλ = 58 , dus P0 = 1 − ρ = 38 . Dit betekent dat de afdeling gemiddeld 35.5% van de tijd zonder werk zit. 2. Hoeveel exemplaren liggen er gemiddeld per uur klaar om ge¨ınspecteerd te worden? • Er geldt dat E(Lq ) = te wachten.
λ2 µ2 −λµ
=
25 64−30
=
25 24 .
Er liggen dus gemiddeld
25 24
exemplaren
3. Wat is de kans dat er minstens 2 exemplaren gereed liggen voor inspectie? • De kans dat er minstens 2 exemplaren gereed liggen voor inspectie is gelijk aan de kans dat er minstens 3 exemplaren in het systeem aanwezig zijn. Deze kans is P3 + P4 + P5 + . . .. Deze kans is gelijk aan 1 − P0 − P1 − P2 = 1 − (1 − ρ) − ρ(1 − ρ) − ρ2 (1 − ρ) = ρ3 = 125 512 . 4. De snelheid van de lopende band wordt verdubbeld zodat er nu gemiddeld 10 defecte exemplaren per uur bij de afdeling kwaliteitszorg aankomen. Deze afdeling wordt uitgebreid en kan nu 12 exemplaren per uur inspecteren. Wat is in dit geval het antwoord op vraag 2? 100 = 25 • Er geldt nu ρ = 56 en E(Lq ) = 144−120 6 . Merk op dat de toename in de bezettingsgraad van 33% leidt tot een toename in de wachtrij van 300%.
Dit voorbeeld laat zien dat E(L) en E(Lq ) zeer snel toenemen als de bezettingsgraad tot 1 nadert. Hetzelfde geldt ook voor E(W ) en E(Wq ). 11
6.3
De economische kant
Iedereen kent wel het spreekwoord: tijd is geld. Dit betekent in de wachtrijtheorie dat wachten geld kost. Daarom werkt men in de economie met wachtrijmodellen om op basis daarvan de optimale inzet van mensen en machines te berekenen. We noemen een inzet van personeel en middelen optimaal als de daarmee gepaard gaande kosten minimaal zijn. In zo’n model moet men de kosten van de inzeet van extra personeel of machines afwegen tegen de kosten van het tijdverlies dat het gevolg is van lange wachttijden. Problemen waarbij men een keuze moet maken tussen alternatieve wachttijdsystemen heten wachttijdoptimalisatieproblemen.
7
M/M/1/N
In het vorige hoofdstuk hebben we gekeken naar het wachtrijsysteem M/M/1, deze heeft een onbeperkte capaciteit. Nu bekijken we het wachtrijsysteem M/M/1/N, hier geeft de N aan dat de capaciteit van het systeem beperkt is tot N klanten. Dit betekent dat als bijvoorbeeld de bakkerij vol staat, je vertrekt en een andere bakkerij zoekt of later weer terugkomt.
7.1
Evenwichtskansen
Een systeem met een capaciteit van N kan zich in N + 1 toestanden bevinden: het aantal in het systeem aanwezige klanten kan 0, 1, . . . , N zijn. We krijgen dus het volgende overgangsdiagram:
We vinden hierbij weer dezelfde evenwichtskansen als bij het wachtrijsysteem met onbeperkte capaciteit. Er geldt dus in een waachtrijsyteem met capaciteit N dat: Pk = ρk P0 met 0 ≤ k ≤ N . Hierbij noemen we PN de blokkeerkans. Immers heeft PN de kans weer dat er N personen in het systeem aanwezig zijn, het systeem is dan geblokkeerd. In een wachtrijsysteem met beperkte capaciteit werken we met een effectieve aankomstrate. Deze aankomstrate is anders dan de λ die we bij een wachtrijsysteem met onbeperkte capaciteit hadden. Er geldt namelijk nu: λe = λ(1 − PN ). Dit is als volgt te begrijpen: PN geeft je informatie over het gedeelte van de tijd dat het systeem geblokkeerd is. Stel nu dat PN is 0.5, dan is het systeem de helft van de tijd geblokkeerd. Als het systeem geblokkeerd is, komen de klanten die dan aankomen niet binnen en vertrekken dus weer. Stel dat λ = 10, dan komen er slechts 5 klanten binnen omdat het systeem de helft van de tijd geblokkeerd is. Met deze redenatie vinden we dat λe = λ(1 − PN ) De bezettingsgraad van een wachtrijsysteem met beperkte capaciteit is niet meer ρ = µλ . Immers komen niet allen klanten die aankomen ook het systeem binnen. We moeten hier de λ vervangen door de hierboven gevonden λe . We vinden dan dat de effectieve bezettingsgraad ρe =
λe λ(1 − PN ) = = ρ(1 − PN ) µ µ
12
is. Merk op dat zowel de aankomstrate als de bezettingsgraad nu van de capaciteit van het systeem afhangen. Net als bij het wachtrijsysteem kunnen we nu weer P0 berekenen. We vinden dan dat P0 =
1−ρ 1 − ρN +1
Met de bovenstaande formules voor de effectieve aankomstrate en bezettingsgraad vinden we tenslotte ρe = 1 − P0
7.2
Wachtrij en wachttijden
Ook bij een wachtrijsysteem met beperkte capaciteit kan je de wachtrij en de wachttijden bepalen. We maken daarbij gebruik van de somformule voor de eindige gemengde reeks: n+1 a + ar + ar2 + . . . + arn = a 1−r met r 6= 1. We nemen dan in ons geval dat a = P0 ρ en 1−r r = ρ. We vinden dan het volgende E(L) = 0P0 + 1P1 + . . . N PN = P0 ρ + 2ρ2 Po + . . . N ρN P0 = P0 ρ(1 + 2ρ + 3ρ2 + . . . N B N −1 ) ρ 1 − (N + 1)ρN + N ρN +1 = 1−ρ 1 − ρN +1 We kunnen dit gemiddelde vergelijken met het gemiddelde aantal klanten bij een systeem met onbeperkte capaciteit. Hier zie je dan dat het gemiddelde aantal klanten bij een systeem met beperkte capaciteit gelijk is aan het gemiddelde aantal klanten bij een onbeperk systeem N +N ρN +1 maal de factor 1−(N +1)ρ . Er geldt dat deze factor kleinter is dan 1 en dit betekent 1−ρN +1 dat het gemiddelde aantal klanten bij een wachtrijsysteem met beperkte capaciteit kleiner is dan bij een wachtrijsyssteem met onbeperkte capaciteit. Bewijs. We willen dat geldt
1−(N +1)ρN +N ρN +1 1−ρN +1
< 1. Hiervoor moet er gelden dat:
1 − (N + 1)ρN + N ρN +1 < 1 − ρN +1 −(N + 1)ρN + N ρN +1 < −ρN +1 N ρN +1 − N ρN − ρN
< −ρN +1
N ρN +1 + ρN +1 < N ρN + ρN (N + 1)ρ < N + 1 ρ < 1 Het klopt dat ρ =
λ µ
< 1, dus er is bewezen dat
1−(N +1)ρN +N ρN +1 1−ρN +1
< 1.
We kunnen E(Lq ), E(W ) en E(Wq ) weer op dezelfde manier berekenen als bij het wachtrijsysteem met onbeperkte capaciteit. We vinden dan E(Lq ) = E(L) − ρe 13
E(W ) = E(Wq ) =
14
E(L) λe E(Lq ) λe
8
Afsluiting
We hebben in dit dictaat laten zien waar wachtrijmodellen op gebaseerd zijn en welke begrippen hierbij voorkomen. Door twee soorten wachtrijmodellen verder uit te leggen, hebben we jullie inzicht willen geven in de wachtrijtheorie. Ook de economische kant is kort genoemd en hier geldt dat voor de bedrijven die gebruik maken van wachtrijmodellen de optimalisatie van een wachtrijmodel van belang is. Dit optimaliseren is de belangrijkste taak van wiskundigen die met wachtrijmodellen werken.
15
9
Opgaven
Opgave 1 Er is een winkel met 1 paskamer. Het is koopzondag en er komt gemiddeld om de 6 minuten een klant die wil gaan passen. Een medewerker hangt de gepaste kleding, die men niet wil kopen, weg en heeft bijgehouden dat een klant er gemiddeld 5 minuten over doet om te passen. Verder nemen we aan dat een klant vertrekt als er al 2 wachtenden staan. Deze klant komt dan op een later moment terug. a. Neem als tijdseenheid 1 uur. Teken het overgangsdiagram en bepaal de evenwichtskansen. b. Bepaal de gemiddelde tijd die een klant in de wachtrij doorbrengt. Je mag enkel gebruik maken van hoofdstuk 1 t/m 5.
Opgave 2 a. In paragraaf 7.1 wordt beweerd: Met de bovenstaande formules voor de effectieve aankomstrate en bezettingsgraad vinden we tenslotte ρe = 1 − P0 . Laat zien dat je met de volgende drie formules PN = ρN P0 , P0 =
1−ρ , 1 − ρN +1
ρe = ρ(1 − PN ) inderdaad de formule ρe = 1 − P0 kunt afleiden. b. Laat zien dat je bij opgave 1b gebruik hebt gemaakt van λe = λ(1 − PN ). c. Bepaal voor het voorbeeld uit vraag 1 ρe met de formule ρe = ρ(1 − PN ). En laat zien dat dit gelijk is aan 1 − P0 . Hoeveel procent van de tijd is het pashokje leeg? d. Laat voor het voorbeeld uit vraag 1 zien dat de formule P0 =
16
1−ρ 1−ρN +1
klopt.
10
Literatuurlijst
Bosch, Rob en Craats, Jan van de , 2001, Wachttijdtheorie, http://staff.science.uva.nl/ craats/Wachttijdtheorie.pdf Ridder, A.A.N., 2001, Kleine kansen en grote afwijkingen, http://personal.vu.nl/a.a.n.ridder/papers/31-ridder.pdf http://wwwhome.math.utwente.nl/ boucherierj/onderwijs/153088/153088sheetshc11.pdf
17
