Stokastisk schemaläggning

Stokastisk schemaläggning avser schemaläggningsproblem som involverar slumpmässiga attribut, såsom slumpmässiga behandlingstider, slumpmässiga förfallodatum, slumpmässiga vikter och stokastiska maskinhaverier. Stora tillämpningar uppstår inom bland annat tillverkningssystem, datorsystem, kommunikationssystem, logistik och transporter och maskininlärning.

Introduktion

Syftet med de stokastiska schemaläggningsproblemen kan vara regelbundna mål som att minimera den totala flödestiden, makespan eller den totala senkostnaden för att missa förfallodatum; eller kan vara oregelbundna mål som att minimera både tidiga och sena kostnader för att slutföra jobben, eller den totala kostnaden för att schemalägga uppgifter under sannolikt ankomst av en katastrofal händelse som en kraftig tyfon.

Prestandan hos sådana system, utvärderad av ett regelbundet prestationsmått eller ett oregelbundet prestationsmått, kan påverkas avsevärt av den schemaläggningspolicy som antas för att över tiden prioritera jobbens tillgång till resurser. Målet med stokastisk schemaläggning är att identifiera schemaläggningspolicyer som kan optimera målet.

Stokastiska schemaläggningsproblem kan klassificeras i tre breda typer: problem som rör schemaläggningen av ett parti med stokastiska jobb, problem med flerarmade banditer och problem som rör schemaläggning av kösystem. Dessa tre typer är vanligtvis under antagandet att fullständig information är tillgänglig i den meningen att sannolikhetsfördelningarna för de inblandade slumpvariablerna är kända i förväg. När sådana fördelningar inte är fullständigt specificerade och det finns flera konkurrerande distributioner för att modellera de slumpmässiga variablerna av intresse, hänvisas problemet till som ofullständig information. Den Bayesianska metoden har använts för att behandla stokastiska schemaläggningsproblem med ofullständig information.

Schemaläggning av ett parti stokastiska jobb

I denna klass av modeller måste en fast sats av $n$ jobb med slumpmässiga processtider, vars fördelningar är kända, slutföras av en uppsättning $m$ maskiner för att optimera ett givet prestandamål.

Den enklaste modellen i den här klassen är problemet med att sekvensera en uppsättning av $n$ jobb på en enda maskin för att minimera den förväntade viktade flödestiden. Jobbbehandlingstider är oberoende slumpvariabler med en generell fördelning $G_{i}(\cdot )$ med medelvärde $p_{i}$ för jobb $i$ . Tillåtna policyer måste vara icke-förutseende (schemaläggningsbeslut baseras på systemets historik fram till och med nuvarande tidpunkt) och icke förebyggande (bearbetning av ett jobb måste fortsätta oavbrutet till slutförandet när det väl har påbörjats).

Låt $w_{i}\geq 0$ beteckna kostnadstakten per tidsenhet i systemet för jobb $i$ , och låt ${\tilde {C}} _{i}$ anger dess slumpmässiga slutförandetid. Låt $\Pi$ beteckna klassen för alla tillåtna policyer, och låt $E_{\pi }[\cdot ]$ beteckna förväntan under policy $\pi \in \Pi$ . Problemet kan anges som

$$\min _{\pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}}_{1}]+\cdots +w_{n}E_{\pi }[ {\tilde {C}}_{n}].$$

Den optimala lösningen i det speciella deterministiska fallet ges av Smiths Shortest Weighted Processing Time-regel: sekvens jobb i icke-ökande ordning av prioritetsindex w i p i {\ $}p_{i}}$ . Den naturliga förlängningen av Smiths regel är också optimal för ovanstående stokastiska modell.

Generellt sett är regeln som ger högre prioritet till jobb med kortare förväntad handläggningstid optimal för flödestidsmålet under följande antaganden: när alla jobbbehandlingstidsfördelningar är exponentiella; när alla jobb har en gemensam allmän handläggningstidsfördelning med en icke-minskande riskhastighetsfunktion; och när fördelningar av jobbbehandlingstid är stokastiskt ordnade.

Flerarmade banditproblem

Flerarmade banditmodeller bildar en speciell typ av optimal resursallokering (som vanligtvis arbetar med tidstilldelning), där ett antal maskiner eller processorer ska allokeras för att tjäna en uppsättning konkurrerande projekt (benämnt som armar). I det typiska ramverket består systemet av en enda maskin och en uppsättning stokastiskt oberoende projekt, som kommer att bidra med slumpmässiga belöningar kontinuerligt eller vid vissa diskreta tidpunkter när de serveras. Målet är att maximera de förväntade totala rabatterade belöningarna över alla dynamiskt reviderbara policyer.

