【摘要】 对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数) ,并证明了当ε=15 时,对偶阈值算法DA315 的近似比为65 ,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.更多还原

【Abstract】 As to the scheduling problem of parallel machines with non-simultaneous machine available times, three machines are investigated. The linear time algorithm called Dual-Threshold Algorithm Class DA3(ε), where ε is an optional parameter, is proposed. Moreover, it is proved that if ε equals 15, the performance ratio of Dual-Threshold Algorithm DA315 is 65, which is the tight one. And up to now, this algorithm is the best algorithm with the least performance ratio and linear time.更多还原