I den klassiska minimum makespan schemaläggning problem, får vi en ingång sekvens av jobb med bearbetningstider. En schemaläggningsalgoritm måste tilldela jobben till m parallella maskiner. Målet är att minimera makespan, vilket är den tid det tar tills alla jobb bearbetas. I den här artikeln överväger vi online schemaläggning algoritmer utan preemption. Men vi kräver inte att varje anländande arbete omedelbart måste tilldelas en av maskinerna. En omordningsbuffert med begränsad lagringskapacitet kan användas för att omorganisera inmatningssekvensen på ett begränsat sätt för att schemalägga jobben med en mindre makepan. Detta är en naturlig förlängning av lookahead. Vi presenterar en omfattande studie av kraften och gränserna för online-omordning för minsta makespan schemaläggning. Som huvudresultat, ger vi, för m identiska maskiner, tight och, i jämförelse med problemet utan omordning, mycket förbättrade gränser på konkurrensförhållandet för minsta makespan schemaläggning med omordning buffertar. Beroende på m ligger det uppnådda konkurrensförhållandet mellan 4/3 och 1.4659. Detta optimala förhållande uppnås med en buffert av storlek -(m). Vi visar att större buffertstorlekar inte leder till någon ytterligare fördel och att en buffert av storlek är nödvändig för att uppnå detta konkurrensförhållande. Vidare presenterar vi flera algoritmer för olika buffertstorlekar. Bland annat introducerar vi en (2 − 1/(m − k + 1))-konkurrensalgoritm för varje buffertstorlek k.[1], (m + 1)/2], som fint generaliserar Grahams välkända resultat. För m jämnt relaterade maskiner ger vi en schemaläggningsalgoritm som uppnår ett konkurrenskraftigt förhållande på 2 med en omordningsbuffert av storlek m. Med tanke på att den mest kända * Stöds av DFG bidrag WE 2842/1. konkurrenskraftigt förhållande för enhetligt besläktade maskiner utan omordning är 5.828, detta resultat betonar kraften i online omordning ytterligare.
Englert m.fl. REF presenterade en algoritm som med hjälp av en buffert av storlek O(m) uppnår ett konkurrenskraftigt förhållande mellan W −1 (−1/e 2 )/(1 + W −1 (−1/e 2 )) och 1,46 där W −1 är Lambert W-funktionen.
The Power of Reordering for Online Minimum Makespan Scheduling
{'venue': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2008 49th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science']}