Nederlands
Menu

Wat is Wachtrijtheorie?

De theorie die met kansmodellen beschrijft hoe verwerkingsverzoeken bij een loket of server aankomen en wachten tot die vrij is om te worden bediend, en die daaruit wachttijden en wachtrijlengtes afleidt. Een model wordt beschreven in de notatie van Kendall, die de aankomstverdeling, de verdeling van de bedieningstijd en het aantal bedieningsstations opsomt, zoals in „M/M/1”. In het M/M/1-model is de gemiddelde wachttijd ρ/(1 − ρ) × Ts, met de bezettingsgraad ρ = aankomstintensiteit λ × gemiddelde bedieningstijd Ts. De theorie wordt gebruikt bij prestatie-evaluatie van computers, de analyse van netwerkvertraging en de analyse van onderhanden werk in fabrieken.

Japanse benaming: 待ち行列理論

“Wachtrijtheorie” komt voor in 6 oefenvragen uit 1 onderwerpen, bijv. Kansrekening, statistiek en wachtrijen.

Vakgebied: Kansrekening, statistiek en wachtrijen

De notatie van Kendall en M/M/1

Een wachtrijmodel wordt geschreven in de vorm „aankomstverdeling/verdeling van de bedieningstijd/aantal bedieningsstations”. M staat voor de markoveigenschap: bij aankomsten betekent het poissonaankomsten (exponentieel verdeelde tussenaankomsttijden) en bij bedieningstijden een exponentiële verdeling. D betekent een constante tijd en G een algemene verdeling. M/M/1 is een model met één bedieningsstation, willekeurige aankomsten en willekeurige bedieningstijden; de basisaannamen zijn een onbeperkte wachtruimte, verwerking in volgorde van aankomst en een stationaire toestand die na voldoende tijd is bereikt.

Basisformules

De bezettingsgraad ρ = λ × Ts is het deel van de tijd waarin het bedieningsstation bezig is. Voor M/M/1 is de gemiddelde wachttijd Wq = ρ/(1 − ρ) × Ts, de gemiddelde responstijd W = Wq + Ts = Ts/(1 − ρ) en het gemiddelde aantal in het systeem L = ρ/(1 − ρ). Deze grootheden zijn verbonden door de wet van Little L = λW; met λ = 3 per minuut en Ts = 15 seconden is bijvoorbeeld ρ = 0,75, Wq = 45 seconden, W = 60 seconden en L = 3.

Bezettingsgraad en wachttijd

Wq ÷ Ts = ρ/(1 − ρ) is 1 bij een bezettingsgraad van 0,5, 4 bij 0,8, 9 bij 0,9 en 19 bij 0,95, en groeit sterk naarmate de bezettingsgraad 1 nadert. Dat komt doordat de vrije tijd 1 − ρ die beschikbaar is om wachtrijen weg te werken die door toevallig samenvallende aankomsten ontstaan, schaars wordt. Systemen waarin de responstijd belangrijk is, worden daarom met marge in de bezettingsgraad ontworpen.

Nu oefenen: vragen over Wachtrijtheorie

Bij een loket komen gemiddeld 12 verzoeken per uur binnen, en de afhandeling van een verzoek duurt gemiddeld 4 minuten. Wat is de bezettingsgraad van het loket als het als M/M/1-wachtrij wordt beschouwd?

  1. A0,8
  2. B1,25
  3. C3
Antwoord en toelichting tonen

Antwoord: A. 0,8

De bezettingsgraad ρ is het product van de aankomstintensiteit λ en de gemiddelde bedieningstijd Ts en drukt uit welk deel van de tijd het loket bezig is. Met gelijke eenheden is 4 minuten = 1/15 uur, dus ρ = 12 × 1/15 = 0,8. Met de bedieningsintensiteit μ = 15 per uur geeft ρ = λ/μ = 12/15 hetzelfde resultaat.

Bij een server komen gemiddeld 3 verzoeken per minuut binnen, en de verwerking van een verzoek duurt gemiddeld 15 seconden. Wat is, als de server als M/M/1-wachtrij wordt beschouwd, de gemiddelde tijd vanaf de aankomst van een verzoek tot het einde van de verwerking (de gemiddelde responstijd)?

  1. A20 seconden
  2. B45 seconden
  3. C60 seconden
