Efter tidigare arbete tar vi hänsyn till den hierarkiska lastbalanseringsmodellen på två maskiner med möjligtvis olika hastigheter. Vi fokuserar först på att maximera den minsta maskinbelastningen och visa att ingen konkurrerande algoritm finns för detta problem. Vi övervinner denna barriär på två sätt, båda relaterade till tidigare kända modeller. Den första är en deluppgift, där varje jobb godtyckligt kan delas mellan maskinerna. Den andra modellen är en semi-online-modell där summan av jobben är känd i förväg. Vi utformar algoritmer för bästa möjliga konkurrensförhållanden för båda dessa fall. Dessutom visar vi att kombinationen av de två modellerna leder till att det finns en optimal algoritm (dvs. en algoritm med konkurrensförhållande 1). Denna algoritm är helt klart optimal för makespan minimization problem också. För det senare problemet anser vi att modellen för deltilldelning och design är en algoritm med bästa möjliga konkurrensförhållande för den.
För detta problem, Chassid och Epstein REF anses fraktionerad modell där varje jobb kan godtyckligt delas mellan maskiner och delar av samma jobb kan köras på olika maskiner parallellt, och en semi-online modell med känd total jobbstorlek i förväg.
The hierarchical model for load balancing on two machines
{'venue': None, 'journal': 'Journal of Combinatorial Optimization', 'mag_field_of_study': ['Mathematics', 'Computer Science']}