Lindley-type recursions

In dit proefschrift staat de volgende Lindley-achtige recursie centraal: Wn+1 = max{0,Bn+1 - An -Wn}. (1) Deze "niet-stijgende" recursie is belangrijk in de analyse van systemen waarbij een bediende alterneert tussen twee bedieningsstations. Een station biedt ruimte voor ´e´en klant. De bediende alterneert tussen beide stations en bediend ´e´en klant per keer. Aangenomen wordt dat voortdurend bij beide stations klanten staan te wachten. Zodra een wachtende klant een station betreed, begint de eerste fase van zijn bediening, die bestaat uit een voorbereidende fase. De bediende is hier niet bij betrokken: pas nadat de voorbereidende fase is afgerond kan een klant aan de tweede fase van zijn bediening beginnen, welke wordt uitgevoerd door de bediende. Dus de eigenlijke bediening bestaat alleen uit de tweede fase. Het kan voorkomen dat de bediende moet wachten totdat de voorbereiding van de volgende klant is afgelopen. We zijn dan ook ge¨interesseerd in de wachttijd van de bediende. Als Bn de voorbereidingstijd is voor de n-de klant en An de bedieningstijd is van de n-de klant, dan kan de wachttijd van de bediende voor de (n + 1)-ste klant beschreven worden door middel van Recursie (1). Een belangrijke observatie is dat deze recursie vrijwel identiek is aan Lindley’s recursie. Het enige verschil is het min-teken voor Wn. Dit model is gemotiveerd door diverse toepassingen waarvan er twee worden besproken in Hoofdstuk 1. De eerste toepassing betreft oog-operaties. De tweede toepassing is gerelateerd aan carousel systemen. Dit soort systemen zijn uitgebreid bestudeerd; Sectie 1.3 geeft een literatuuroverzicht. Verderop in dit hoofdstuk geven we een gedetailleerde modelbeschrijving en noemen we enkele verschillen tussen de analyse van dit model en het standaard wachtrijmodel. Hoofdstuk 2 bestudeert enkele algemene eigenschappen van Recursie (1), zoals de stabiliteit van het systeem, existentie van een evenwichtsverdeling, convergentie naar deze verdeling als n naar oneindig gaat en het staartgedrag en de covariantie functie van de verdeling van de wachttijd van de bediende. Een rode draad in dit proefschrift is de afleiding van de evenwichtsverdeling van de wachttijd van de bediende. In de volgende drie hoofdstukken leiden we deze verdeling af onder diverse aannames over de verdeling van de voorbereidingstijd en bedieningstijd van een generieke klant. We bestuderen gevallen die analoog zijn aan de klassieke M/G/1, G/PH/1 en PH/P/1 wachtrijmodellen, waarbij "P" staat voor polynomiale verdelingen. Ge¨inspireerd door de toepassingen van ons model, bekijken we enkele prestatiematen voor dit systeem, zoals de doorzet. Dit maakt een vergelijk met de prestatie van niet-alternerende systemen mogelijk. In Hoofdstuk 6 onderzoeken we methoden om de wachttijdverdeling te benaderen door de verdeling van de voorbereidingstijd of bedieningstijd te benaderen met een verdeling die exacte berekeningen mogelijk maakt. We beschrijven hoe zo’n verdel- ing kan worden gevonden en we geven een bovengrens voor de fout tussen de werkelijke wachttijdverdeling en zijn benadering. In alle voorgaande hoofdstukken hebben we aangenomen dat alle voorbereidingstijden en bedieningstijden onafhankelijk van elkaar zijn. In Hoofdstuk 7 laten we deze aanname vallen. We onderzoeken twee specifieke vormen van afhankelijkheid tussen deze variabelen. Voor beide vormen leiden we opnieuw de limietverdeling af van de wachttijd van de bediende. Hoofdstuk 8 analyseert een recursie welke een uitbreiding is van zowel Lindley’s recursie als (1). We bekijken, namelijk, de recursie Wn+1 = max{0,Bn+1 - An + YnWn}, met Yn een stochastische variabele die zowel de waarde 1 als -1 kan aannemen. Voor deze recursie onderzoeken we stabiliteit, en we berekenen de limietverdeling in twee specifieke gevallen, waarmee we de bestaande theorie voor Lindley’s recursie en Recursie (1) generaliseren. De analyse maakt duidelijk dat de technieken voor het analyseren van (1) en voor het analyseren Lindley’s recursie moeten worden gecombineerd. Diverse methoden om Lindley’s recursie te analyseren zijn ook nuttig voor de analyse van (1). Wanneer we aannemen dat de voorbereidingstijd een fase-type verdeling heeft, dan reduceert de analyse van (1) tot de analyse van een Markovketen met eindige toestandsruimte. Ook kunnen Laplace-transformaties of Wiener- Hopf technieken in diverse gevallen worden toegepast (cf. Sectie 1.6). In andere gevallen moet een niet-standaard differentiaalvergelijking worden opgelost, of moet uitgeweken worden naar een iteratieve benadering van de wachttijdverdeling. In Hoofdstuk 5 dient ook een speciale klasse van verdelingen ge¨introduceerd te worden die het mogelijk maakt om een Fredholm vergelijking op te lossen. In de meeste gevallen zijn de resultaten expliciet of kunnen worden weergegeven in termen van de oplossing van een lineair stelsel vergelijkingen, zie bijvoorbeeld Stelling 4.8. Het proefschrift wordt afgesloten met enkele afsluitende opmerkingen en diverse suggesties voor verder onderzoek.