Vi anser att en allmän online schemaläggning problem på en enda maskin med målet att minimera j w j g(F j ), där w j är vikten / betydelsen av jobbet J j, F j är flödestiden för jobbet i schemat, och g är en godtycklig icke-decreasing kostnadsfunktion. Många naturliga tidtabellsmål är speciella fall av detta allmänna mål. Vi visar att schemaläggningsalgoritmen Högsta densitet först (HDF) är (2+ )-hastighet O(1)-konkurrenskraftig för alla kostnadsfunktioner g samtidigt. Vi ger lägre gränser som visar HDF-algoritmen och denna analys är i huvudsak optimal. Slutligen visar vi skalbara algoritmer är möjliga att uppnå i vissa speciella fall.
Det generaliserade flödesproblemet på en enda maskin med speciella kostnadsfunktioner g j (t) = g(t − r j ) har studerats i REF.
Online Scheduling with General Cost Functions
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science']}