关键词: 多处理机任务, 调度, 近似算法, 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 prespecified 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 been used 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.This paper proposes an approximation algorithm for this problem based on the approximation clique partition method.By the analysis from test data，this algorithm presents more optional ratio preference.

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