网络并行环境下多处理机任务的调度

Multiprocessor-job Scheduling on Network Parallel System

随着网络技术的不断发展 ,网络上可供共享的资源越来越丰富 ,集群技术的兴起更是扩展了并行计算的环境 .这种环境下系统中很多任务依赖于多种资源 (或多个处理机 ) ,称这样的任务为多处理机任务 .本文研究基于多处理机任务的调度模型 Pm|fix|Cmax.当 m≥ 3时 ,这类调度问题是强 NP-难的 ,所以只能寻求有好的逼近性能的多项式时间近似算法 .文中给出了当 m =4或 5时线性时间的近似调度算法 ,优于目前已有的最好结果 ,最后我们还讨论了当 k≥

Many jobs in parallel systems usually depend on more than one resource or more than one processor. This kind of jobs is called multiprocessor job. In this paper, we study the scheduling model P m|fix|C max based on multiprocessor jobs. When m≥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 3/2 for m=4 and 2 for m=5 of the P m|fix|C max problem, which improves the best previous results (2 and 2.5 respectively) for practical algorithms for the problem. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than five processors. We will also introduce a generalized and more practical scheduling algorithm.