M/D/1 wachtsysteem

Het wachtsysteem kenmerkt zich door een constante bedieningsduur bij het loket. Het aankomstproces is (nog steeds) een Poisson-proces. De bedieningsduur schrijven we weer als , maar is nu een gedegenereerde stochastische variabele die altijd dezelfde waarde aanneemt. Om de overeenkomst te handhaven met de wachtrij, is die vaste waarde :

Het aankomstproces is een Poisson-proces met intensiteit (klanten per tijdseenheid). De bezettingsgraad van de wachtrij is het product van het aantal klanten per tijdseenheid en het aantal tijdseenheden bedieningsduur per klant:

Als we de toestand van een wachtrij op een willekeurig moment zouden moeten beschrijven, dan moet, naast het aantal klanten in het systeem, ook vermeld worden hoever de bediening van de klant bij het loket gevorderd is, omdat nu de bedieningsduur niet een geheugenloze verdeling heeft. Het lijkt daarom dat de eenvoudige Markov-keten beschrijving zoals we die kennen van de wachtrij hier niet opgaat. Toch is er een eenvoudig model mogelijk, namelijk door te kijken naar het aantal klanten in het systeem op discrete tijdstippen. We kiezen deze tijdstippen op onderling gelijke afstand van precies één bedieningsduur:

Als t de bovenstaande waarden doorloopt dan is het proces een discrete tijd Markov-keten. Ondanks dat niet gegeven is hoeveel van de bedieningsduur verstreken is van de klant bij het loket (als er eentje is) is het wel zeker dat een eventuele bediening, die gaande is op een bepaald tijdstip, afgelopen zal zijn op het volgende discrete tijdstip. Ook is zeker dat er tussen twee tijdstippen van de rij (5.41) er nooit meer dan één bediening beëindigd zal worden.

Het toeval in de overgangen van de discrete-tijd Markov-keten wordt bepaald door het aankomstproces. Het aantal aankomsten in een tijdsinterval van lengte is Poisson verdeeld met gemiddelde . De kans op k aankomsten wordt dan gegeven door de bekende formule:

Als er op een bepaald tijdstip i klanten in het systeem zijn (i>0), dan zijn er met kans het volgende discrete tijdstip i-1+k klanten in het systeem. Dit geeft de overganskansen vanuit de toestand i (i>0). Vanuit toestand 0 wordt met kans een sprong gemaakt naar toestand k. Vanuit elke toestand gaat dus een hele waaier van overgangskansen naar rechts in het toestandsdiagram. In figuur 5.5 is dit aangegeven met een onderbroken pijl. Bijvoorbeeld vanuit toestand 3 zijn overgangen mogelijk naar toestand 2 met kans , naar zichzelf met kans , naar 4 met kans , en zo verder, naar k met kans . Dit laatste staat in het diagram als .

 
Figuur: Toestandsdiagram discrete tijd Markov-keten bij model.  

Voor het opschrijven van de evenwichtskansen van de discrete-tijd Markov-keten is het handig om te definiëren als de kans op k of meer aankomsten:

De evenwichtskans om 0 klanten in het systeem te treffen is 1 minus de kans dat het loket bezet is:

Het bepalen van de overige evenwichtskansen gaat met een soortgelijk evenwichtsargument als in het geval dat er alleen overgangen naar buurtoestanden mogelijk zijn (zie pagina ). Denk een verticale lijn tussen toestand 0 en 1. De kans dat een willekeurige overgang er een is die van rechts naar links over die lijn gaat, is gelijk aan . De kans op een overgang over die lijn van links naar rechts is . Uit de evenwichtsveronderstelling volgt dan:

Plaats nu een denkbeeldige lijn tussen 1 en 2. De kans op een sprong naar links, over de lijn, is . Een sprong naar rechts, over de lijn, kan komen uit toestand 0 (kans ) of uit toestand 1 (kans ). In geval van evenwicht is een sprong naar rechts even waarschijnlijk als een sprong naar links, dus:

