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

Authors

  • Wei Ding Sun Yat-sen University
  • Yi Zhao Sun Yat-sen University

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