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

Vol. 5 No. 1 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.