A Heuristic for Two-Stage No-Wait Hybrid Flowshop Scheduling with a Single Machine in Either Stage  

作　　者：刘志新 谢金星 李建国 董杰方 

机构地区：[1]DONG Jiefang Department of Mathematical Sciences Tsinghua University [2]Wuhan Iron and Steel Group Company

出　　处：《Tsinghua Science and Technology》2003年第1期43-48,共6页清华大学学报（自然科学版（英文版）

基　　金：Supported by the National Natural Science Foundationof China( No. 6 990 40 0 7)

摘　　要：This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine centers, one has a single machine and the other has more than one parallel machine. A greedy heuristic named least deviation algorithm is designed and its worst case performance is analyzed. Computational results are also given to show the algorithm's average performance compared with some other algorithms. The least deviation algorithm outperforms the others in most cases tested here, and it is of low computational complexity and is easy to carry out,thus it is of favorable application value.This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine centers, one has a single machine and the other has more than one parallel machine. A greedy heuristic named least deviation algorithm is designed and its worst case performance is analyzed. Computational results are also given to show the algorithm's average performance compared with some other algorithms. The least deviation algorithm outperforms the others in most cases tested here, and it is of low computational complexity and is easy to carry out,thus it is of favorable application value.

关 键 词：hybrid flowshop scheduling no wait HEURISTIC worst case analysis 

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