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

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