Wachttijdtheorie
Beo-cases
Prof. dr N.M. van Dijk Dr H.J. van der Sluis
Een ogenblik geduld a.u.b.
Een ogenblik geduld ... (Uit Trouw artikel, 26 augustus 1998) Zeker een jaar van ons leven verdoen we onze tijd aan wachten. Bij de supermarkt, in de file of aan de telefoon: 'Al onze lijnen zijn bezet; een ogenblik geduld alstublieft'. Een verspild jaar, vindt iedereen. Nog enkele weken geleden lag half Nederland weliswaar te niksen aan het strand of in de achtertuin, maar nu de onthaasting weer voorbij is, is elke wachtminuut er één teveel. Dus zigzaggen we weer in de file en tussen de rijen voor de loketten. Natuurlijk is bij onze kassa altijd de papierrol op en blijken we achter een toerist te staan die geen kleingeld op zak heeft en geen Nederlands spreekt. En de trein vertrekt alleen dan op tijd wanneer wij een minuutje verlaat zijn. Over de psychologie van het wachten zijn hele verhandelingen te houden. Het is vooral een kwestie van beleving. De tijdschriften bij de kapper of het aperitiefje in het restaurant kunnen ertoe bijdragen dat men niet het idee heeft zijn tijd te verdoen. Maar de irritatie komt ook voort uit machteloosheid, uit het gevoel te zijn overgeleverd aan 'het systeem'. Niet weten bijvoorbeeld hoelang het nog gaat duren. In Londen is sinds een jaar of zes op bushaltes te lezen wanneer de volgende bus er aankomt. Enig effect op de wachttijden heeft dat niet gehad: die is nog steeds zo'n minuut of vijf. Maar vroeger dachten de Londenaren dat ze wel twaalf minuten stonden te wachten en sinds de meldingen zijn het er voor hun gevoel nog maar achteneenhalf. Ook pretparken hebben hun wachtrijen, maar daar heeft men de zaak omgedraaid en van de nood een deugd gemaakt. In het hoogseizoen staan bezoekers van de Efteling een groot deel van hun tijd in de rij voor de Python of andere topattracties. Markeringen langs de route geven aan hoe lang het nog wachten is. Hier heeft iedereen juist prima uitzicht op wat komen gaat. Soms zijn er voorprogramma's om de gasten in de goede stemming te brengen. En dat werkt: 85 procent vindt de attracties een wachttijd van soms anderhalf uur de moeite waard. Sterker nog, bij een vergelijkbaar Brits pretpark vond men de attracties mét wacht-voorpret leuker dan zonder. Alle psychologische verhandelingen draaien om die ene brandende vraag heen: waarom moeten wij überhaupt wachten? Waarom zorgt zo'n supermarkt of postkantoor niet gewoon voor voldoende kassa's of loketten? Men houdt daar toch wel bij hoeveel klanten per uur binnenkomen, en hoeveel tijd ieder vraagt? Stel dat een klant gemiddeld drie minuten nodig heeft; dan kan een lokettist er twintig per uur bedienen. Als er tweehonderd klanten per uur zijn, heb je dus aan tien loketten voldoende. Tenminste, dat zou je denken. Maar deze aanpak is een gegarandeerd recept voor lange wachtrijen, leert de queueing theory, de wiskunde van wachten. Een vreemd vakgebied waarin de intuïtie het regelmatig moet afleggen tegen de logica. Terug naar de wachtende rij van het postkantoor. De gestaag doorwerkende lokettist bedient twintig klanten per uur. Zoveel klanten komen er gemiddeld ook binnen, maar ze komen niet exact om de drie minuten. Bovendien zijn sommigen na een halve minuut al geholpen terwijl de eerder genoemde toerist tien minuten nodig heeft. Gevolg: het ene moment zijn er geen klanten en zit de brave medewerker uit zijn neus te peuteren en juist als die toerist aan de beurt is, komt er een groepje klanten. Er ontstaat een niet meer weg te werken rij - de lokettist kan zijn neuspeuter-minuutjes niet meer inhalen. Dat kan hij echter wel als de manager van het postkantoor daar tijd voor reserveert, als hij extra mensen aan het werk zet. Dus niet, bij tweehonderd klanten per uur, tien loketten van twintig per uur, maar bijvoorbeeld twaalf loketten. Daarmee verschaft hij de lokettisten adempauzes. Als de lokettist structureel pauzes krijgt ingelast tussen twee klanten, heeft hij niet alleen de mogelijkheid wachtrijen weg te werken, maar kan de klant ook variëren. Zoals gezegd, als
Universiteit van Amsterdam
1
Operationele Research & Management
iedereen op gezette tijden zou komen en evenveel servicetijd vroeg, waren er geen wachtrijen. Die ontstaan door de variaties. Maar zolang de klant tijdens pauzes van de lokettist arriveert, is hij meteen aan de beurt. En de pauzes staan ook toe dat klanten meer servicetijd dan gemiddeld vragen. Hoe groter de pauzes, des te groter is de kans dat de wachtrijen uitblijven. Een paar jaar geleden besloot de PTT om in de hoofdpostkantoren het systeem van afzonderlijke rijen voor afzonderlijke loketten af te schaffen. Dat leidde maar tot frustratie en ergernis: die andere rij die altijd sneller ging en die vervelende klant die voortdurend wisde. Tegenwoordig is er nog maar één wachtrij. Klanten trekken nummertjes en wie aan de beurt is, voegt zich bij het loket dat zojuist is vrijgekomen. Dat is eerlijker, vond de PTT. Iedereen wordt in volgorde van binnenkomst behandeld en er is geen snellere rij. Bovendien lijkt één lange rij sneller op te schieten. Het is echter de vraag of het ook daadwerkelijk sneller gaat. Bij een experiment op een postkantoor in Schiedam werden de klanten in vijf groepen ingedeeld: korte en lange geldhandelingen, korte en lange posthandelingen en andere handelingen. Iedereen trok nummertjes voor zijn 'eigen' loket, met die nuancering dat als één loket tijdelijk geen clientèle had, de medewerkers ook andere rijen zouden bedienen. In het één-rij-systeem was de wachttijd gemiddeld ruim vier minuten. Volgens (wachttijd)analyse kon iedereen erop vooruitgaan: de meesten een paar seconden tot een minuutje, maar de grote groep klanten met korte geldtransacties – opnemen en storten – zou al na anderhalve minuut weer buiten staan. Hoe kan dit? Laat U meenemen in de intrigerende wiskunde van het wachten. Prof. dr. N.M. van Dijk
Wachten!!! AAAARGH!!! Onderzoek (NIPO) wijst uit dat wachten ergernis nummer 1 is. Waar(op) moeten we al niet wachten: • • • • • • • • •
In postkantoren / banken In het ziekenhuis / op artsen In het verkeer (files) Informatie nummers In de supermarkt Op de levering van een nieuwe auto Bij reisorganisaties In pretparken Op vrienden
Universiteit van Amsterdam
2
Operationele Research & Management
Psychologische factoren De belangrijkste psychologische factoren die een rol spelen bij wachten zijn: • • • • •
Eerlijkheid (één rij systeem, geen voordringen, dus iedereen dezelfde gemiddelde wachttijd) Informatie (nog 78 wachtenden voor u, de trein komt over 10 minuten) Animatie (omgeving, muziek, literatuur, TV-scherm) Iets te doen hebben (neem een boek mee) Bezorgdheid (bij de dokter, mis ik nu niet mijn aansluiting)
Deze psychologische factoren beïnvloeden echter alleen de beleving tijdens het wachten maar niet de wachttijd zelf. Daarvoor zijn kwantitatieve factoren van belang. Kwantitatieve factoren Waarom moet er überhaupt gewacht worden? Er is toch voldoende capaciteit. Hoe kun je wachttijd verkorten? Wachten kan in essentie verklaard worden met behulp van onderstaande twee kwantitatieve factoren.
1. Capaciteit
Universiteit van Amsterdam
2.variabiliteit
3
Operationele Research & Management
Capaciteit Wachttijd formules Voor de meest eenvoudige situatie van een enkel loket gelden de volgende formules voor de gemiddelde verblijf- en wachttijd:
W= Wq: W:
1 C−A
Wq = S
en
F 1− F
gemiddelde wachttijd gemiddelde verblijftijd (= Wq + S) met
S: F: A: C:
gemiddelde bedieningstijd gemiddelde bezettingsgraad (= A / C) gemiddeldeaantal aankomsten per minuut bedieningscapaciteit (voltooiingen) per minuut
De afleiding van deze formules is in onderstaand kader te vinden. Wachttijd voorbeeld I • • •
Één server (loket) Random aankomsten A (per 10 min) Één minuut gemiddelde servicetijd per klant (S = 1 minuut)
A 4 5 8 9 9.5 9.9
Universiteit van Amsterdam
W 1.6 2 5 10 20 100
Wq 0.6 1 4 9 19 99
4
F 40% 50% 80% 90% 95% 99%
Operationele Research & Management
Wachten op één bediende
(Uit natuur en Techniek, december 1996, door prof. dr N.M. van Dijk)
D
W = (L+1) × S
e formule voor de wachttijd, of preciezer de verblijfstijd (= wachttijd + bedieningstijd), voor een faciliteit met een bediende luidt:
W=
S: gemiddelde bedieningsduur per klant = (A × W + 1) × S.
1 C−A
Met S = 1/C en
Waarbij:
F=A×S
W: gemiddelde verblijftijd in minuten per klant, A: aantal klanten dat per minuut arriveert, C: bedieningscapaciteit (aantal bedieningen dat gemiddeld maximaal voltooid kan worden) per minuut.
F: de aangeboden werklast per minuut = bezettingsgraad geldt dus: W=A×W×S+S=F×W+S
Hierbij wordt natuurlijkerwijze verondersteld dat A < C. de formule is volledig gebaseerd op gemiddelden A en C en doet een uitspraak over de gemiddelde verblijfstijd W. Bij een gemiddelde aankomstintensiteit van 9 klanten per 10 minuten en een gemiddelde bedieningstijd van 1 minuut per klant geldt: A = 0.9 en C = 1 zodat W = 1 / (1-0.9) = 10 minuten. In dit vrij realistische geval waarbij de bediende voor 90% van zijn tijd met werk belast is, geldt dus dat een klant voor 1 minuut bediening 9 minuten moet wachten.
Omdat F = A / C < 1 als fractie kan worden gezien, geldt eveneens: W = F x W + (1- F) x W, Als men de laatste twee gelijkheden vergelijkt, blijkt dus dat van de totale verblijfstijd W slechts de fractie (1-F) wordt besteed aan de eigen bedieningstijd S, zoals ook in het rekenvoorbeeld met A = 0.9 en C = 1 en dus F = 0.9 (90%). Oftewel,
Een formele afleiding van de wachttijdformule vereist in feite een nadere bespreking van impliciet veronderstelde zogenaamde exponentiële randomness alsmede stellingen uit de kansrekening. Een intuïtief inzichtelijk bewijs is echter vrij eenvoudig te geven. Essentieel hiertoe is de beroemde formule van Little:
S / W = 1-F. Omgezet betekent dit: W=
Voor
L=AxW
Wq:
L: gemiddeld aantal klanten dat zich in het systeem bevindt
de gemiddelde wachttijd (de q staat voor queue)
volgt nu
Deze relatie is eenvoudig in te zien als men L als werklast opvat en A als in- of outputintensiteit. Bijvoorbeeld, als gemiddeld per week A = 100 patiënten het ziekenhuis ingaan (en dus ook verlaten) en de gemiddelde verblijfsduur per patiënt W = 2.5 weken bedraagt, dan zullen op een willekeurig moment gemiddeld L = 100×2.5 = 250 patiënten in het ziekenhuis verblijven.
1 A = C C(C − A ) 1 A/C F = =S 1− F C (1 − A / C)
Wq = W − S = W −
Samenvattend: L = A W, W =
Voor de afleiding van de wachttijdformule merk nu vervolgens op dat een arriverende klant moet wachten totdat alle aanwezige klanten, L, geholpen zijn. De totale verblijfstijd, inclusief zijn eigen bediening, bedraagt voor een zojuist gearriveerde klant dus:
Universiteit van Amsterdam
S 1/C 1 = = 1 - F 1 - A/ C C - A
F 1 en Wq = S C−A 1− F
Dus de bezettingsgraad F leidt tot een vergrotingsfactor F / ( 1- F) voor de gemiddelde wachttijd Wq t.o.v. de gemiddelde bedieningstijd S.
5
Operationele Research & Management
Variabiliteit Wachttijd voorbeeld II Dit voor beeld illustreert het effect van variabiliteit in tussenaankomsttijden. Zo kan men terecht afvragen waarom zich bij een loket in bijvoorbeeld een postkantoor wachtrijen voordoen indien er gemiddeld per 5 minuten 4 klanten arriveren en elke klant gemiddeld 1 minuut bedieningstijd vergt. Er zou gemiddeld gezien zelfs nog één klant bij kunnen. Een eerste inzicht in deze vraagstelling wordt verschaft in Kader 1 aan de hand van drie situaties. Situatie 1 Veronderstel dat de klanten precies na 1.15 minuut van elkaar binnenkomen en dat de bedieningstijd van elke klant exact 1 minuut bedraagt. In dit geval bedraagt de gemiddelde wachttijd W = 0 minuten. Situatie 2 Veronderstel dat de klanten onafhankelijk van elkaar, dus ‘at random’ arriveren, zodat met gerede kans twee klanten binnen 1 minuut van elkaar kunnen arriveren. Met nog steeds een bedieningstijd van exact 1 minuut zal in een dergelijk geval minstens één van de klanten op de voorganger moeten wachten zodat in ieder geval W > 0 (in dit specifieke geval kan bepaald worden dat W = 2 minuten) als gevolg van de variatie (variabiliteit) in de tussen aankomsttijden. Situatie 3 Indien naast de tussenaankomsttijden ook de bedieningstijden zelf, zoals natuurlijkerwijze, variaties vertonen zal de verwachte wachttijd toenemen naarmate deze variaties sterker zijn ondanks gelijkblijvende gemiddelden. (Bij zogenaamde exponentiele bedieningstijden – zoals standaard in de wachttijdtheorie gebruikt- zou die gemiddelde wachttijd in dit geval W = 4 minuten bedragen.) Kort samengevat: • Één server (loket) • Aankomsten: 4 klanten per 5 minuten • Één minuut gemiddelde servicetijd per klant 1. Aankomsten precies na 1.25 minuten Servicetijd precies 1 minuut
⇒
Wq = 0 minuten (D / D / 1 – model)
2. Aankomsten random (willekeurig) Servicetijd precies 1 minuut
⇒
Wq = 2 minuten (M / D / 1 – model)
3. Aankomsten random (willekeurig) Servicetijd: exponentieel
⇒
Wq = 4 minuten (M / M / 1 – model)
Conclusie: De essentie van wachttijden is gelegen in de variabiliteit in aankomstpatronen en serviceduren. Een voorbeeld waarmee dit nog sterker kan worden geïllustreerd is het voorbeeld van een bushalte.
Universiteit van Amsterdam
6
Operationele Research & Management
Busvoorbeeld
Stel 3 bussen per uur langs een bushalte Veronderstel dat bij een bushalte gemiddeld per uur 3 bussen arriveren. Gevraagd naar de gemiddelde wachttijd bij aankomst op een willekeurig moment is het intuïtief voor de hand liggende antwoord: 10 minuten. Deze 10 minuten zullen echter alleen met de werkelijkheid overeenkomen indien de bussen strikt om de twintig minuten arriveren. Bij de minst mogelijke variatie in tussenaankomsttijden, daarentegen, is het enige juiste antwoord: in ieder geval méér dan 10 minuten. Het bekende gevoel dat de bus altijd langer op zich laat wachten dan men mocht verwachten, blijkt wiskundig verklaarbaar. Stel bijvoorbeeld, puur fictief, dat twee op de drie bussen reeds na drie minuten arriveren, maar één op de drie pas na 54 minuten, dus gemiddeld nog steeds om de 20 minuten. Een statistisch representatieve situatie is dan bijvoorbeeld een opeenvolging van tussenaankomsttijden voor 6 bussen van 3, 54, 3, 54, 3, 3 minuten (dus nog steeds gemiddeld 20).
3
54
3
54
3 3
Bij aankomst in een kort tusseninterval zal de gemiddelde wachttijd 1 ½ minuut zijn, terwijl dit voor een lang tijdsinterval de gemiddelde wachttijd 27 minuten bedraagt. Alleen is de kans om in zo’n lang interval te arriveren is aanzienlijk groter, 18 keer om precies te zijn. Aldus wordt de gemiddelde wachttijd 2 * 3/60 * 1 ½ + 54/60 * 27 = 25 minuten. Samenvattend • De gemiddelde wachttijd is precies 10 minuten als de bussen strikt om de 20 minuten aankomen. • Als de bussen volgens een andere dienstregeling rijden dan zal 100% zeker de gemiddelde wachttijd > 10 minuten zijn.
Universiteit van Amsterdam
7
Operationele Research & Management
Enkele wachttijdmodellen Onderstaand figuur bevat wachttijdformules voor de volgende modellen M/M/1, M/D/1 en M/M/s.
M / M /1 − model
λ2 µ ⋅ (µ − λ )
Lq = L=
M / D /1 − model
λ2 2µ ⋅ ( µ − λ )
Lq =
λ
L = Lq +
µ −λ
Lq = ( grafiek )
λ µ
Wq =
λ µ ⋅ (µ − λ )
Wq =
W=
1 µ −λ
W = Wq +
ρ=
λ µ
ρ=
Pn = (1 − λ µ ) ⋅ ( λ µ )
M / M / s − model
L = Lq +
λ 2µ ⋅ (µ − λ )
Wq =
1
λ µ
Lq
λ
W = Wq +
µ
λ µ
ρ=
1
µ
λ s⋅µ
n
Legenda λ: µ: s: Wq: W: Lq: L: ρ: Pn :
aankomstintensiteit (= A in het 1-loket model) bedieningscapaciteit per server (= C in het 1-loket model) aantal ingezette servers gemiddelde wachttijd gemiddelde doorlooptijd (verblijftijd) gemiddeld aantal klanten in de wachtrij gemiddeld aantal klanten in het systeem efficiëntie van het systeem (= F) kans op n klanten
Tevens geldt altijd: W = Wq + 1/µ Lq = λ Wq L = λW
Universiteit van Amsterdam
8
Operationele Research & Management
Opdrachten Opgave 1 Een 0900-informatielijn dient te worden geopend. • De vaste ‘all-in’ kosten, inclusief de loonkosten, voor een benodigde telefonist, bedragen € 60,- p.u. • De gemiddelde gespreksduur is 3 minuten. Door de aanschaf van speciale ‘script’ programmatuur kan deze worden teruggebracht tot 2½ minuut per gesprek. • Tijdens het wachten en het in gesprek zijn worden de telefoonkosten doorberekend tegen € 5,per uur. Adviseer over de al dan niet te gebruiken programmatuur tegen € 20,- per uur als het aantal telefoontjes op 18 per uur wordt geschat. Opgave 2 Door toenemende groei in de luchtvaart wordt de aanleg van een nieuwe landingsbaan overwogen. Omdat de extreme kosten voor de aanleg van deze baan een belangrijke factor spelen, worden ook de ‘wacht’ kosten van vliegtuigen in aanmerking genomen. Het gemiddelde ‘brandstof’ verbruik per minuut voor een ‘wachtend (rondcirkelend)’ vliegtuig bedraagt 40 liter tegen € 0,50 per liter. De gemiddelde landingsduur, inclusief opvolgtijd i.v.m. veiligheidsmaatregelen, kan gesteld worden op 3 minuten. Alleen de 3 piekuren (hubs) per dag worden in acht genomen en andere kosten (personeel, goodwill) worden buiten beschouwing gelaten. a) Bepaal de met deze landingsbaan gepaard gaande ‘landingskosten’ op jaarbasis bij een verwachte vluchtintensiteit gedurende piekuren van 5 vluchten per uur 10 vluchten per uur 15 vluchten per uur 17 vluchten per uur 18 vluchten per uur b) De aanlegkosten van een tweede (vijfde) baan worden geraamd op 30 miljoen Euro. Deze dienen in 10 jaar ‘terugverdiend’ te zijn, waarbij de ‘opbrengsten’ van een vlucht buiten beschouwing worden gelaten. Bij welke ‘drukte’ prognose voor de komende 10 jaar (constant verondersteld gedurende 10 jaar) zou U de aanleg van een ‘tweede’ baan adviseren?
Universiteit van Amsterdam
9
Operationele Research & Management
Opgave 3 De polikliniek van Medisch Centrum West heeft thans één arts voor niet-urgente patiënten. Dergelijke patiënten komen at random binnen volgens gemiddeld 2 ½ per uur en vereisen een behandelingstijd van gemiddeld 20 minuten. 1. Bepaal de gemiddelde tijd die en patiënt moet wachten voordat hij behandeld wordt, indien de behandelingsduur exponentieel wordt verondersteld. Wat is het aantal patiënten dat gemiddeld aanwezig is, hetzij in behandeling dan wel wachtend? 2. Men overweegt een tweede en eventueel zelfs eren derde arts toe te voegen om de wachttijden terug te brengen. Vergelijk m.b.v. onderstaand figuur, daartoe de wachttijden in elk van de drie gevallen. 3. De salariskosten per arts bedragen € 200,- per uur. De kosten van wachten als maat voor goodwill en toekomstige clientèle (zie Elsevier, juni 1995) worden geschat op € 75,- per patiënt per uur. Breng op basis van een kostenvergelijking uw advies uit.
Universiteit van Amsterdam
10
Operationele Research & Management
