Queues with state-dependent rates

Abstract

In klassieke wachtrijmodellen wordt aangenomen dat de bediende op constante snelheid werkt zolang er werk in het systeem aanwezig is. Er zijn echter tal van situaties waar deze aanname niet opgaat, zoals in productiesystemen, waterreservoirs of communicatienetwerken. Bovendien kan de aankomstintensiteit van nieuwe klanten worden be????nvloed door de mate van congestie in het systeem. In dit proefschrift concentreren we ons daarom speci??ek op wachtrijen met toestandsafhankelijke snelheden. We onderscheiden in dit proefschrift drie belangrijke toepassingsgebieden. Als eerste noemen we productiesystemen waarbij de productiviteit van het personeel afhangt van de aanwezige hoeveelheid werk. In de psychologie wordt de relatie tussen werkdruk en productiviteit beschreven door de Yerkes Dodson wet: In eerste instantie leidt een hogere werkdruk tot een verbeterde productiviteit, maar bij een aanhoudende stijging van de aanwezige hoeveelheid werk krijgen stressfactoren de overhand, resulterend in een scherpe productiviteitsdaling. Een tweede toepassingsgebied van modellen met toestandsafhankelijke snelheden zijn communicatienetwerken waarbij het verzendingsprotocol reageert op drukte in het netwerk. Een duidelijk voorbeeld hiervan is het veel gebruikte Transmission Control Protocol (TCP), waarbij informatie over netwerkcongestie de basis vormt voor de bepaling van de verzendingssnelheid van Internetverkeer. In hoofdstuk 7 richten we ons speci??ek op de integratie van verkeersstromen van verschillende aard met uiteenlopende kwaliteitseisen. Als derde toepassing noemen we de studie van waterreservoirs, en opslagmodellen in het algemeen. Instromend water als gevolg van hevige regenval wordt opgevangen in een reservoir, terwijl de uitstroomsnelheid afhangt van de watervoorraad achter de dam. Deze toepassing is van een meer wiskundige aard en is met name vanuit een historisch perspectief van groot belang. In hoofdstuk 1 geven we verdere achtergrondinformatie over de bovengenoemde drie toepassingsgebieden en bespreken we de relatie tot wachtrijmodellen met toestandsafhankelijke snelheden. Verder demonstreren we verschillende methoden uit het proefschrift aan de hand van de klassieke M/G/1 rij. De daaruit voortvloeiende bekende M/G/1 resultaten kunnen tevens worden gebruikt als referentie voor resultaten in latere hoofdstukken. De voornaamste prestatiemaat in dit proefschrift is de verdeling van de hoeveelheid werk (ook wel werklast genoemd) in de evenwichtssituatie. In hoofdstuk 2 bestuderen we allereerst de M/G/1 wachtrij met werklastaf hankelijke aankomst- en bedieningssnelheden. Dit model hangt nauw samen met het hierboven besproken waterreservoir waarbij de uitstroomsnelheid afhangt van de inhoud van het reservoir. Het belangrijkste resultaat is de relatie tussen grootheden, zoals de werklastverdeling, in twee verwante M/G/1 wachtrijen. Daarnaast werken we enkele speciale gevallen verder uit. Vervolgens beschouwen we het algemenere G/G/1 model en geven we relaties tussen de werklast op verschillende momenten. In hoofdstuk 3 breiden we het M/G/1 model van hoofdstuk 2 uit door verschillende begrenzingen (of toelatingseisen) op de werklast toe te staan. We kijken daarbij opnieuw naar de relatie tussen grootheden in verwante M/G/1 wachtrijen en laten verder zien dat de werklastverdeling voor een aantal M/G/1 rijen met beperkte toelating proportioneel is aan de werklastverdeling van het model zonder toelatingsrestrictie. Tevens beschouwen we de verdeling van een andere prestatiemaat, het cycle maximum. Het cycle maximum is de maximale hoeveelheid werk gedurende een busy cycle (de periode dat de bediende onafgebroken werkt). We besluiten het hoofdstuk door een aantal speciale gevallen uit te werken. Het cycle maximum speelt ook een centrale rol in hoofdstuk 4. We bestuderen daar een G/G/1 rij met eindige bu??er en analyseren de relatie tussen de kans dat een klant niet volledig wordt geaccepteerd (de verlieskans) en de staartkans van het cycle maximum in de daarbij behorende rij met oneindige bu??er. Voor het klassieke G/G/1 model laten we zien dat deze twee kansen identiek zijn. In het model waarbij de bedieningssnelheid afhangt van de aanwezige hoeveelheid werk zijn de staartkans van het cycle maximum en de verlieskans op een iets ingewikkeldere manier gerelateerd. Tenslotte passen we deze relaties toe om resultaten te verkrijgen voor de verlieskans in modellen waar de verdeling van het cycle maximum bekend is en vice versa. Hoofdstuk 5 betreft opnieuw een M/G/1 rij met werklastafhankelijke bedieningssnelheden. Mede ge????nspireerd door de hierboven beschreven productiviteitspatronen in, bijvoorbeeld, productiesystemen, richten we ons speci??ek op bedieningssnelheden die eerst stijgen en dan dalen als functie van de aanwezige hoeveelheid werk. Besturing van het systeem vindt plaats door het al dan niet toelaten van klanten afhankelijk van de werklast bij aankomst, met als doel de lange-termijn gemiddelde hoeveelheid afgehandeld werk (ofwel de throughput) te maximaliseren. We laten zien dat, onder bepaalde voorwaarden, een drempelwaarde strategie voor het accepteren van klanten optimaal is. We geven ook een karakterisering van de optimale drempelwaarde, waarvan de berekening in bepaalde gevallen reduceert tot de oplossing van een betrekkelijk eenvoudige vergelijking. In de bovengenoemde hoofdstukken 2{5 hebben we steeds verondersteld dat de bedieningssnelheid op elk moment (en continu door de tijd) kan worden aangepast. In verschillende praktische situaties kan het echter voorkomen dat niet op elk moment informatie over de toestand van het systeem aanwezig is, of dat er hoge kosten gepaard gaan met het continu aanpassen van de bedieningssnelheid. In hoofdstuk 6 nemen we daarom aan dat de snelheid van bediening alleen op momenten direct na een aankomst kan worden gewijzigd, terwijl deze constant wordt gehouden tussen aankomsten van klanten in. Voor het geval van bedieningsdisciplines met ??e??en of meer drempelwaarden vinden we de verdeling en de getransformeerde van de hoeveelheid werk in het systeem op verschillende momenten. Tenslotte richten we ons in hoofdstuk 7 op een toepassing op het gebied van communicatienetwerken. We beschouwen twee typen verkeer, stromend en elastisch, die capaciteit delen volgens de Processor Sharing (PS) discipline. De PS discipline is een natuurlijke manier om het delen van capaciteit tussen TCP en TCP-friendly gestuurd Internetverkeer te modelleren. Bovendien nemen we aan dat het verkeer van de elastische klasse zwaarstaartig is en dat de verbinding kritiek belast is. Het belangrijkste resultaat betreft de werklast asymptotiek van de stromende klasse. Deze prestatiemaat is met name interessant omdat de werklast kan worden ge????nterpreteerd als een bedieningstekort ten opzichte van een ideaal scenario. Verder geven we ook verschillende resultaten voor de elastische klasse. We merken op dat het model van dit hoofdstuk ook opgevat kan worden als een waterreservoir of vloeistofmodel in een zwaarstaartige stochastische omgeving. Die omgeving bestaat dan uit de elastische klanten, terwijl de bedieningssnelheid, of uitstroomsnelheid, van de dam gelijk is aan die van een permanent aanwezige klant in een G/G/1 rij bediend volgens de PS discipline.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 16 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.