On the worst-case ratio of a compound multiprocessor scheduling algorithm (Q1097028)

Approximation algorithms for nonpreemptive scheduling of independent tasks on m identical processors are studied. For a heuristic MIX which chooses the best solution of the two well-known heuristics LPT and MULTIFIT the following results are derived: \[ (i)\quad 10/9\leq R_ 2(MIX)\leq 10/9 +2^{-k},\quad (ii)\quad 8/7\leq R_ 3(MIX)\leq 8/7 +2^{-k}, \] \[ (iii)\quad 15/13\leq R_ m(MIX)\text{ for all } m\geq 5. \] Here \(R_ m(MIX)\) denotes the worst-case ratio and k is the number of iterations in which MULTIFIT calls the subroutine FIRST-FIT DECREASING.