摘要
对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数) ,并证明了当ε=15 时,对偶阈值算法DA315 的近似比为65 ,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.
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.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2005年第3期258-263,共6页
Journal of Zhejiang University（Science Edition）
基金
国家自然科学基金资助项目 (10 2 71110 )
关键词
排序
近似比
机器
住备时间
线性时间
scheduling
performance ratio
machine available time
linear time
