并行环境下基于多处理机任务的调度模型与调度算法  

Multiprocessor-job Scheduling: Models and Algorithms

作　　者：黄金贵[1] 陈建二[2] 陈松乔[2] 

机构地区：[1]湖南师范大学图像识别与计算机视觉研究所,长沙410081 [2]中南大学信息工程学院计算机理论与软件研究所,长沙410083

出　　处：《计算机科学》2002年第4期1-3,共3页Computer Science

基　　金：国家杰出青年学者自然科学基金;长江学者奖励基金

摘　　要：1引言目前所研究的并行系统中的任务调度问题，大都针对于单处理机任务进行。Many jobs in parallel systems usually depend on more than one resource or more than one processor. This kind of jobs are called multiprocessor jobs. In this paper, we study the scheduling model Pk |fix |Cmax based on multiprocessor jobs. When k≥3,the problem is NP-hard in the strong sense thus it does not have a fully polynomial time approximation scheme unless P = NP. We develop a linear time approximation algorithm of ratio 5/3 for the P4|fix| Cmax problem, which improves the best previous ratio 2 for practical algorithms for the problem. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors. We will also introduce a generalized and more practical scheduling model.

关 键 词：多处理机 任务调度模型 任务调度算法 并行环境 计算机 

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