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 A1gorithm will be controlled by abnormal stopping rule. We can also get the same result. Moreover, it is proved that ifε equal to (m-1)/m, the performance ratio of Primal-Threshold Algorithm PTm((m-1)/m) is 1+(m-1)/m, which is tight. It extends the case of two machines on Primal-Threshold Algorithms.