Abstrakt. Online makespan minimization är ett klassiskt problem där en sekvens av jobb σ = J1,. .., Jn måste schemaläggas på m identiska parallella maskiner för att minimera den maximala slutförandetiden för alla jobb. I detta dokument undersöker vi problemet med en i grunden ny modell för resursförstärkning. Mer specifikt är en online-algoritm tillåtet att bygga flera scheman parallellt under bearbetningen σ. I slutet av schemaläggningsprocessen väljs det bästa schemat. Denna modell kan ses som att ge en online-algoritm med extra utrymme, som investeras för att upprätthålla flera lösningar. Inställningen är av särskilt intresse för parallella bearbetningsmiljöer där varje processor kan underhålla en enda eller en liten uppsättning lösningar. Som ett huvudresultat utvecklar vi en (4 3 + ε)-kompetitiv algoritm, för alla 0 < ε ≤ 1, som använder ett konstant antal scheman. Konstanten är 1 ε O(log( 1 ε)). Vi ger också en (1 + ε)-kompetitiv algoritm, för alla 0 < ε ≤ 1, som bygger ett polynomtal av (m ε) O(log( 1 ε) ε) scheman. Detta värde beror på m men är oberoende av indatan σ. Prestandagarantierna är nästan bästa möjliga. Vi visar att alla algoritmer som uppnår en konkurrenskraft som är mindre än 4 3 måste konstruera scheman. Våra algoritmer använder sig av nya gissningssystem som (1) förutsäger den optimala makepan av en jobbsekvens σ till inom en faktor på 1+ε och (2) gissa jobbbearbetningstiderna och deras frekvenser i σ. I (2) vi måste sparifiera universum av alla gissningar för att minska antalet scheman till en konstant. De konkurrensförhållanden som uppnås med hjälp av parallella scheman är betydligt mindre än de i standardproblemet utan resursförstärkning. Dessutom är de minst lika bra och i de flesta fall bättre än de kvoter som erhålls med andra medel för resursförstärkning för makespan minimization.
Dessutom, en algoritm för schemaläggning problem på m identiska maskiner med målet att minimera makespan presenteras av Albers och Hellwig REF.
Online Makespan Minimization with Parallel Schedules
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}