中文摘要：

研究独立多处理机任务静态调度问题Pm｜fix｜Cmax,即在m个处理机系统中调度n个多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行．该问题应用广泛但早已证明为NP难问题，而且也不存在常数近似算法．分析了问题Pm｜fix｜Cmax和其中所有任务都是单位处理机时间的特殊情形Pm｜fix,p=1｜Cmax的调度，并利用实例划分（split scheduling，简称SS）、首次满足优先（first fit，简称FF）和最大宽度优先（large wide first，简称LWF）等方法，构造了问题Pm｜fix,p=1｜Cmax的√2m＋1近似算法和问题Pm｜fix｜Cmax的2√m近似算法，优于目前已有文献的最好结果．

英文摘要：

This paper studies the multiprocessor job scheduling problem, and describes the m processors system, and analyze the algorithm for the problem of the offiine version, both Pm｜fix｜Cmax of the scheduling problem with arbitrary process time jobs, and Pm｜fix｜, p=1｜Cmax of the scheduling problem with unit processing time jobs. Severalvery simple and practical polynomial time approximation algorithm are constructed, a （√2m ＋1）-approximation algorithm for the problem Pm｜fix, p=1｜Cmax and a 2√m-approximation algorithm for the problem Pm｜fix｜Cmax, by usingthe Split Scheduling （SS）, the First Fit （FF） and the Large Wide First （LWF） technique The results are better than any seen in the literature at present.