Improved worst-case ratio of the Knuth–Kleitman algorithm for minimising makespan

The parallel machine scheduling problem (minimise makespan) is considered here. Knuth and Kleitman provided an approximation algorithm for this problem. Graham has proved that the worst-case ratio of algorithm AKK is 1+1−1/m/1+[k/m] and the bound on AKK is the best possible for k ≡ (B(0)mod m). In this paper, we give an improved worst-case ratio 1+max {1−1/m/1+k1+1/m, 1−1/m−k2/1+k1} for algorithm AKK, in which k/m + k2 = k and k1,k2 are nonnegative integers. And we prove that it is better the result of Graham when k2 ≠ (B0), and we give two instances to show it is tight.