Zo kan de redenering voortgezet worden. We schrijven hier de resultaten tot en met op:

De verdelingsfunctie van de wachttijd wordt gegeven door een redelijk complexe uitdrukking die we hier in zijn algemeenheid niet kunnen behandelen. Echter als we ons beperken tot die waarden van de verdelingsfunctie waar t een veelvoud van de bedieningsduur is, dan blijkt dat er slechts nog een simpele optelling van bovenstaande kansen van de evenwichtsverdeling nodig is.

De reden is dat de wachttijd van een nieuwe klant, die k of minder klanten aantreft in het systeem, altijd kleiner is dan k maal de bedieningsduur . Omgekeerd volgt uit het feit dat de wachttijd voor een ``test-klant'' kleiner is dan dat het aantal klanten dat deze klant in het systeem treft kleiner of gelijk aan k moet zijn. Als we dit combineren met het PASTA (Poisson Arrivals See Time Averages) resultaat dan kunnen we compact in formule notatie schrijven:

Met een constante bedieningsduur is de verblijftijd van een klant in het systeem altijd precies langer dan de wachttijd. De verdelingsfunctie van de verblijftijd is dan:

De gemiddelde verblijftijd of wachttijd is niet direct af te leiden uit (5.49) respectievelijk (5.50) omdat de verdelingsfuncties alleen gegeven zijn voor veelvouden van de bedieningsduur, en bovendien zijn die formules alleen praktisch indien k niet te groot is. Voor de gemiddelde verblijftijd / wachttijd maken we gebruik van een algemeen resultaat dat in de volgende paragraaf gegeven wordt. In het geval van de wachtrij levert dit de volgende formules op:

Een processor verwerkt taken met een verwerkingstijd (bedieningsduur) van 100 ms per taak. De toegestane bezettingsgraad van de processor, , wordt bepaald door de eis dat, met slechts 10% kans, de responstijd langer dan 300 ms mag zijn.

Aanvankelijk had men berekend volgens het model (dus uitgaande van een negatief exponentieel verdeelde bedieningsduur). Dit gaf een waarde van die in de praktijk veel te laag bleek. Toen merkte men op dat de bedieningsduur geen toevalsgrootheid is, maar een deterministische waarde heeft. Het model is dus van toepassing. De aanname van een Poisson-aankomstproces (de eerste M) blijft wel gerechtvaardigd zolang de aankomsten gegenereerd worden door een groot aantal onafhankelijke bronnen.

Gevraagd: Wat is de waarde van ,

1.   volgens het model?
2.   volgens het model?

Voor het model halen we deze overschrijdingskans uit de verdelingsfunctie voor de verblijftijd (5.18):

Hieruit kunnen we oplossen; deze waarde van geeft dan (vanwege ) ook de maximaal toegestane waarde voor :

Voor de wachtrij, wordt 1 minus de overschrijdingskans gegeven door formule (5.50). Hieruit volgt dat de kans op een verblijftijd groter dan 3 maal de bedieningsduur gelijk is aan:

Om de drie evenwichtskansen te berekenen passen we de formules (5.42)--(5.47) toe. Daarmee schrijven we achtereenvolgens op:

Bij het sommeren van , en , vallen sommige termen tegen elkaar weg; met nog wat algebra vinden we dan

Het rechterlid, 0.9, komt van de eis . De maximaal toegestane bezettingsgraad, , is de oplossing van bovenstaande vergelijking. De oplossing van deze zogeheten transcendente vergelijking is niet in elementaire functies uit te drukken. We hebben daarom bepaald met een binary search. Deze zoek methode is eenvoudig te programmeren en kan in een paar regels Pascal opgeschreven worden als:

     left := 0; right := 1; 
     for i := 1 to 20 do
     begin
       rho := (left + right)/2; 
       if exp(rho) * (exp(rho) - rho) * (1 - rho) > 0.9 
       then
         left := rho
       else 
         right := rho
     end;