A CLASS OF GENERALIZED MULTIPROCESSOR SCHEDULING PROBLEMS

作     者：YANG Xiaoguang (Laboratory of Management, Decision and Information System, Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China) 

作者机构：中科院系统科学所 管理、决策与信息系统开放实验室 北京 100080 

出 版 物：《Systems Science and Mathematical Sciences》 (SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES)

年 卷 期：2000年第13卷第4期

页      面：385-390页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：the National Natural Science Foundation of China (No. 79791030) andNational 863 Hi-Tech Project (No. 863-306-ZT04-04-1) 

主　　题：Unit execution time polynomial algorithm bound. 

摘      要：The paper discusses a class of generalized multiprocessor scheduling problems which is to arrange some independent jobs on almost identical processors. Different from the classical multiprocessor scheduling, each job may only be processed by some processors, not all. In this paper, we first prove that the problems of minimization makespan and minimization total weighted completion time can be solved by the polynomial algorithms if all processing time are unit time. Then for arbitrary processing time, we try to analyze the worst performance of list schedule (LS) method and longest processing time(LPT) method when there are only two machines involved. We show that the bounds for LS and LPT are exactly two.