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