| Article ID: | iaor1994121 |
| Country: | United States |
| Volume: | 39 |
| Issue: | 5 |
| Start Page Number: | 616 |
| End Page Number: | 625 |
| Publication Date: | May 1993 |
| Journal: | Management Science |
| Authors: | Cheng T.C.E., Lee Chung-Yee, Lin B.M.T. |
| Keywords: | programming: branch and bound |
This paper considers minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. After problem formulation, the authors present a proof to show that the general version of this problem is strongly NP-complete. They then discuss a few polynomially solvable cases of the problem and present the solution algorithms. Next, a branch and bound solution scheme is suggested. Finally, three heuristics to find approximate solutions to the general problem are proposed and their error bounds are analyzed.