Vi studerar online-mekanismer för förebyggande schemaläggning med deadlines, med målet att maximera det totala värdet av avslutade jobb. Detta problem är grundläggande för deadline-medveten moln schemaläggning, men det finns starka lägre gränser även för algoritmiska problem utan incitament begränsningar. Dessa lägre gränser kan dock kringgås under det naturliga antagandet om tidsbrist, dvs. att det finns en garanterad lägre gräns s > 1 på förhållandet mellan ett jobbs storlek och tidsfönstret där det kan utföras. I detta dokument konstruerar vi en sanningsenlig schemaläggningsmekanism med ett konstant konkurrensförhållande, med tanke på att s > 1. Dessutom visar vi att om det är tillräckligt stort kan vi bygga upp en mekanism som också uppfyller ett åtagande: det kan avgöras om ett arbete kommer att slutföras eller inte, och den nödvändiga betalningen om så är fallet, i god tid före varje jobbs sista dag. Detta är anmärkningsvärt eftersom användare med strikta tidsfrister i praktiken kan tycka att det är oacceptabelt att endast mycket nära sin tidsfrist upptäcka att deras arbete har avvisats.
REF tillhandahåller en mekanism för förebyggande schemaläggning med tidsfrister som maximerar det totala värdet av avslutade arbetstillfällen.
Truthful Online Scheduling with Commitments
{'venue': "EC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}