Vi anser att det klassiska problemet med att minimera den totala viktade flödestiden för icke-relaterade maskiner i online-non-clairvoyant inställning. I detta problem, en uppsättning jobb J anländer över tid för att schemaläggas på en uppsättning M maskiner. Varje jobb j har bearbetningslängd pj, vikt wj, och bearbetas med en hastighet av ij när schemalagd på maskin i. Online schemaläggaren vet värdet av wj och ij vid ankomsten av jobbet, men är inte medveten om mängden pj. Vi presenterar den första online-algoritmen som är skalbar (1 + )-hastighet O( 1 2 )-konkurrenskraftig för alla konstanter > 0) för det totala viktade flödestidsmålet. Inga icke-triviala resultat var kända för denna inställning, förutom för det mest grundläggande fallet av identiska maskiner. Vårt resultat löser ett stort öppet problem i online schemaläggning teori. Dessutom visar vi att inget arbete behöver mer än ett logaritmiskt antal flyttningar. Vi utökar ytterligare vårt resultat och ger en skalbar algoritm för målet att minimera total vägd flödestid plus energikostnad för icke-relaterade maskiner. I detta problem, varje maskin kan påskyndas av en faktor f −1 i (P ) när man konsumerar power P, där fi är en godtycklig strikt konvex effekt funktion. I synnerhet får vi en O (γ 2 )-konkurrenskraftig algoritm när alla effektfunktioner är av form s γ. Dessa är de första icke-triviala icke-klairvoyant resultat i någon miljö med heterogena maskiner. Den viktigaste algoritmiska idén är att låta jobb migrera själviskt tills de konvergerar till jämvikt. I detta syfte definierar vi ett spel där varje jobbs nytta som är nära knuten till den momentana ökningen av det mål som jobbet är ansvarigt för, och varje maskin förklarar en politik som ger prioritet åt jobb baserade på när de migrerar till det, och utförandet hastigheter. Detta har en anda som liknar samordningsmekanismer som försöker uppnå nära optimal välfärd i närvaro av själviska agenter (jobb). Så vitt vi vet är detta det första arbetet som visar nyttan av idéer från samordningsmekanismer och Nash equilibria för att designa och analysera online-algoritmer.
För den allmänna bedömningen av icke-klairvoyant vägd flödestid på icke-närstående maskiner, Im et al. REF visade att viktat round-robin med en lämplig migrationspolitik ger en (2 + ε) konkurrenskraftig algoritm med (1 + ε) hastighetsförstärkning.
SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}