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

Wei Ding, Yi Zhao

Abstract


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 α 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.

Keywords


Heuristic algorithm; LS algorithm; LPT algorithm; general-purpose processors; special-purpose processors; tight bound.

Full Text:

PDF


Algorithmic Operations Research. ISSN: 1718-3235