Antwoord en toelichting tonen

Antwoord: C. 60 seconden

De bezettingsgraad is ρ = 3 per minuut × 15 seconden ÷ 60 seconden = 0,75. De gemiddelde wachttijd is Wq = ρ/(1 − ρ) × Ts = 0,75/0,25 × 15 = 45 seconden, en met de verwerkingstijd van 15 seconden erbij is de gemiddelde responstijd 45 + 15 = 60 seconden. Ts/(1 − ρ) = 15/0,25 = 60 seconden geeft hetzelfde resultaat.

Veelgestelde vragen

Wat als de aannamen van M/M/1 niet gelden?

Dan wordt een model gebruikt dat dichter bij de werkelijkheid ligt, zoals M/D/1 als de bedieningstijd constant is. De gemiddelde wachttijd bij M/D/1 is precies de helft van die bij M/M/1, en hoe kleiner de variatie in bedieningstijd, des te korter het wachten. Complexe systemen worden vaak met simulatie gecontroleerd, en de wet van Little geldt in alle gevallen.

Is het beter om bedieningsstations toe te voegen of om een station sneller te maken?

Bij dezelfde totale capaciteit geeft één station dat twee keer zo snel is een kortere gemiddelde responstijd dan twee stations die één wachtrij delen (M/M/2). Vergelijkt men alleen de tijd die in de wachtrij wordt doorgebracht, dan geven twee stations juist het kortere wachten. Krijgt bij twee stations elk station een eigen wachtrij, dan kunnen klanten bij het ene wachten terwijl het andere vrij is, zodat de wachttijd langer is dan met één gedeelde wachtrij.

“Wachtrijtheorie” in de toelichting

Vragen met “Wachtrijtheorie” (6)

  1. Bij een loket komen gemiddeld 12 verzoeken per uur binnen, en de afhandeling van een verzoek duurt gemiddeld 4 minuten. Wat is de bezettingsgraad van het loket als het als M/M/1-wachtrij wordt beschouwd?
  2. Bij een server komen gemiddeld 3 verzoeken per minuut binnen, en de verwerking van een verzoek duurt gemiddeld 15 seconden. Wat is, als de server als M/M/1-wachtrij wordt beschouwd, de gemiddelde tijd vanaf de aankomst van een verzoek tot het einde van de verwerking (de gemiddelde responstijd)?
  3. Bij een server die als M/M/1-wachtrij kan worden beschouwd, nam de aankomstintensiteit toe terwijl de gemiddelde bedieningstijd gelijk bleef, en steeg de bezettingsgraad van 0,8 naar 0,9. Met welke factor veranderde de gemiddelde wachttijd Wq (de tijd die in de wachtrij wordt doorgebracht)? Welke waarde ligt het dichtst bij deze factor?
  4. Een server met een gemiddelde bedieningstijd van 0,2 seconden wordt als M/M/1-wachtrij beschouwd. Welke waarde ligt het dichtst bij de maximale aankomstintensiteit die kan worden toegelaten als de gemiddelde responstijd (wachttijd plus verwerkingstijd) hoogstens 1,0 seconde mag zijn?
  5. Verzoeken bereiken een server als poissonaankomsten (onafhankelijke, willekeurige aankomsten), gemiddeld 6 per minuut. Welke combinatie van de verdeling die de tussenaankomsttijden volgen en hun gemiddelde is juist?
  6. Er zijn twee loketten die even snel werken. Bij methode A kiest elke klant bij aankomst met gelijke kans een van de loketten en sluit aan in de eigen rij van dat loket. Bij methode B sluiten klanten aan in één gemeenschappelijke rij en worden ze geholpen door het loket dat het eerst vrijkomt. De aankomsten zijn willekeurig, en de totale aankomstintensiteit en de bedieningssnelheid zijn bij beide methoden gelijk. Welke vergelijking van de gemiddelde wachttijd is juist?

Verwante termen

Exponentiële verdeling Betrouwbaarheidsinterval Binomiale verdeling Correlatiecoëfficiënt Hypothesetoets Kwartiel Mediaan Normale verdeling Permutaties en combinaties Poissonverdeling

Naar de woordenlijst