Approximation algorithm for multiprocessor parallel job scheduling
来源期刊：中南大学学报(英文版)2002年第4期
论文作者：陈松乔 黄金贵 陈建二
文章页码：267 - 272
Key words：multiprocessor parallel job; scheduling; approximation algorithm; NP-hard problem
Abstract: Pk|fix|Cmaxproblem is a newscheduling problembased on the multiprocessor parallel job, and it is proved to be NP-hard problemwhenk≥3. This paper focuses on the case of k=3. Some new observations and new techniques for P3|fix|Cmax problem are offered. The concept of semi-normal schedulings is introduced, and a very simple lineartime 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 P3|fix|Cmaxproblem, and improves the previous best ratio of 7/6 by M.X.Go- emans.