Den första versionen av multi-bandit problem formulerades inom området sekventiell design av Robbins (1952). Sedan dess hade det inte skett några väsentliga framsteg på två decennier, tills Gittins och hans medarbetare gjorde hyllade forskningsresultat i Gittins (1979), Gittins och Jones (1974), Gittins och Glazebrook (1977) och Whittle (1980) under Markov och semi-Markov inställningar. I denna tidiga modell modelleras varje arm av en Markov- eller semi-Markov-process där tidpunkterna för att göra tillståndsövergångar är beslutsepoker. Maskinen kan vid varje epok välja en arm att tjäna med en belöning representerad som en funktion av det aktuella tillståndet för den arm som bearbetas, och lösningen kännetecknas av allokeringsindex som tilldelas varje tillstånd som endast beror på armarnas tillstånd. Dessa index är därför kända som Gittins-index och de optimala policyerna brukar kallas Gittins indexpolicyer , på grund av hans välrenommerade bidrag.

Strax efter Gittins uppsats undersökte Whittle (1981) utvidgningen till problem med förgrenade banditer till att modellera stokastiska ankomster (även känd som problemet med öppen bandit eller arm förvärvande bandit). Andra förlängningar inkluderar modellerna av restless bandit, formulerade av Whittle (1988), där varje arm utvecklas rastlöst enligt två olika mekanismer (tommode och upptaget mode), och modellerna med bytekostnader/förseningar av Van Oyen et al. (1992), som visade att ingen indexpolicy är optimal när byte mellan armar medför kostnader/förseningar.

Schemaläggning av kösystem

Modeller i denna klass handlar om problemen med att designa optimala servicediscipliner i kösystem, där jobben som ska slutföras anländer till slumpmässiga epoker över tid, istället för att vara tillgängliga i början. Huvudklassen av modeller i den här miljön är den för multiclass queuing networks (MQNs), allmänt tillämpade som mångsidiga modeller av datorkommunikation och tillverkningssystem.

De enklaste typerna av MQN innebär att schemalägga ett antal jobbklasser på en enda server. På samma sätt som i de två modellkategorier som diskuterats tidigare har enkla prioritetsindexregler visat sig vara optimala för en mängd olika sådana modeller.

Mer allmänna MQN-modeller involverar funktioner som övergångstider för att byta tjänst från en jobbklass till en annan (Levy och Sidi, 1990), eller flera bearbetningsstationer, som tillhandahåller service till motsvarande icke-överlappande delmängder av jobbklasser. På grund av svårigheterna med sådana modeller har forskare strävat efter att utforma relativt enkla heuristiska policyer som uppnår en prestanda nära optimal.

Stokastisk schemaläggning med ofullständig information

Majoriteten av studierna av stokastiska schemaläggningsmodeller har till stor del etablerats utifrån antagandet om fullständig information, i den meningen att sannolikhetsfördelningarna för de inblandade slumpvariablerna, såsom bearbetningstiderna och maskinens upp-/stopptider, är fullständigt specificerade a priori .

Det finns dock omständigheter där informationen endast är delvis tillgänglig. Exempel på schemaläggning med ofullständig information finns i miljösanering, projektledning, petroleumprospektering, sensorschemaläggning i mobila robotar och cykeltidsmodellering, bland många andra.

Som ett resultat av ofullständig information kan det finnas flera konkurrerande distributioner för att modellera de slumpmässiga variablerna av intresse. Ett effektivt tillvägagångssätt har utvecklats av Cai et al. (2009), för att ta itu med detta problem, baserat på Bayesiansk informationsuppdatering. Den identifierar varje konkurrerande distribution genom att realisera en slumpvariabel, säg $\Theta$ . Inledningsvis $\Theta$ en tidigare fördelning baserad på historisk information eller antagande (vilket kan vara icke-informativt om ingen historisk information är tillgänglig). Information om $\Theta$ kan uppdateras efter att realiseringar av de slumpmässiga variablerna har observerats. En viktig fråga vid beslutsfattande är hur man använder den uppdaterade informationen för att förfina och förbättra besluten. När schemaläggningspolicyn är statisk i den meningen att den inte förändras över tiden, identifieras optimala sekvenser för att minimera den förväntade rabatterade belöningen och stokastiskt minimera antalet sena jobb under ett vanligt exponentiellt förfallodatum. När schemaläggningspolicyn är dynamisk i den meningen att den kan göra justeringar under processen baserat på uppdaterad information, utvecklas posterior Gittins index för att hitta den optimala policyn som minimerar den förväntade rabatterade belöningen i klassen dynamiska policyer.