摘要
研究了两台流水作业机器有调整时间的成组排序问题.首先对NP-难的F2 |S,GT ∑i,jWij Cij,给出了一个近似算法,证明了它的最坏情况界为2 .然后讨论了F2 |S,GT|Cmax在线排序,并给出了一个最坏情况界为2的近似算法,并证明不可能存在最坏情况界小于2的在线近似算法.
Two machine flowshop scheduling problems with setup time and group technology were considered. For the problem F-2|S,GT∑ i,j W_ ij C_ ij , an approximate algorithm with worst-case bound 2 is proposed. For the on-line problem F-2|S,GT|C_ max , an approximate algorithm with worst-case bound 2 is also proposed while it can be proved that there is not online approximation algorithm with worst-case bound less than 2.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2005年第3期264-267,272,共5页
Journal of Zhejiang University（Science Edition）
基金
国家自然科学基金资助项目 (10 2 71110 )
