流水作业两台机器的成组排序的一个新问题  

A new two machine flowshop scheduling problem with setup time and group technology.

作　　者：谷会昆[1] 

机构地区：[1]浙江大学数学系,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2005年第3期264-267,272,共5页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目 (10 2 71110 )

摘　　要：研究了两台流水作业机器有调整时间的成组排序问题.首先对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.

关 键 词：流水作业 成组技术 加权总完工时间 

分 类 号：O223[理学—运筹学与控制论]