Exact, Approximate, and Guaranteed Accuracy Algorithms for the Flow-Shop Problem n / 2 / F / F¯
Walter H. Kohler, Kenneth Steiglitz · Journal of the ACM · 1975
Improved exact and approximate algorithms for the n-job two-machine mean finishing time flow-shop problem, n/2JF/P, are presented While other researchers have used a variety of approximate methods to generate suboptimal solutions and branch-and-bound algorithms to generate exact solutmns to sequencing problems, thin work demonstrates the computatmnal effectiveness of couphng the two methods to generate solutmns with a guaranteed accuracy.The computational reqmrements of exact, approximate, and guaranteed accuracy algorithms are compared expemmentally on a set of test problems ranging in size from 10 to 50 jobs The approach is readily apphcable to other sequencing problems