The makespan problem of scheduling multi groups of jobs on multi processors at different speeds

Authors

  • Wei Ding Sun Yat-sen University

Keywords:

Heuristic algorithm, LPT algorithm, approximate solutions, optimal solutions, upper bound

Abstract

In the paper we mainly study the makespan problem of scheduling <em>n</em> groups of jobs on <em>n</em> special-purpose processors and <em>m</em> general-purpose processors at different speeds. We first propose an improved <em>LPT</em> algorithm and investigate several properties of this algorithm. We then obtain an upper bound for the ratio of the approximate solution <em>T</em> to the optimal solution <em>T</em><sup>*</sup> under the improved <em>LPT</em> algorithm.

Downloads

Published

2012-07-26

How to Cite

Ding, W. (2012). The makespan problem of scheduling multi groups of jobs on multi processors at different speeds. Algorithmic Operations Research, 7(1), Pages 41 – 50. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18367

Issue

Section

Articles