Wachtrijmodellen voor optimalisatie in het dagelijks leven Richard J. Boucherie Stochastische Operationele Research
Abstract Wachten doen we allemaal: bij de kassa van de supermarkt, in het verkeer, maar ook op het Internet. Wachten vormt een normaal aspect van onze dagelijkse routine, en wordt voor een belangrijk deel veroorzaakt door ‡uctuaties in de belasting van systemen. Dit artikel behandelt de achtergrond en de eenvoudige wiskundige theorie van enkele basismodellen in de wachtrijtheorie: het Erlang verlies systeem, en het Processor Sharing systeem. Deze modellen vinden respectievelijk hun oorsprong in de klassieke handgeschakelde telefooncentrale en de CPU van de computer, maar komen in verschillende varianten terug in moderne systemen zoals een GSM cel, een Intensive Care eenheid in een ziekenhuis, het Internet, of het Wireless LAN.
Inleiding Plannen van systemen gebeurt veelal in de veronderstelling dat alle benodigde gegevens bekend en onveranderlijk zijn. Zo lijkt het mogelijk op een machine die gemiddeld 80% van de tijd werkt een additionele hoeveelheid taken te verwerken gelijk aan 20% van de capaciteit van de machine. Hierbij wordt echter volledig voorbij gegaan aan de variatie in duur en begintijdstippen van deze taken. Indien de taken gelijkmatig binnenkomen en allen dezelfde verwerkingstijd hebben (zeg iedere minuut een taak, met verwerkingstijd van 1 minuut), dan is het inderdaad mogelijk de machine tot 100% te belasten. Echter, indien de taken onregelmatig binnenkomen en/of een onregelmatige lengte hebben, dan stijgt de wachttijd van de taken explosief met de belasting van het systeem: bij een belasting van 90% is de wachttijd 2 maal zo groot, en bij belasting van 99% zelfs al 20 maal zo groot als bij belasting van 80%. Vergelijkbare e¤ecten treden op bij autowegen (waar …les ontstaan door variabele snelheid en variabele aantallen auto’s, en een oplossing gevonden wordt door alle auto’s met dezelfde snelheid te laten rijden), spoorwegnetwerken (waar vertragingen ontstaan door kleine verstoringen in de rij- en stoptijden), telecommunicatienetwerken (met variabele duur en aanvangstijdstippen van gesprekken), en in ziekenhuizen waar naast de wachtlijsten bijvoorbeeld ook afzeggen van een operatie omdat er geen vrij Intensive Care bed beschikbaar is grote problemen oplevert, in ieder geval voor de patient die onverrichterzake naar huis moet. De e¤ecten van variabiliteit
1
op de prestatie van systemen wordt beschreven en geanalyseerd binnen de stochastische operationele research, een discipline binnen de toegepaste wiskunde die zich vooral toelegt op de analyse van prestatiematen in systemen die met onzekerheid in de invoer geconfronteerd worden.
Robuuste modellen De stochastische operationele research vindt haar oorsprong in de analyse van telecommunicatiesystemen. In 1917 publiceerde A.K. Erlang de beroemde formule " C # 1 n C X B( ; C) = C! n=0 n!
voor de verlieskans van een handgeschakeld telefoonsysteem. Deze Erlang verliesformule beschrijft de kans dat een gesprek niet toegelaten kan worden in een telefoonsysteem met C lijnen waar gesprekken in de tijd arriveren volgens een Poisson proces met een gemiddelde van per tijdseenheid en gemiddelde gespreksduur van tijdseenheiden, en = . Een gesprek dat alle lijnen bezet vindt wordt geblokkeerd, en gaat verloren. Voor het Erlang verlies systeem is deze blokkeringskans de belangrijkste prestatiemaat. De kracht van de Erlang verliesformule ligt in de eenvoudige relatie tussen de karakteristieken van het telefoonsysteem (capaciteit C en belasting ) en de verlieskans B( ; C). Hiernaast vormt de grote robuustheid van Erlang’s verliesformule een belangrijke sleutel tot het succes van dit resultaat: de formule blijkt zelfs voor netwerken bestaande uit meerdere telefoonsystemen een goede basis te leveren voor de berekening van verlieskansen van gesprekken. Een tweede mijlpaal vormt het processor sharing systeem. Dit is een model voor de Centrale Processor in een computer, in 1967 gepubliceerd door L. Kleinrock, als wiskundige idealisatie van time-sharing in een processor. In dit systeem komen taken aan bij de CPU volgens een Poisson proces, zeg met gemiddeld taken per tijdseenheid. Een taak heeft een gemiddelde lengte van tijdseenheiden, = . De processor verdeelt zijn aandacht eerlijk over de aanwezige taken, gaat cyclisch langs de aanwezige taken, en handelt telkens een klein deel van iedere taak af. In de limiet waarin de processor telkens sneller langs de taken gaat, en telkens een kleinere hoeveelheid werk per taak uitvoert vinden we het Processor Sharing systeem, waarin de processor bij n aanwezige taken op ieder moment een fractie 1=n van zijn capaciteit geeft aan iedere aanwezige taak. Voor het processor sharing systeem is vertraging de belangrijkste prestatiemaat, immers vertraging ontstaat doordat er meer taken gelijktijdig gebruik maken van de processor. Voor een taak van lengte x is de vertraging E[T (x)] =
x 1
:
Zowel het Erlang verlies systeem als het processor sharing systeem noemen we eerlijk, omdat alle taken op dezelfde wijze worden behandeld. Voor het PS 2
systeem geldt bovendien dat de vertraging van een taak evenredig is met de lengte van de taak. Een kleine taak wordt dus niet overmatig gehinderd door andere grote taken. Dit is heel anders dan in een wachtrij voor de kassa, waar een klant met 1 pakje boter wel moet wachten op een klant die een hele kar heeft volgeladen voor het jaarlijks feest van de faculteit. Dit systeem, het First In First Out wachtrij systeem, en vele andere systemen kunnen ook worden geanalyseerd, maar dat zullen we hier niet doen.
A‡eiding van prestatiematen Het Erlang verlies systeem en het Processor Sharing systeem zijn voorbeelden van stochastische processen, waarvoor vele eigenschappen expliciet kunnen worden afgeleid. Wanneer we aannemen dat de gevraagde hoeveelheid werk in deze systemen exponentieel verdeeld is met gemiddelde , dan zijn het voorbeelden van geboorte-sterfte processen, een speciale klasse processen binnen de Markov ketens. Voor deze processen is op eenvoudige wijze de kansverdeling van het aantal actieve taken in het systeem te bepalen. Een stochastisch proces fX(t); t 0g beschrijft de evolutie van een stochastische variabele vanaf tijdstip 0. De aftelbare toestandsruimte S bevat alle toestanden die dit proces kan aannemen. Het stochastisch proces is een Markov proces wanneer de voorwaardelijke kans dat de toestand j is op tijdstip t + s gegeven dat de toestand i is op tijdstip t, en dat in het verleden voor tijdstip t de toestanden i1 ; : : : ; in zijn doorlopen op tijdstippen t1 t2 tn niet af hangt van dat verleden, maar uitsluitend van de toestand i op tijdstip t. Een Markov proces heeft derhalve geen geheugen. Het Erlang verlies systeem en het processor sharing systeem zijn Markov processen die de evolutie van het aantal taken in het systeem beschrijven. De toestandsruimte is S = f0; 1; 2; : : : ; Cg, met C = 1 voor het processor sharing systeem. Dit zijn bijzondere systemen, omdat het aantal taken slechts met een tegelijk kan veranderen. Voor het Erlang verlies systeem is het aankomstproces een Poisson proces, resulterend in een aankomst intensiteit q(i; i + 1) = , de intensiteit van het Poisson aankomst proces. We accepteren aankomsten uitsluitend zolang het systeem niet vol is, dus zolang i < C. De vertrek intensiteit is q(i; i 1) = i= , omdat i exponentieel verdeelde taken met gemiddelde gelijktijdig worden bediend. Voor het Processor sharing systeem is het aankomst proces ook een Poisson proces, zodat q(i; i + 1) = . Hier worden alle taken geaccepteerd. Er is een server. De vertrekintensiteit per aanwezig taak is 1=i , immers alle taken delen de server. Er zijn in toestand i gelijktijdig i taken actief, resulterend in vertrekintensiteit q(i; i 1) = 1= . Hiermee kunnen we een stelsel vergelijking opstellen voor de kans P (i; t) dat de Markov keten zich op tijdstip t in toestand i bevindt, voor alle i 2 S. Veelal
3
beperken we ons tot de evenwichtsverding (i) = lim P (i; t); t!1
waarbij moet worden opgemerkt dat voor onze processen deze limiet inderdaad bestaat, en onafhankelijk is van de beginverdeling. De kansverdeling beschrijft het systeem in statistisch evenwicht. Voor praktische systemen blijkt dat relaxatie naar statistisch evenwicht bijzonder snel optreedt. Uit de evenwichtsverdeling kan voor het Processor Sharing systeem ook de gemiddelde vertraging worden afgeleid. De formule voor de verwachte vertraging E[T (x)] als functie van de grootte van de taak volgt via een andere methode. De belangrijkste eigenschappen van het Erlang verlies model en het Processor sharing model staan in onderstaande tabel. Blocked call C servers
Single server
Processor sharing
Erlang verlies eigenschappen
alle taken accepteren alle taken delen server
hoogstens C accepteren ieder taak eigen server toestandsruimte
S = f0; 1; 2; : : :g
intensiteiten aankomst vertrek evenwichtsverdeling
q(i; i + 1) = q(i; i 1) = 1= (n) = (1
)
n
= prestatiematen
vertraging E[T ] = =(1
S = f0; 1; 2; : : : ; Cg q(i; i + 1) = q(i; i 1) = i= (n) =
n
n!
.P
n C n=0 n!
fractie geblokkeerde .P taken C n C
)
B( ; C) =
C!
n=0 n!
Een belangrijke eigenschap van het Erlang verlies systeem en het Processor Sharing systeem is dat we kunnen laten zien dat de kansverdeling van het aantal aanwezige taken in evenwicht hetzelfde blijft wanneer we de aanname van exponentieel verdeelde grootte van de taken laten vervallen. De enige aanname is dat taken aankomen volgens een Poisson proces. Het Poisson proces vormt een goede beschrijving van een aankomstproces gegenereerd door zeer vele mogelijke taken, waarvan slechts een klein deel daadwerkelijk in het systeem aanwezig is. Dit maakt deze modellen toepasbaar voor modellering en analyse van praktische systemen, immers in de praktijk is veelal slechts beperkte informatie beschikbaar over de kansverdeling van de duur van taken. Het gemiddelde is de meest eenvoudig te verkrijgen statistiek.
4
Voorbeelden Een GSM cel Voor draadloze communicatie tussen de mobiele telefoon en het basisstation (BTS) van het netwerk wordt gebruik gemaakt van frequenties, net als in FM radio. Voor de daadwerkelijke communicatie wordt het spectrum opgedeeld in aparte draaggolven die voor GSM 200 kHz uit elkaar liggen. Hiernaast wordt in GSM door digitale codering iedere draaggolf in de tijd opgeknipt in 8 tijdsloten. Voor een gesprek tussen de mobiele telefoon en de zendmast maakt de GSM telefoon gebruik van een enkel tijdslot op een enkele draaggolf. Dit wordt een kanaal genoemd. Een kanaal wordt toegewezen aan een gesprek voor de gehele gespreksduur. Frequenties worden verdeeld over de BTSs, waarbij een frequentie kan worden hergebruikt op een BTS dat voldoende ver weg ligt. Net als in FM radio zou anders interferentie optreden. In een typisch basisstation zijn 3 a 4 frequenties beschikbaar. Een nieuw gesprek dat alle kanalen bezet vindt wordt geblokkeerd en gaat verloren. Voor de wiskundige modellering van een BTS en de verbinding met de mobiele telefoon is de beschikbare capaciteit (aantal kanalen) van belang. Iedere verbinding met een BTS krijgt een vast kanaal toegewezen. Dit kanaal wordt gebruikt tot het einde van de verbinding. Indien alle kanalen van een BTS in gebruik zijn, zullen de volgende gesprekken niet worden toegelaten. Een BTS is dus te modelleren als een Erlang verliessysteem. De blokkeringskans is zowel voor de operator als voor de klant een belangrijke prestatiemaat. Intensive Care Eenheid De Intensive Care eenheid (IC) vormt een belangrijke schakel binnen de keten die een patiënt kan doorlopen binnen een ziekenhuis, en ontvangt de patienten die intensieve zorg nodig hebben, bijvoorbeeld na een operatie, of als gevolg van een ongeval. De hoeveelheid IC verplegers vormt een belangrijke bottle neck. In principe wordt aan ieder IC bed een verpleger toegewezen. Patienten worden uitsluitend opgenomen op de IC, wanneer een vrij bed (vrije verpleger) aanwezig is. Zo niet, dan wordt de patient niet geaccepteerd. Dit heeft verveldende consequenties, omdat een geplande operatie waarbij na a‡oop een IC nodig is niet kan worden uitgevoerd wanneer geen IC bed beschikbaar is. Ook een patient die na een ernstig ongeval naar het ziekenhuis wordt gebracht zal worden geweigerd wanneer geen IC bed beschikbaar is. Een toegelaten patient zal het IC bed bezetten zolang intensieve zorg nodig is. Voor de wiskundige modellering van een IC is de beschikbare capaciteit (aantal bedden) van belang. Iedere patient krijgt een bed (kanaal) toegewezen. Dit bed wordt gebruikt tot het einde van de verpleging. Indien alle bedden van een IC in gebruik zijn, zullen de volgende patienten niet worden toegelaten. Een IC is dus te modelleren als een Erlang verliessysteem. De blokkeringskans is zowel voor het ziekenhuis als voor de patient een belangrijke prestatiemaat. NS Station Op het station komen treinen aan volgens een Poisson proces. Iedere trein 5
vereist een perron om passagiers te laten in en uitstappen, en bezet het perron gedurende de halteringstijd. Het NS station kan worden gemodelleerd met behulp van een variant van het Erlang verlies systeem. Uiteraard laten we in deze variant treinen die geen vrij perron aantre¤en niet verloren gaan, maar wachten op hun beurt. Internet TCP/IP Over het Internet worden tegelijkertijd …les van uiteenlopende grootte verstuurd door verschillende gebruikers. Om de capaciteit van het Internet enigszins eerlijk te verdelen over de actieve gebruikers wordt TCP/IP gebruikt. Onder dit protocol worden …les verstuurd in pakketten. Voor ieder pakket dat bij de bestemming aankomt wordt een Acknowledgement (Ack) verstuurd. Wanneer de zender van de …le een Ack ontvangt verhoogt hij de zendsnelheid, maar wanneer de Ack niet of te laat wordt ontvangen wordt dit opgevat als signaal dat het druk is op het Internet en verlaagt hij de zendsnelheid. Op deze wijze wordt de capaciteit van het Internet eerlijk verdeeld over de actieve gebruikers. Voor de wiskundige modellering van het Internet is de beschikbare capaciteit vast. Iedere te versturen …le gebruikt gelijktijdig een eerlijk deel van deze capaciteit. Het Internet onder TCP/IP is dus te modelleren als een Processor Sharing systeem. De vertraging is een belangrijke prestatiemaat. UMTS UMTS wordt de nieuwe standaard voor mobiele telefonie. In UMTS gebruiken alle gesprekken dezelfde frequentie. Om interferentie te onderdrukken worden gesprekken gecodeerd, zodanig dat een gesprek slechts een lichte ruis veroorzaakt bij een ander gesprek. Zolang de totale ruis niet te groot is kan het signaal worden gedecodeerd om zo het oorspronkelijke gesprek terug te krijgen. De totale ruis wordt bepaald door het aantal gelijktijdige gesprekken. Ieder gesprek ziet op min of meer dezelfde wijze de ruis veroorzaakt door de overige gesprekken. Dit is te vergelijken met een zaal waarin veel mensen tegelijkertijd gesprekken willen voeren. Hierbij vindt iedereen een beetje hinder van de overige gesprekken, maar zolang de totale hoeveelheid ruis onder een zekere grens blijft is communicatie mogelijk. Voor de wiskundige modellering van UMTS correspondeert de beschikbare capaciteit met de beschikbare frequentie ruimte, en ligt dus vast. Ieder gesprek gebruikt gelijktijdig een eerlijk deel van deze capaciteit. UMTS is dus te modelleren als een Processor Sharing systeem. Wireless LAN De MAC laag (Medium Access Control) van een Wireless LAN regelt de toegang van bijvoorbeeld laptops en pda’s in een WLAN netwerk zoals op de campus van de UT. Schematisch werkt dit als volgt. Iedere laptop die een …le wil verzenden luistert of er al een ander aan het zenden is. Indien dit niet het geval is, trekt de laptop een back-o¤ counter, een random getal uit een zekere range en telt vervolgens zolang er niemand aan het zenden is terug tot nul. Wanneer er wel iemand aan het zenden is, dan stopt het terugtellen. Zodra de teller op 0 6
is gekomen mag de laptop een pakket verzenden. Hierna trekt deze opnieuw een back-o¤ counter. Het kan zijn dat toevallig bij verzending toch een andere laptop aan het zenden is, maar dat dit ofwel niet gehoord is, ofwel dat deze op exact hetzelfde moment start met zenden. In dat geval gaat de transmissie verloren. De laptop trekt opnieuw een back-o¤ counter, maar dan eventueel uit een grotere range. Aangezien alle laptops dit mechanisme gebruiken komen ze min of meer even vaak aan de beurt. Voor de wiskundige modellering van het WLAN ligt de beschikbare capaciteit min of meer vast: een deel van de beschikbare capaciteit gaat verloren ten gevolge van de overhead, bijvoorbeeld veroorzaakt door het back-o¤ mechanisme. Iedere te versturen …le gebruikt gelijktijdig een eerlijk deel van deze resterende capaciteit. Het WLAN is te modelleren als een Processor Sharing systeem. De vertraging is een belangrijke prestatiemaat.
Conclusie Binnen de stochastische operationele research worden modellen ontwikkeld voor de analyse van systemen die gedreven worden door onzekerheid. Naast de in dit artikel genoemde Erlang verlies en Processor Sharing systemen worden meer gecompliceerde modellen geanalyseerd voor bijvoorbeeld netwerken van wachtrijen, en verlies netwerken. In een netwerk van wachtrijen beweegt een taak van wachtrij naar wachtrij om bij iedere wachtrij een bewerking te ondergaan. Dit model wordt veelvuldig toegepast in logistieke ketens, zoals productie systemen. In een verlies netwerk gebruikt een taak tegelijkertijd een deel van de capaciteit bij alle onderdelen op zijn route door het netwerk. Dit model is representatief voor een telefoonnetwerk, waarbij een lange afstandsgesprek overal een lijn bezet houdt. Een belangrijk onderdeel van optimalisatie van systemen gedreven door onzekerheid vormt het on-line nemen van de beslissingen. Dit is het onderwerp van studie binnen Stochastisch dynamische programmering (SDP). Hieraan sterk verwant is de stochastische speltheorie, die voor een deel kan worden gezien als SDP voor meerdere spelers. Belangrijke vraag is bijvoorbeeld hoe spelers een extra opbrengst verkregen door samenwerking onderling moeten verdelen. In een meer praktische context wordt momenteel binnen SOR gewerkt aan verdeling van extra winst verkregen door samenwerking in voorraadketens. Naast de voor de hand liggende systemen waarin onzekerheid direct herkenbaar is bestaan ook zeer interessante systemen waarin de onzekerheid verborgen is. Surfgedrag op Internet kan bijvoorbeeld worden gemodelleerd met behulp van een Markov keten, en de verklaring voor het feit dat de gezochte pagina bij een Google zoekopdracht vrijwel altijd bovenaan staat moet gezocht worden in de theorie van Markov ketens. Stochastische Operationele Research is een fascinerend vakgebied met vele gezichten waarvan de toepassingen in onze samenleving een belangrijke rol spelen.
7
