Vol 5 No 1 (2010)
Articles

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

Wei Ding
Sun Yat-sen University
Yi Zhao
Sun Yat-sen University
Published April 14, 2010
Keywords
  • Heuristic algorithm,
  • LS algorithm,
  • LPT algorithm,
  • general-purpose processors,
  • special-purpose processors,
  • tight bound.
  • ...More
    Less
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

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.