摘要
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.
出处
《计算机科学》
CSCD
北大核心
2002年第4期1-3,共3页
Computer Science
基金
国家杰出青年学者自然科学基金
长江学者奖励基金
