Johnson's Three-Machine Flow-Shop Conjecture

In an epoch-setting paper on scheduling theory, Johnson determined an efficient algorithm for solving the two-stage flow-shop problem and two special cases of the three-stage problem. In his concluding remarks he suggested another special condition in which one would obtain a three-stage solution. W...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1976-05, Vol.24 (3), p.578-580
Main Authors: Burns, Fennell, Rooker, John
Format: Article
Language:English
Subjects:
Technical Notes
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In an epoch-setting paper on scheduling theory, Johnson determined an efficient algorithm for solving the two-stage flow-shop problem and two special cases of the three-stage problem. In his concluding remarks he suggested another special condition in which one would obtain a three-stage solution. We give an example to show that this conjecture is not quite true. A true statement is obtained, however, by only a slight strengthening of the original. The primary issue concerns the impact of the two-stage no-preference precedent rules on the three-stage problem.
ISSN:0030-364X
1526-5463