An improved LS (Link State) algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed

In the paper we mainly study the C max 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 a 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 TLS to the optimal solution T* is less than (1 + a)(2 - 1 / n + m ). Moreover, we give an example to illustrate that it is tight for any a = 0.