An improved LS algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed
Keywords:
Heuristic algorithm, LS algorithm, LPT algorithm, general-purpose processors, special-purpose processors, tight bound.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.Downloads
Published
2010-04-14
How to Cite
Ding, W., & Zhao, Y. (2010). An improved LS algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed. Algorithmic Operations Research, 5(1), Pages 34 –38. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12573
Issue
Section
Articles