A new heuristic for three-machine flow shop scheduling
成果类型：
Article
署名作者：
Chen, B; Glass, CA; Potts, CN; Strusevich, VA
署名单位：
University of Southampton; University of Greenwich
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.44.6.891
发表日期：
1996
页码：
891-898
关键词：
摘要：
This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.