中文摘要：

对于机器不同时开工排序问题，研究m台机器的情况，给出原始阚值算法PTm（ε）（其中ε为可选参数），并证明当ε=m-1/m时原始阈值算法PTm（m-1/m）的近似比为1＋m-1/m，而且证明该界是紧的。由此推广原有文献中两台机器的原始阈值算法。

英文摘要：

In this paper the case of m machines with non-simultaneous machine available times is investigated. As a generalation of the classical parallel machine scheduling problem,each machine is available only at a machine dependent release time. For the problem of minimizing the makespan, the kind of algorthm which is called Primal-Threshold PTm（ ε）, where ε is an optional parameter, is proposed. Then we prove that if the Algorithm will be controlled by normal stopping rule, we can obtain that C^PTm（ε）/C^OPT〈1＋ε The Algorithm will be controlled by abnormal stopping rule. We can also get the same result. Moreover,it is proved that if ε equalso to m-1/mthe performance ratio of Prlmal-Threshold Algorithm PTm（m-1/m）is 1＋（m-1）/m,which is tight. It extends the case of two machines onPrimal-Threshold Algorithms.