Abstract: This paper studies the problem of scheduling model P_m|fix，p_j=1|C_max，that schedules a set of n independent multiprocessor jobs with unit process time and prespecifies processor allocation on a set of identical processors in order to minimize the makespan.The general problem P_m|fix|C_max，that has widely applied in various fields such as the network parallel computing，the multi-casting system and the project plan，is proved to be NP-hard and cannot be approximated within a constant factor unless P=NP.Recently，E.Bampis et al.gave a 2m-approximation algorithm for this problem by using the split-round technique.This paper proposes a 2m+1-approximation algorithm for this problem based on the Largest Wide First（LWF）and partial schedule algorithm.

Key words: multiprocessor job, scheduling, approximation algorithm, NP-hard problem

摘要： 研究多处理机任务调度模型P_m|fix，p_j=1|C_max，即在m个处理机系统中调度n个时间长度都为1的多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是P_m|fix|C_max，在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题，而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法，并从理论上证明了该算法在最坏情况下的近似比为2m+1，优于已有文献中2m的目前最好结果。

关键词: 多处理机任务, 调度, 近似算法, NP难问题