Approximation algorithm for multiprocessor parallel job scheduling  

作　　者：陈松乔 黄金贵 陈建二 

机构地区：[1]College of Information Engineering, Central South University

出　　处：《Journal of Central South University of Technology》2002年第4期267-272,共6页中南工业大学学报（英文版）

基　　金：TheNationalNaturalScienceFoundationofChina(No.6 992 82 0 1) ;TheChangjiangScholarRewardProject.

摘　　要：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 3 |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 3|fix| C max problem, and improves the previous best ratio of 7/6 by M.X.Goemans.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 3 |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 3|fix| C max problem, and improves the previous best ratio of 7/6 by M.X.Goemans.

关 键 词：MULTIPROCESSOR PARALLEL JOB SCHEDULING APPROXIMATION algorithm NP-HARD problem 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]