Vi undersöker problemet med online schemaläggning av jobb för att minimera flödestid och sträcka på m identiska maskiner. Vi anser att fallet där algoritmen ges antingen (1 + )m maskiner eller m maskiner av hastighet (1 + ), för godtyckligt liten > 0. Vi visar att enkla randomiserade och deterministiska lastbalanseringsalgoritmer, tillsammans med enkla schemaläggningsstrategier för en maskin såsom SRPT (kortaste återstående processtid) och SJF (kortaste jobbet först), är O(poly(1/ )-konkurrenskraft för både flödestid och sträcka. Dessa är de första resultaten som visar konstant faktor konkurrensförhållanden för flödestid eller sträcka med godtyckligt liten resursökning. Både de randomiserade och deterministiska lastbalanseringsalgoritmerna är icke-migratoriska och skickar omedelbart jobb. Den randomiserade algoritmen allokerar bara varje inkommande jobb till en slumpmässig maskin. Därför denna algoritm är nonclairvoyant, och i kombination med SETF (kortaste förfluten tid först), ger den första icke-clairvoyant algoritm som är konstant konkurrenskraftig för att minimera flödestid med godtyckligt liten resursförstärkning. Den deterministiska algoritm som vi analyserar beror på Avrahami och Azar. För denna algoritm visar vi O(1/ )- *
Chekuri m.fl. visa sedan att enkla uniprocessor schemaläggning algoritmer som SRPT kombineras med enkla lastbalansering algoritmer är också (1 + )-hastighet O(1)-konkurrenskraftiga för att minimera p normer för flöde och stretch på m identiska maskiner REF.
Multi-processor scheduling to minimize flow time with ε resource augmentation
{'venue': "STOC '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}