Advances in Operations Research
Volume 2012 (2012), Article ID 748597, 9 pages
http://dx.doi.org/10.1155/2012/748597
Research Article

The 𝐶 m a x Problem of Scheduling Multiple Groups of Jobs on Multiple Processors at Different Speeds

Wei Ding

Department of Mathematics, Sun Yat-Sen University, Guangzhou 510275, China

Received 1 April 2012; Revised 4 July 2012; Accepted 19 July 2012

Academic Editor: Ching-Jong Liao

Copyright © 2012 Wei Ding. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We mainly study the 𝐶 m a x problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at different speeds provided that the setup time of each job is less than 𝛼 times of its processing time. We first propose an improved LS algorithm. Then, by applying this new algorithm, we obtain two bounds for the ratio of the approximate solution 𝑇 L S to the optimal solution T* under two different conditions.