Vi studerar ett online jobb schemaläggning problem som motiveras av storyboarding i webbreklam, där en annonsör får värde från oavbruten sekventiell tillgång till en användare surfa på webben. Användaren upphör att bläddra med sannolikhet 1 − β vid varje steg, oberoende. Berättelser (jobb) anländer online; jobb s har längd s och per enhet värde v s. Ett värde v s erhålls för varje enhet av jobbet som schemaläggs i följd utan avbrott, diskonteras för den tid vid vilken det är schemalagt. Arbetstillfällen kan förebyggas, men inget ytterligare värde kan härledas från de återstående oplanerade arbetsenheterna. Vi söker en online-algoritm vars totala belöning är konkurrenskraftig mot den offline schemaläggaren som vet alla jobb i förväg. Vi överväger två modeller baserade på den maximala fördröjning som kan tillåtas mellan ankomst och schemaläggning av ett jobb. I den första kan ett jobb schemaläggas när som helst efter sin ankomst; i den andra går ett jobb förlorat om det inte är planerat omedelbart vid ankomsten, vilket förhindrar ett jobb som för närvarande körs om det behövs. De två inställningarna motsvarar två naturliga modeller av hur länge en annonsör behåller intresset för en relevant användare. Vi visar att det faktiskt finns en skarp åtskillnad mellan vad en online schemaläggare kan uppnå i dessa två inställningar. I den första inställningen utan deadlines, ger vi en naturlig deterministisk algoritm med en konstant konkurrensförhållande mot offline schemaläggaren. Däremot visar vi att i den skarpa deadlineinställningen kan ingen (deterministisk eller randomiserad) onlinealgoritm uppnå bättre än ett polylogaritmiskt förhållande.
Dasgupta m.fl. Ref övervägde ett problem med jobbplanering som motiveras av webbannonsering.
Online story scheduling in web advertising
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}