An improved LS algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed - Ding, Wei; Zhao, Yi (Algorithmic Operations Research, 2009)
In the paper we mainly study the Cmax problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at the same speed provided the ready time of each job is less than times of its processing time. We first propose an improved LS algorithm. We then show that the bound for the ratio of the approximate solution T LS to the optimal solution T is less than (1 + )(2 − 1 n+m ). Moreover, we give an example to illustrate that it is tight for any ≥ 0.