Vi modellerar ett enhop mobilt nätverk under centraliserad kontroll med N serviceklasser som ett system av N viktade kostnadsparallell köer med M~1  på M  på N! servrar, ankomster, varierande binär konnektivitet, och Bernoulli service framgång vid varje kö+ Vi anser schemaläggning problem i detta system och, under olika antaganden om ankomster och konnektivitet, härleda villkor tillräckliga, men inte nödvändiga, för att garantera optimaliteten av en index policy+ Överväg ett system av N-mobiler som kommunicerar i diskret tid med en central nätverk controller~e+g+, basstation eller satellit! som har M-kanaler för meddelandekommunikation+ Vid varje tillfälle överför varje mobil en kort kontrollpuls~mes-ålder! Till controllern; Kontrollmeddelandet innehåller information om typ och antal datameddelanden mobilen vill skicka till controllern+ Om styrmeddelandet tas emot av controllern, är mobilen ansluten till controllern för *Denna forskning stöddes delvis av ARO bidrag DAAH04-96/1-0377 och AFOSR beviljar F49620-96-1-0028 och F49620-98-1-0370+ Sannolikhet i ingenjörsvetenskap och informationsvetenskap, 14, 2000, 259-277+ 259 att time slot+ Därför vet controllern vid varje tidpunkt slot de mobiler som är anslutna till den, och den typ och mängd information varje mobil måste överföra+ Baserat på denna information, controllern måste besluta hur man dynamiskt fördela sina kanaler över tid så att det kan minimera den förväntade diskonterade viktade flödestid i samband med överföringen av meddelanden+ Vi formulerar ett abstrakt problem som fångar viktiga funktioner i singlehop nätverk beskrivs ovan, och analysera flera varianter av detta problem+ Det allmänna abstrakta problemet kan beskrivas som följer+ Vi anser att en diskret-tidsmodell av N-köer som betjänas av M~M + +! Vid varje tid betjänas vid varje server som helst kö till den mest en server kan vara en enda server. eller det är inte ~ inte ansluten!+ Varje gång, innan tilldelningen av servrar, konnektiviteten av alla köer är känd för den tiden + Vi tillåter ankomster vid varje kö vid varje tidpunkt, och ankomster vid en given tidpunkt antas ske innan servern allokering vid den tidpunkten + Statistiken över konnektivitet och ankomstprocesser antas godtycklig + När en server har tilldelats till en ansluten kö, finns det en sannolikhet, fast för varje kö, att tjänsten är framgångsrik + Denna tjänst framgångsprocessen är i+i+d+ och oberoende bland köer, även om framgångsannolikheten kan vara köberoende+ Vi vill bestämma en server tilldelningspolicy p som minimerar där F 0 summerar all information som är tillgänglig i början av tilldelningsperioden + C p är kostnaden under p, ges av b är diskonteringsfaktorn, T är den finita horisonten, c i är innehavskostnaden för kö i~Q i!, genom vilken vi skiljer tjänsteklass, och x t i är längden av Q i i vid tiden t+ I Problem~P! vi har antagit att horisonten T är ändlig+ Vi först analysera Problem~P! och dess finita horisontproblem, och sedan visa att resultaten av analysen håller för motsvarande oändliga horisontproblem+ Som nämnts, modellen som beskrivs i Problem~P! uppstår i samband med en enda-hop mobila radionät, som kan modelleras som en bank av meddelande köer som betjänas av en eller flera kommunikationskanaler+ Den varierande konnektivitet avser en mängd olika mobila kommunikationssystem, såsom cellulära och mobila paket radionät @10#, satellitkommunikation @3#, och meteor-burst kanaler @4#+ Kostnadsfunktionen återspeglar sedan straffet för att hålla paket väntar i varje kö, och kö viktning möjliggör en prioritering av paket för överföring+ Samma modell uppstår i bildbildningssystem, där servicebeslut motsvarar sensor tilldelningar för särskilda övervakningsområden för informationssamlande ändamål+ Modellen har också ett oberoende intresse som ett specifikt problem i kö teori + C. Lott och D. Tenekethis I @2,13#, problemet med N köer med olika innehavskostnader och en server med full konnektivitet övervägdes, och den enkla cμ regeln visades att vara optimal, men detta resultat inte generalisera till Problem~P!+ Vår modell liknar det i @10#, men endast en enda server och ingen differentierad tjänst anses i den artikeln + The connecty10ue! Detta är optimal+.......... som inte inkluderar differentierad tjänst+........................................................................................................................................................................................................................................................ och processorer är ändliga + Systemets stabilitet0maximal genomströmning metod som används i mycket av det arbete som just diskuterats implicit antar att alla jobb är identiska+ Detta innebär att kontroll problemet består helt och hållet i att hålla servern ~s! Den här situationen förändras när vi tillåter jobb att ha olika tjänsteklasser+ När det gäller ett multiserversystem med full anslutning med olika hållkostnader är det till exempel lätt att konstruera ett exempel där det längsta anslutna köprotokollet inte är optimalt+ Vi kan på liknande sätt konstruera ett exempel som visar att indexpolicyn inte är optimal för en enda server varierande anslutningssystem med olika hållkostnader+ Såvitt vi vet finns det för närvarande inga resultat tillgängliga för multiserverschemaläggning av parallella köer med konnektivitetsbegränsningar och flera tjänsteklasser+ I den här artikeln undersöker vi ett exempel på multiserverschemaläggning av parallella köer med konnektivitetsbegränsningar och flera tjänsteklasser+ Artikelns huvudsakliga bidrag är fastställandet av villkor för jobb~message! viktning och jobb service tider tillräckligt för att garantera optimaliteten av en index policy för Problem~P!+ Vi visar med exempel att de ovan nämnda villkoren inte är nödvändiga för att säkerställa optimalitet index policy+ Artikeln är organiserad enligt följande+ I Avsnitt 2, Problem~P! analyseras; ett villkor som är tillräckligt för att garantera optimaliteten i en indexpolicy presenteras+ I avsnitt 3, olika förbättringar till Problem~P!, inklusive mer specifika antaganden om ankomst- och anslutningsprocesser, beaktas+ Dessa förbättringar möjliggör förbättrade villkor som fortfarande är tillräckliga för att garantera optimalitet i samma index policy+ Avsnitt 4 innehåller en kort diskussion om den oändliga horisont problem och Avsnitt 5 sammanfattar artikeln+ Slutligen, tilläggen A-F ger detaljerade bevis på vissa tekniska uttalanden i huvudtexten, inte ingår där för att förbättra flödet av de grundläggande argumenten+ För att fortsätta med analysen, behöver vi följande definitioner och notation+ N Antalet köer+ M Antalet servrar+ T Längden på den ändliga tidshorisonten+ Kostnaden RV i samband med policy p, som definieras i ~2!+ Genom ett index, menar vi någon politik som fäster en fast numerisk index till varje kö och sedan spelar M anslutna och nontomy köer högsta index vid varje tidpunkt+ Indexet för en kö hänvisar till detta numeriska index, och inte kön s subscript+ Som anges i Problem~P! som för att uppnå detta, behöver vi ~ 1! ett resultat som beskriver effekten av det ursprungliga villkoret på resultatet av någon index policy p och ~ 2! ett uttryck som anger skillnaden i prestanda mellan två politikområden, säger J p och [ p, under samma ursprungliga villkor + Vi börjar med resultatet som beskriver effekten av det ursprungliga villkoret på resultatet av någon index policy p+ Bevis: För det första, notera att om x 0 i 0, vi har x 0 x 0 i och sedan lemma är tydligt sant+ Vi antar hädanefter x 0 i. 0, så att x 0 x 0 i, och fortsätta genom induktion på T+ Först, definierar vi följande händelser: A1! Samma köer betjänas av vår indexpolicy p under x 0 och x 0 i på + A2! På t 1 och M 1 av servrarna fördelas till samma köer av policy p under x 0 och x 0 i på; Mth servern tilldelas Q i under x 0 och till Q j under x 0 i på samma sätt, där Q j är av lägre index än Q i + Eftersom p är en indexpolicy, uppstår en tjänsteskillnad på t 1 endast när x 0 i  på 1, p allokerar till Q i under x 0, och, under x 0 i och p allokeras till Q j, en kö med lägre prioritet än Q i, istället för den tomma Q i + Därför, händelser~A1! Och ~A2! partition utrymmet för möjliga händelser+ Vi går nu vidare med induktionen+ Låt T 1+ Under~A1!, är kostnadsskillnaden 1 För husbilar x och y, händelse A, och s-field F, definierar vi E @y6A, x, F # att betyda E @y6A S~x! på F #+ Under~A2!, är kostnadsskillnaden eftersom tjänsten framgång antas i+i+d+ och oberoende bland köer+ Från ~5! och ~6!, induktion bas steget är etablerad + Nu, anta ~4! håller för en godtycklig T och överväga fallet med en T 1 horisont, märkning tid så att teorem är sant över 2, + + +,T  och 1+ Sedan, under~A1!, Vi har eftersom tjänsten framgång i båda fallen är samma + Genom induktionshypotesen, Under~A2!, igen eftersom tjänsten är i+i+d+ och oberoende bland köer, Vi finner att där x 1 är det tillstånd som följer av x 0 när ingen tjänst slutföras på t 1 vid Q i och Q j + Genom induktionshypotesen, och genom att tillämpa induktionshypotesen två gånger i följd, vi får Combining~10!-~13!, Vi får eftersom A1 och A2 är en partition av alla möjligheter som uppstår från tilldelningen av M-servrar under de två olika ursprungliga villkoren ~ under samma indexpolicy!,~9! Och ~ 14! innebär att och induktionssteget bevisas+ Därför är beviset för Lemma 1 komplett+ III Nästa, vi härleder ett uttryck som anger skillnaden i prestanda mellan två policyer J p och [p under samma ursprungliga villkor+ Tidigare, vi har definierat C [ p att vara kostnaden RV under [ p och C J p att vara kostnaden RV under J p+ Vi definierar nu R att vara skillnaden För att visa J p optimal, räcker det att bevisa att för någon annan tilldelning politik [ p+ För att bevisa ~16!, överväga två givna politik [ p och J p och anta att på t 1 de båda körs på samma system och att både Q i och Q j är anslutna och nonemty vid denna tid + Assume J p väljer Q i och inte Q j, och [ p väljer Q j och inte Q i at t 1 och vidare anta att alla andra server tilldelningar är samma för de två politikerna på t + 1+ Kom ihåg att h t i är tjänsten framgångsindikatorn variabel vid tiden t för Q i + Vi har där den sista jämlikhet + eftersom tjänsten är att ansluta sig och använda alla köer och oberoende Använd och oberoende Vi är helt oberoende Att bevisa huvudresultatet av detta avsnitt, som ges av följande Theorem+ Diskussion: Kärnan i resultatet av Theorem 1 är följande: Om vi var garanterade att systemet som beskrivs i Problem~P! drivs bort från gränsen hela tiden~i+e+, om köerna var kontinuerligt nontomy!, då skulle det vara optimalt att alltid allokera M-servrarna till köerna med M högsta index+ Nära gränsen, serverutnyttjande~på grund av tomma köer! blir en kritisk fråga när det gäller att bestämma en optimal serverallokeringsstrategi+ Indexpolicyn, som allokerar servrar utan att ta hänsyn till antalet kunder i köerna, kan resultera i serverunderutnyttjande; därför kan det inte vara optimalt nära gränsen+ Följaktligen, om vi kräver optimal indexpolicy för Problem~P!, måste vi identifiera villkor för att säkerställa att den fördel som uppnås genom att alltid fördela servrarna till den högsta index köer överkompenserar potentiella förluster till följd av server underutilization nära gränsen+ Ett sådant villkor uttrycks av~18!, vilket kräver att indexen i samband med köerna är tillräckligt separerade från varandra+ En sådan separation resulterar i en prioritering av köer tillräckligt för att garantera optimaliteten av indexregeln+ Det är intressant att jämföra detta resultat med fallet där alla köer har samma viktning+ Då~se @10,12#!, den optimala policyn är att tjäna de anslutna köerna av längsta längd~LCQ!+ Intuitionen här är att, vid en given tid, som betjänar någon annan, så den optimala avkastningen som tjänar, så att den optimala servern för att antalet köer som inte är tillgängliga tjänster som krävs genom att minska antalet svar. är tillräckligt kompenserad+ Mellan dessa två ytterligheter, det finns en region av kö kostnad så att dessa två konkurrerande mål konflikt, och den optimala politiken blir ganska svårt att specificera + Proof~Theorem 1!: Antag att köerna har märkts så att ~18! är nöjd+ Överväg M ytterligare köer i systemet, numrerade N  på 1, N  på 2, + +, N på M, var och en med c N på i m N på 0+ villkor ~ 18! är fortfarande nöjd med dessa extra på grund av ~18! och det faktum att ~1  på b!0@1 ~1  till m i!b# 1 + Repetition av argumentet som leder till ~19! visar att påståendet om teorem är sant för T  på 1+ Att fortsätta med induktionen, vi antar att påståendet om teorem är sant när horisonten är T och bevisa att indexpolicyn som beskrivs i beskrivningen av teorem är optimal när horisonten är T 1+ Överväg policyer [ p och J p med följande funktioner: p och J p allokera M 1 av servrarna till samma köer; M th servern tilldelas Q i av policy J p och Q j genom policy [ p, där i  på j+ Utan någon förlust av generalitet, antar vi att i  på N+ F2! Från tid t 2 on, policys J p och [ p följa den optimala fördelningspolicyn för T-horizon problem+ Vi definierar Q  på: att $ uppsättningen av köer med index större än Q j %, Q  med $ Den uppsättning köer med index lika med eller mindre än Q j %, Använda egenskaperna hos politik [ p och J p, ovanstående definitioner, och ~28! och 29!, vi fortsätter att slutföra induktionssteg genom att bestämma en lägre gräns på E @R6F 0 # at t  på 1+ För att uppnå detta, undersöker vi separat var och en av de fyra termer som visas i höger sida av ~17!+ Vi bevisar att Combining ~17! och ~30!-~33!, vi får på grund av ~28! Och ~ 29!, Den sista ojämlikheten i ~ 35! är sant eftersom tjänsten framgång vid Q i under [p är oberoende av händelsen Dh 1 i  på 1 samt den ursprungliga informationsstaten F 0, eftersom tjänsten Combining~34!-~36!, vi får och på grund av ~18!, Följaktligen, politik J p är överlägsen [ p för ~T  med1!-horizon problem+ Repetition av argumentet som leder till ~38! visar att, under~18!, index policy beskrivs i uttalandet av theorem är optimal för ~T 1!-horisont problem+ För att slutföra beviset för induktionssteg, måste vi bevisa ~30!-~33!+ Bevisen för dessa ekvationer finns i tillägg A-D+ Med~30!-~33!, induktionssteget är komplett och theorem bevisas+ III Anmärkning: Utbyte argument som används för att bevisa optimaliteten av cm regeln i @2# kan inte tillämpas på fallet med antingen multiserver eller varierande anslutning, eftersom det inte är möjligt att garantera att en sådan utbytestid inträffar+ Vi presenterar två exempel för att illustrera rollen av villkor ~18!+ Det första exemplet visar att om villkor~18! är inte nöjd, indexpolicyn är i allmänhet inte optimal+ Det andra exemplet visar att villkor ~18! är inte nödvändigt för att garantera optimaliteten i indexpolicyn+ Exempel 1: Låt T  på 2, N på 2, M på 1, m 1 på m 2 på 1, x 0 1 på x 0 2 på 1, c 1 c 2 0+9c 1, och b på 0+5+ Antag att det inte finns några ankomster, och konnektivitet är i+i+d+ med q 1 och q 2 på 0+5+ Sedan, och Från ~39! Och ~ 40!, vi drar slutsatsen att Q 1 har högre index, men villkor ~ 18! av Theorem 1 är inte nöjd + Denote av J p index policy~i+e+, den policy som ger prioritet till Q 1 när båda köer är anslutna och nontomy!, och av [ p, den policy som ger prioritet till Q 2 när båda köer är anslutna och nontomy+ Sedan, J p är icke-optimal, eftersom i det fall där båda köer är initialt anslutna, Exempel 2: Betrakta samma situation som i Exempel 1 med en skillnad: c 2 0+7c 1 + Då, ~39! är giltig och villkor ~18! av Theorem 1 är inte nöjd eftersom Icke desto mindre indexpolicyn J p är optimal eftersom resultatet av Theorem 1 kan grafiskt beskrivas för ett system som består av två köer ~N 2! + Den grafiska beskrivningen är baserad på följande sammanfattning av resultatet av Theorem 1 för detta fall+ När båda köerna är anslutna vid en given tidpunkt, Om vi anser c 2 m 2 fast och föreställa sig varierande c 1 m 1, sedan, på grund av ~ 42! och ~43!, utrymmet för möjliga värden på c 1 m 1 är uppdelad i tre regioner ~visas i Fig+ 1!: 1! Vad är det för fel på dig? Servera Q 1 när båda köerna är anslutna; ~ 2! tjäna Q 2 när båda köerna är anslutna; ~3! optimal politik är ospecificerad+ Den tredje regionen finns eftersom ~42! Och ~ 43! inte täcka alla möjligheter+ Intuitionen som utvecklats från detta enkla fall sträcker sig naturligt till det allmänna fallet+ Observera att som br 0, regionen i Figur 1 där den optimala politiken inte anges blir tom+ Detta är den situation där framtida kostnader inte har någon effekt på nuvarande beslut, och så den bästa politiken minimerar kostnaden vid den aktuella tidpunkten steg bara+ För detta fall, den optimala politiken är en girig algoritm~i+e+, cm regeln!+ 270 C. Lott och D. Teneketlis Condition~18!, vilket är tillräckligt för att säkerställa optimal indexpolicy för Problem~P!, härleddes under inga antaganden om ankomst- och anslutningsprocesser+ Resultatet av Theorem 1 kan stärkas under uttryckliga antaganden om de ovan nämnda processerna+ I detta avsnitt undersöker vi flera fall av Problem~P! som uppstår under olika antaganden om ankomst- och anslutningsprocesser+ Vi visar att villkor ~18! kan förbättras när mer information ges om ankomst och0eller anslutningsprocesser+ Som en påminnelse, antagandet av i+i+d+ tjänsten innehar under hela denna del av artikeln+ Vi antar i+i+d+ kö anslutning, oberoende av tjänsten framgångsprocessen, men lämna ankomster godtyckligt+ Vi kräver inte oberoende av anslutning mellan köer, endast i+i+d+ för varje given kö, och oberoende av tjänsten framgång för alla köer+ Vi bevisar följande variant av Theorem 1+ Bevis: Vi antar~44! är nöjd och gå vidare genom induktion+ Vi visar först att för T  på 1, resultatet av Theorem 2 är sant under ~ 44! och sedan att induktionssteget håller + Först, notera att Så om ~44! är nöjd, då nödvändigtvis m i c i  ska m j c j + Då, för T 1 är beviset på resultatet av teorem samma som i Theorem 1+ Vi fortsätter med induktionssteget+ Först, notera att argumenten som leder tõ 34! beror inte på den specifika formen av ~18!; Därför är samma argument giltiga här också + Så, ~ 34! Is true+ Definiera Precis som för t 1, vi definierar t 3  på 1 när t 3 T+ Som tidigare, vi vet att t 1 t s a+s+, där t s definieras av~26!+ Vi har också att t s 3 a+s+, som följer direkt från deras definitioner+ Dessutom, genom sin definition, oberoende tjänsteframgångar, och i+i+d+ typ av anslutning vid Q i, t 3 är oberoende av andra systemprocesser+ Vi får därmed Nästa, vi beräknar höger sida av ~46!: På grund av ~46! Och ~ 47!, 272 Kombinera ~ 34! Och ~ 48!, Ojämlikhet ~ 44! då innebär DJ 0, och induktionssteget kompletteras med argument som är identiska med de följande ~38! i beviset för Theorem 1+ Under det ytterligare antagandet av i+i+d+ konnektivitet, Theorem 2 ger en förbättrad tillräcklighet villkor över Theorem 1+ För fast q i m i, precis som tidigare, b r 0 innebär en omversion av cm regel + Skillnaden mellan problemet som beaktas i detta avsnitt och Problem~P! is that in the "sufficiency factor" ~1 påb!0@1 påm i!b#, som beskriver uppdelningen av index i ~18!, m i är ersatt av q i m i + Därför, den takt med vilken Q i kan serveras minskas med både konnektivitet och service sannolikhet, och detta leder till ett tillstånd som är svagare ~i+e+, bättre! Det är mer än 18! och är tillräckligt för att garantera optimalitet index policy+ I motsats till Avsnitt 3+1, här antar vi Bernoulli ankomster och godtycklig konnektivitet+ Ankomsterna behöver inte vara oberoende bland köer+ Vi bevisar följande variant av Theorem 1+ Bevis: Vi börjar med ~34! eftersom argumenten som leder till det är som i beviset för Theorem 1+ Antag ~49! är nöjd och notera att Då, nödvändigtvis  skai, j, m i c i  och m j c j + Sedan, för T 1 kan påståendet om teorem fastställas på samma sätt som i Theorem 1+ För att bevisa induktionssteg, vi börjar med ~34! och definiera stopptiderna: Precis som tidigare, definierar vi t 3 A+s+ @t 1 definieras av~22!#, som ett minimikrav för t 1 A + t är att Q i vara tom för J P och tjänsten är möjlig på t + Om en ankomst just inträffade, kö inte kan vara tom + Också från definitionerna, är det omedelbart att t 3  på 4 a+s+ Dessutom, genom sin definition, oberoende av tjänsten framgång, och i+i+d+ typ av ankomster till Q i, t 4 är oberoende av andra systemprocesser + Därför, vi får Letting S a i  och i, sannolikheten för ingen ankomst, vi får för höger sida av 52!, På grund av ~52! och ~ 53!, 274 Kombinera ~ 34! Och ~ 54!, vi hittar det villkor ~ 49! då innebär DJ  på 0, och resten av induktionssteg följer som i Theorem 1+ III I detta avsnitt antar vi både Bernoulli köer anslutning och Bernoulli ankomster+ Sedan får vi följande villkor som är tillräckligt för att garantera optimaliteten av en index policy+ Bevis: Vi antar ~55! är nöjd och notera att då, c i m i c j m j, i, j, i j, och för T 1 beviset för Theorem 4 är samma som för Theorem 1+ För att fastställa induktionssteg, Vi noterar att argumenten som leder till ~34! är samma som i Theorem 1 och definiera stopptiden t 5 min$t 2: det finns en tjänsteframgång och ingen ankomst till Q i under [p6Q i är alltid serveras när ansluten under [ p% och låt t 5  på T 1 när t 5 T+ Från definitionerna, det följer att t 1  på 5 a+s+ Observera att för i+i+d+ ankomster och konnektivitet, systemet är en Markov kedja, och så F 0 information sammanfattas i x 0 ; från sin definition, t 5 är oberoende av den ursprungliga tillstånd och tjänsteframgång på t  och 1+ Följaktligen, Låta S a i  och i, sannolikheten för ingen ankomst, vi får för höger sida av 56!, På grund av ~56! Och ~57! och Markovian egendomen i systemet, Combining ~ 34! Och ~ 58!, vi hittar villkor ~ 55! Då innebär DJ  till exempel 0, och resten av induktionssteget är detsamma som i Theorem 1+ Vi kan förbättra resultatet av Theorem 4 genom att utföra en mer noggrann analys av en första slagtid bundet för t 1 + Det resulterande tillräckliga villkoret är mer avslappnad än ~ 55!, men uttrycket som beskriver villkoret är mer komplicerat och mindre intuitivt+ och för alla ändliga dimension L, definiera L  på L-matris A i som då, när som helst t, det är optimalt att tjäna M anslutna köer av högsta index, eller tjäna alla köer om mindre än M är anslutna+ Ytterligare, är "tillräcklig faktor" monoton i storleken på A i ; det vill säga, Bevis: Beviset för Theorem 5 ges i bilaga E+ I detta avsnitt, vi släppa i+i+d+ antagande om ankomster och konnektivitet+ Under vissa statistiska antaganden om ankomst och konnektivitet processer, som anges exakt i följande Theorem, vi härled ett tillstånd tillräckligt för att garantera optimalitet index policy beskrivs i Avsnitt 2+ Vi visar att detta tillstånd förbättrar ~18+ i den, och T +. Och Conditioñ D1! i @7# ge villkor på drift av en process $x t, t  på 0%; de skiljer sig i sina krav på riktningen för den drift bundna + 2+ I allmänhet är det svårt att uttryckligen ange h i och r i som uppfyller ~ 64! och ge det optimala tillståndet i ~65! och ~66!, även om de kan fastställas numeriskt + 3+ Som exempel, från ~65! Vi kan uppnå tillståndet ~18! När h i  på ln b och r i 10b ~ 10m i!Detta ger en r i 1 endast när det är lättare att kontrollera och innebär ~ 64!+ Det kan dock finnas fall där ~ 64! är nöjd och ~67! är inte+ Vi sammanfattar resultaten i tabell 1+ Från tabellen, och från tidigare derivationer, observerar vi att alltid och under vissa villkor ~E1! De "tillräckliga faktorerna" som visas i tabellen anger hur mycket indexen för olika köer måste skiljas från varandra för att garantera att indexpolicyn är optimal+ Ovanstående ojämlikheter är intuitivt tilltalande eftersom de visar att som den statistiska beskrivningen av sys- godtyckliga ankomster, godtycklig konnektivitet tem blir mer detaljerad, de tillräckliga förutsättningarna för optimalitet indexpolicyn förbättras; det vill säga den ytterligare statistiska informationen om systemet används för att minska separationen mellan köernas index medan optimaliteten i indexpolicyn upprätthålls+ Kommentar: Observera att antalet servrar M aldrig uttryckligen anges i argumenten för bevisen i avsnitten 2 och 3+ Därför tror vi att även när antalet servrar är en slumpmässig funktion av tiden, de villkor som är tillräckliga för att garantera optimalheten av cm regeln för kanal tilldelningsproblem som beskrivs i denna artikel är desamma som de som visas i tabell 1+ 4. INFINITE HORIZON Indexpolicyn som beskrivs i avsnitt 2 är optimal för alla finit-horisontella problem under villkoren i Theorems 1-6+ Eftersom villkoren för dessa teorem inte beror på horisonten T, kan man med ett enkelt motsättningsargument bevisa att samma indexpolicy är optimal för motsvarande oändliga horisontproblem under samma villkor+ Vi har visat att det finns villkor på systemparametrar som garanterar optimalheten av en indexpolicy för N-queue M-server-systemet med ankomster och varierande konnektivitet+ Dessa villkor beror på de statistiska antaganden som gjorts för problemet, liksom värdet av nyckelsystemparametrar, såsom ankomsthastighet, anslutningsannolikhet och servicesannolikhet+ Intresset för detta problem uppstår från dess tillämplighet på flera viktiga system, inklusive mobila kommunikationsnätverk under centraliserad kontroll och bildbildningssystem+
I REF formulerades problemet med tilldelning av flera kanaler för mobila enhop-nät med flera tjänsteklasser som en RMBP, och tillräckliga villkor för att en indexpolicy av myopisk typ skulle vara optimal fastställdes.
2000), ‘On the Optimality of An Index Rule in Multichannel Allocation for Single-Hop Mobile Networks with Multiple Service Classes
{'venue': 'Probability in the Engineering and Informational Sciences', 'journal': None, 'mag_field_of_study': ['Mathematics']}