Wachten in de supermarkt Rik Schepens 0772841
Rob Wu 0787817
22 juni 2012
Begeleider: Marko Boon
Modelleren A Vakcode: 2WH01
Inhoudsopgave Samenvatting
1
1 Inleiding
1
2 Theorie
1
3 Model
3
4 Resultaten
5
5 Conclusie en discussie
5
A Voorbeelden van wachtrij-aspecten
6
B Programma en algoritme
7
C Resultaten van de simulatie
8
Referenties
9
Samenvatting In een supermarkt zijn er vijf permanent bemande kassa’s. Wanneer een klant wilt afrekenen, sluit hij bij ´e´en van de rijen voor deze kassa’s aan. Het komt regelmatig voor dat een kassa vrij is, terwijl er een (lange) rij voor een andere kassa staat. Het inkorten van de wachttijden is in ieders belang, en daarom wordt er onderzocht hoe deze verkort kan worden. De situatie waarbij het aantal wachtrijen wordt teruggebracht tot ´e´en grote moet worden onderzocht. De wachttijd is afhankelijk van het volume klanten en de verwerkingscapaciteit van de kassa’s. Met behulp van formules uit de wachtrijtheorie kan worden berekend wat de invloed van deze factoren is op de wachttijd. Door middel van simulaties is nogmaals te zien hoe de wachttijden zich ontwikkelen. Om de wachttijd te verkorten verdient het gebruik van ´e´en grote rij de voorkeur boven vijf kleine rijen.
1
Inleiding
De supermarkt heeft vijf kassa’s, die altijd bemand zijn. Op het moment kunnen klanten voor elke kassa bij de rij aansluiten. Het vaak voor dat een klant ziet dat een andere kassa vrij is gekomen, terwijl hij in de rij wacht. Soms wisselt hierdoor een klant van kassa, om zo sneller geholpen te worden. Misschien is het hanteren van ´e´en wachtrij effici¨enter. In dit geval gaat een klant uit de rij naar een kassa, zodra deze vrijkomt.
2
Theorie
Het probleem is onderdeel van een bepaalde tak van de wiskunde, de wachtrijtheorie. Om dit goed te begrijpen moet je eerst door een stuk theorie. Hieronder staat het standaard model van een wachtrij. De horizontale lijn is hier de rij, de verticale streepjes zijn de wachtenden, en het rondje is de server. De server verwerkt de wachtenden, hier is dit dus de kassa.
1
Standaard wachtrij model Vervolgens moet er rekening worden gehouden met de volgende punten: Het aankomstproces van de klanten, het gedrag van de klanten, de service snelheid, de verwerkingsvolgorde, de service capaciteit en de maximale lengte van de wachtrij. Deze be¨ınvloeden wat voor soort model je zou moeten kiezen. Hoe deze er bij ons model uitzien wordt bij het model verteld. En er staan per punt extra voorbeelden in de bijlage. (Bijlage: A) Een groot aantal modellen zijn door Kendall samen gevat in een korte notatie. Deze ziet eruit als a/b/c , hierbij is a de verdeling van de tijd tussen de aankomsten, b de verdeling van de service tijd, en c het aantal servers. De verdelingen worden afgekort met letters. De hier gebruikte letters zijn M (memoryless), welke een exponenti¨ele verdeling aangeeft, en G (general) welke een verdeling in het algemeen aangeeft. De letters λ1 en µ1 geven respectievelijk de gemiddelde tussenaankomsttijd en de gemiddelde servicetijd weer. Deze zijn van belang bij de verdeling van aankomsten, en service tijd. De verhouding hiertussen wordt vaak aangeduid met ρ, het is zeer belangrijk dat deze verhouding kleiner is dan 1. Dit is de stabiliteitsvoorwaarde, als hier niet aan wordt voldaan dan groeit de wachtrij enkel. Tot slot moet er worden bepaalt waar naar wordt gekeken om de prestatie te meten. Hier zullen we vooral ge¨ınteresseerd zijn in de gemiddelde waardes van de lengte van de wachtrij E(Lq ) (q staat hier voor queue) en de wachttijd E(W ).
De Wet van Little De wet van Little geeft een belangrijke relatie aan tussen deze laatstgenoemden. Hierbij is al wel aangenomen dat het een stabiel systeem is. Dus ρ < 1. Little zegt dan het volgende: E(Lq ) = λE(W )
(1)
Dit is heel handig om berekeningen uit te voeren.
PASTA De PASTA eigenschap geld voor bepaalde wachtrij-modellen. En deze zegt dat als je op een willekeurig moment kijkt dat de kans dat je situatie A aantreft even groot is als de de fractie van de tijd dat het systeem zich in situatie A bevindt. 2
Over het algemeen is dit niet het geval. Enkel bij M/ · /· is dit altijd het geval. Dit zorgt ervoor dat bij een zodanig model de gemiddelde waardes makkelijker bepaald kunnen worden.
3
Model
Het is belangrijk om eerst een paar dingen aan te nemen. Ten eerste nemen we aan dat de tussenaankomstijd exponentieel verdeeld is, dit maakt het rekenwerk veel eenvoudiger, en is ook een zeer representatief model voor de tussenaankomsttijden. Ook wordt de verdeling van de service tijd exponentieel verondersteld. Hier is wederom voor gekozen om het model eenvoudiger te houden. Ook is het een redelijk representatief model voor de service tijden. Daarnaast wordt er een situatie verondersteld met vijf kassa’s die allen geopend zijn, dus de service capaciteit is vijf. Tevens veronderstellen we dat bij iedere kassa de service tijd identiek en onafhankelijk verdeeld is. Het is vrij logisch dat dit in de werkelijkheid niet volledig waar is, het verschil wat dit in de resultaten veroorzaakt is echter verwaarloosbaar. (Zie bijlage C) Ook wordt verondersteld dat er volgens een ”wie het eerst komt, wie het eerst maalt”systeem wordt gewerkt, dit is gebruikelijk in een supermarkt. Tot slot is er geen maximale lengte van de wachtrij. Ten eerste staan hier de gekozen modellen zoveel mogelijk theoretisch uitgewerkt, hierin is de gemiddelde tussenaankomstijd van het hele systeem λ1 genoemd en de gemiddelde service tijd per server µ1 . We gaan ervan uit dat ρ kleiner is dan 1, zodat er een stabiel systeem is. Daarnaast is er ook een programma wat een simulatie draait van de modellen, hier is het bijvoorbeeld ook mogelijk om verschil in service tijden in te voeren. Dit is theoretisch nauwelijks te verwerken, maar wel is het met een simulatie goed te benaderen.
1 rij per kassa Dit is het systeem dat op het moment eigenlijk overal wordt gebruikt. Hier zijn een paar extra aannames nodig om het model in goede banen te leiden. Om te beginnen, kiest klant een rij en blijft bij zijn keuze. Ofwel hij wisselt niet van rij. Daarnaast kiest een klant willekeurig een rij waarin hij aansluit. Dit is natuurlijk niet realistisch en zal een redelijk verschil maken, echter is er geen manier om een model zodanig te maken dat er een logische keuze, zoals sluit aan in de kortste rij, wordt gemaakt. Hier zal een simulatie alsnog uitkomst voor bieden. Deze aannames leveren vijf maal een M/M/1 model. Preciezer nog een 3
M ( 15 λ)/M (µ)/1, waarbij dus de tussenaankomstentijden exponentieel verdeeld zijn met een gemiddelde van 11λ en de service tijden exponentieel zijn 5
verdeeld met een gemiddelde van µ1 . De gemiddelde rijlengte en de gemiddelde wachtrij zijn dan ook vrij vanzelfsprekend gelijk aan die van ´e´en maal 1 λ ditzelfde model. Er geld dan ρ = 5µ . Volgens de formules [1] geldt dan het volgende: ρ/µ (2) E(W ) = 1−ρ ρ2 E(L ) = 1−ρ q
(3)
Let op Lq staat hier natuurlijk wel voor de gemiddelde rijlengte per rij. Voor de totale wachtrij geldt: E(LqT ) = 5 ·
ρ2 1−ρ
(4)
1 grote rij Dit is het alternatieve systeem waarvan wordt vermoed dat het wellicht beter werkt. Ook hier zijn een paar extra aannames vereist. Om te beginnen zal het in de praktijk wellicht voorkomen dat kassa’s tijdelijk niemand bedienen, omdat mensen er nog naartoe moeten lopen. Dit is echter gering, zeker als je meeneemt dat als er bijna een kassa vrij is, dat dit wel duidelijk is, en de volgende persoon alvast naar de deze kassa kan lopen. Deze looptijd wordt dus op nul verondersteld. Dit levert een redelijk standaard voorbeeld van een M/M/c model, of preciezer een M (λ)/M (µ)/5 model. Met exponentieel verdeelde tussenaankomstentijden met een gemiddelde van λ1 en met exponentieel verdeelde service λ tijden met een gemiddelde van µ1 . Er geld dan ρ = 5µ (merk op dat deze gelijk is aan de ρ in het andere systeem). Volgens de formules [1] geldt dan het volgende: 1 1 E(W ) = ΠW · · (5) 1 − ρ cµ ρ E(Lq ) = ΠW · (6) 1−ρ Hierbij komt ΠW tevoorschijn, dit is een aparte variabele die een vervelende som voorkomt, en ook snel het verband laat zien met het andere model van het systeem met vijf rijen. ΠW is dusdanig lastig te berekenen dat het hier wordt overgeslagen. Meer informatie hierover is te vinden in [1].
4
4
Resultaten
Uit 6 en 4 blijkt al snel dat enkel ΠW hoeft te worden vergeleken met ρ. Indien ΠW < ρ dan levert ´e´en grote rij dus betere resultaten. Vice versa, als ΠW > ρ dan geniet een rij per kassa de voorkeur. Uiteindelijk bleek echter uit de simulaties dat vooral het model voor de vijf rijen dusdanig ver van de werkelijkheid lag, dat de resultaten uit deze vergelijkingen niet representatief genoeg zijn. In de simulaties wordt ook duidelijk dat de situatie met 1 rij een beter resultaat levert. In de simulatie is duidelijk te zien dat de wachttijden korter worden bij kleine waarden van ρ. Bij gelijke waarden van ρ is te zien dat de wachttijden groter zijn bij kleinere waarden λ en µ. Dit is eenvoudig in te zien: Een kleine waarde λ of µ betekent dat de gemiddelde tussenaankomst- en verwerkingstijd een hoge waarde hebben. In de praktijk betekent dit dat er niet vaak klanten komen, maar dat a´ls er een klant komt, deze vaak een grote bestelling heeft gedaan. De kans dat twee of meer van deze klanten achter elkaar komen is niet te verwaarlozen, wat terug te zien is in de resultaten van de simulatie. De slechtere prestatie van het vijf-kassa’s-model ten opzichte van de simulatie, waarbij wel slim word gekozen, is te verklaren door het feit dat bij het model er momenten zijn waarbij een kassa leeg is, terwijl er elders een wachtrij is. En dat de kans even groot is dat de nieuwe klant in een van beide rijen aansluit.
5
Conclusie en discussie
Uit de simulaties blijkt dat de situatie met ´e´en lange wachtrij een kortere wachttijd per klant geeft dan het geval waarin er vijf wachtrijen zijn. Vandaar het advies om dit systeem te gebruiken. In de modellen zijn verschillende aannames gemaakt. Met de psychologische kant is geen rekening gehouden. Het is mogelijk dat een klant in een lange rij de duur van het wachten groter ervaart dan dat het in werkelijkheid is. In de praktijk zal de looptijd in de rij en tussen de rij en kassa een rol spelen. Denk hierbij aan een oude vrouw die slecht ter been is, of een groepje personen die in een geanimeerd gesprek niet door hebben dat de rij inmiddels is doorgeschoven.
5
A
Voorbeelden van wachtrij-aspecten • Het aankomstproces van de klanten Het is belangrijk om te weten hoe dit gebeurd, hiervoor is een verdeling van de tussenaankomsttijden nodig, en is het ook handig om hier meteen een gemiddelde van λ1 bij te doen. • Het gedrag van de klanten Het kan bijvoorbeeld zijn (bij een telefooncentrale) dat mensen uit de wachtrij stappen as ze al heel lang wachten, specifieke voorbeelden hier zijn dingen als hoe kiest een klant zijn rij. • De service snelheid Ook hier is de vraag hoe de service tijd is verdeeld, en wat hier het gemiddelde van is. • De verwerkingsvolgorde Wordt er FiFo (first-in, first-out) gewerkt, of worden de laatste mensen uit de rij eerst geholpen, of in een supermarkt vaak van toepassing, worden mensen met een kleine bestelling eerst geholpen. • De service capaciteit Hoeveel servers heb je, hier dus 5 kassa’s • De maximale lengte van de wachtrij Hoe lang kan de rij worden, bij de Jumbo mag dit maar 4 zijn, anders zijn de boodschappen gratis.
6
B
Programma en algoritme
Voor dit project hebben we een programma geschreven die een simulatie uitvoert. Deze demo bevat ook een animatie van de situatie, en is te vinden op http://rob.lekensteyn.nl/supermarkt/ en volgt het volgende algoritme: Initialisatie: Bereken de eerstvolgende aankomsttijd (next time) van een klant, exponentieel verdeeld met gemiddelde λ1 . Zolang de simulatie bezig is: 1. Verhoog de teller (time) die het aantal tijdseenheden bijhoudt met ´e´en. 2. Bereken het verschil tussen next time en time. Als deze afgerond kleiner is dan ´e´en, dan zitten de tijden dicht op elkaar. Dit betekent dat er een klant binnenkomt. Als dit niet het geval is, ga naar stap 6. 3. Maak een nieuwe klant met een willekeurige (exponentieel verdeeld) verwerkingstijd. Dit is de tijd die de kassa later nodig zal hebben voor deze klant. 4. Voeg deze klant toe aan de aankomstwachtrij (arrival queue), en verhoog de teller van het aantal aangekomen klanten met ´e´en. 5. Genereer een nieuwe waarde voor next time, zoals beschreven in de initialisatiestap. Deze waarde geeft aan hoeveel tijd er nog moet verstrijken voordat de volgende klant aankomt. Tel hierbij de huidige waarde van time op, zodat het verschil berekenen in stap 2 zinvol is. 6. Voer de model-afhankelijke stappen uitvoert. 7. Ga verder bij 1.
Model-afhankelijke stappen voor ´ e´ en grote wachtrij In de broncode te vinden in functie demo 1q. 1. Volg voor elke kassa de volgende stappen: • Als de kassa geen klant aan het verwerken is en arrival queue is niet leeg, verwijder de eerste klant uit deze wachtrij. Tel de verwerkingstijd van deze klant op bij de benodigde verwerkingstijd van de kassa. • Als de verwerkingstijd van de kassa hoger is dan nul, trek daar dan ´e´en van af. 7
2. Tel de lengte van de arrival queue op bij de totale wachttijd.
Model-afhankelijke stappen voor vijf wachtrijen In de broncode te vinden in functie demo 5q. 1. Als de lengte van arrival queue hoger is dan nul (dat wil zeggen, er is een klant gearriveerd), dan: • (”Slim gekozen”) Neem van alle kassa’s de kassa met de kortste wachtrij. (In overeenstemming met het theoretische model) Kies een kassa, volstrekt willekeurig. • Voeg de nieuwe klant toe aan de wachtrij van deze kassa. 2. Voer de volgende stappen uit voor elke kassa: • work load is de actuele verwerkingstijd die de kassa nog nodig heeft om zijn klant weg te werken • Als de kassa bezig is (work load is groter dan nul), trek hier dan ´e´en eenheid van af. • Als work load kleiner of gelijk is aan nul en de kassa heeft een niet-lege wachtrij, verwijder de eerste klant uit deze wachtrij, en voeg de waarde van de klant’s verwerkingstijd toe aan work load. • Tel de lengte van de rij bij de kassa op bij de totale wachttijd (iedere persoon in de rij moet immers ´e´en tijdseenheid wachten). De gemiddelde wachttijd per klant is uit te rekenen door de totale wachttijd te delen door het aantal aangekomen klanten. Merk op: In het algorithme is nergens een specificatie gegeven voor het aantal kassa’s. De simulatie is dus algemeen toepasbaar voor een willekeurig aantal kassas. Dit is in de broncode bovenaan in te stellen via de variable CHECKOUT COUNT.
C
Resultaten van de simulatie
In de tabel hieronder is te zien wat de gemiddelde wachttijd is per klant na 108 simulaties (in tijdseenheden). De simulatie is gedaan onder de aannames dat zowel de aankomsttijden van de klant, als de verwerkingstijden voor de 8
klant exponentie¨el verdeeld zijn met gemiddelde λ1 respectievelijk µ1 . Verder zijn de kassa’s identiek wat betreft verwerkingssnelheid en worden de klanten geholpen in de volgorde van aankomst bij de kassa (FIFO). De rijlengte is ongelimiteerd en er zijn vijf kassa’s. Kolom Q1 geeft het resultaat bij ´e´en grote rij. Voor vijf rijen, waarbij de klant steeds de kortste kassa kiest is het resultaat weergeven in kolom Q5. Het geval waarbij een klant willekeurig een kassa kiest is in de laatste kolom (R5) te zien. λ µ ρ = 5µ Q1 Q5 R5 λ 0.500 0.100 1.000 ∞* ∞* ∞* 0.100 0.021 0.952 2.4 · 102 4.0 · 102 1.2 · 102 0.004 0.001 0.800 5.3 · 102 1.0 · 102 3.9 · 104 45 1.7 · 102 0.100 0.250 0.800 24 0.200 0.500 0.800 13 26 92 0.050 0.020 0.500 2.7 6.2 51 3,7 26 0.100 0.040 0.500 1.4 0.001 0.001 0.200 0.9 1.6 2.5 · 102 0.010 0.010 0.200 0.1 0.6 25 0.200 0.200 0.200 0 0.6 1.4 0.7 0.8 0.400 0.400 0.200 0 0.400 0.400 0.200 0 0.7 0.8 0.005 0.100 0.100 0 0 0.1 0.010 0.200 0.100 0 0 0.1 0 0 0.020 0.400 0.100 0 0.001 0.020 0.010 0 0 0.6 0 0.0 0.002 0.040 0.010 0 0.001 0.040 0.005 0 0 0 λ * Wanneer het quotient 5µ bijna gelijk of groter is aan ´e´en, is de gemiddelde tijd aankomsttijd van een klant gelijk aan de capaciteit van de kassa’s gezamenlijk. Op een gegeven moment onstaan er rijen, die niet meer weg te werken zijn. Het gevolg is dat elke volgende klant gemiddeld langer moet wachten.
Referenties [1] Adan, I., & Resing, J. (2002) Queueing Theory. Department of Mathematics and Computer Science, Eindhoven University of Technology [2] Queue 2.0: Applet Wachtrijsimulatie. Tu/e, faculteit Wiskunde en Informatica. URL: http://www.win.tue.nl/cow/Q2 9
