Approximation algorithm for multiprocessor parallel job scheduling

Abstract

P_k|fix|C_max 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 k=3. Some new observations and new techniques for P₃|fix|C_max problem are offered. The concept of semi-normal schedulings is introduced, and a very simple linear time algorithm Semi-normal Algorithm for constructing semi-normal schedulings 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 P₃|fix|C_max problem, and improves the previous best ratio of 7/6 by M.X. Goemans.

Keywords

multiprocessor parallel job / scheduling / approximation algorithm / NP-hard problem

References

[1] AmouraA K, BampisE, KenyonC, et al.BurkardR, WoegingerG J, et al.. Scheduling independent multiprocessor tasks[A]. Proc 5th Ann European Symposium on Algorithms. Lecture Notes in Computer Science[C], 1997, Berlin, Springer-Verlag Press: 1-12

[2] ChenJ, MirandaA. A polynomial time approximation scheme for general multiprocessor job scheduling[J]. SIAM (Society for Industrial and Applied Mathematics) J Computer, 2001, 31: 1-7

[3] JansenK, PorkolabLDehneF, GuptaA, SackJ. General multiprocessor task scheduling: Approximate solutions in linear time[A]. 1999 Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science[C], 1999, Berlin, Springer-Verlag Press: 110-121

[4] HoogeveenJ A, Van de VeldeS L, VeltmanB. Complexity of scheduling multiprocessor tasks with prespecified processor allocations[J]. Discrete Applied Mathematics, 1994, 55: 259-272

[5] BlazewiczJ, Dell’OlmoP, DrozdowskiM, et al.. Scheduling multiprocessor tasks on the three dedicated processors[J]. Information Processing Letters, 1992, 41: 275-280

[6] BlazewiczJ, DrozdowskiM, WeglarzJ. Scheduling multiprocessor tasks to minimize scheduling length[J]. IEEE Transaction on Computers, 1986, 35: 389-393

[7] GareyM R, JohnsonD SComputers and intractability: A guide to the theory of NP-completeness[M], 1979, San Francisco, Freeman Press

[8] Dell’OlmoP, SperanzaM G, TuzaZ S. Efficiency and effectiveness of normal schedules on three dedicated processors[J]. Discrete Mathematics, 1997, 164: 67-79

[9] HuangJ, ChenJ, ChenSHsuTsan Sheng. A simple linear time approximation algorithm for multi-processor job scheduling on four processors[A]. 12th Annual International Symposium on Algorithms and Computation. Lecture Notes in Computer Science [C], 2000, Berlin, Springer-Verlag Press: 60-71

[10] GoemansM X. An approximation algorithm for scheduling on three dedicated machines[J]. Discrete Applied Mathematics, 1995, 61: 49-59

[11] GrahamR L. Bounds for certain multiprocessing anomalies[J]. Bell System Technical Journal, 1966, 45: 1563-1581