A NEW HEURISTIC FOR 3-MACHINE FLOW-SHOP SCHEDULING

Authors
CHEN B GLASS CA POTTS CN STRUSEVICH VA
Citation
B. Chen et al., A NEW HEURISTIC FOR 3-MACHINE FLOW-SHOP SCHEDULING, Operations research, 44(6), 1996, pp. 891-898
Citations number
16
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
44
Issue
6
Year of publication
1996
Pages
891 - 898
Database
ISI
SICI code
0030-364X(1996)44:6<891:ANHF3F>2.0.ZU;2-X
Abstract
This paper considers the problem of sequencing n jobs in a three-machi ne flow shop with the objective of minimizing the makespan, which is t he 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 ra tio of 2. An application to the general flow shop is also discussed.