机器不同时开工平行机排序问题的原始阈值算法-重庆师范大学学报（自然科学版）

文章信息/Info

Title:: Primal Threshold Algorithms of Non-Simultaneous Machine Available Times

作者:: 李蒙¹; 唐万梅¹; 唐国春²; 1.重庆师范大学数学与计算机科学学院，重庆 400047； 2.上海第二工业大学管理工程研究所，上海 200041

Author(s):: ^{LI Meng¹}; TANG Wan-mei¹; TANG Guo-chun²; 1. College of Mathematics and Computer Science Chongqing Normal University Chongqing 400047; 2. Institute of Management Engineering Shanghai Second Polytechnic University Shanghai 200041，China )

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

Abstract:: 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.