Approximation algorithm for multiprocessor parallel job scheduling Academic Article

abstract

• Pk |fix| Cmax problem is a new scheduling problem based on the multiprocessor parallel job, and it is proved to be NP-hard problem when k=3. This paper focuses on the case of k3. Some new observations and new techniques for P3|fix| Cmax problem are offered. The concept of semi-normal scheduling is introduced, and a very simple linear time algorithm Semi-normal Algorithm for constructing semi-normal scheduling is developed. With the method of the classical Graham List Scheduling, a thorough analysis of the optimal scheduling on a special instance is provided, which shows that the algorithm is an approximation algorithm of ratio of 9/8 for any instance of P3 |fix| Cmaxproblem, and improves the previous best ratio of 7/6 by M.X. Goemans.

authors

• Chen, Jianer

published proceedings

• Journal of Central South University

author list (cited authors)

• Chen, S., Huang, J., & Chen, J.

citation count

• 2

complete list of authors

• Chen, Song-qiao||Huang, Jin-gui||Chen, Jian-er

publication date

• December 2002

publisher

• Springer Nature  Publisher

published in

• Journal- Central South University  Journal

Digital Object Identifier (DOI)

• 10.1007/s11771-002-0040-0

start page

• 267

end page

• 272

volume

• 9

issue

• 4

URL

• http://dx.doi.org/10.1007/s11771-002-0040-0