MINIMIZING THE MAKESPAN IN THE 3-MACHINE ASSEMBLY-TYPE FLOWSHOP SCHEDULING PROBLEM

• 成果类型: Article
• 署名作者: LEE, CY; CHENG, TCE; LIN, BMT
• 署名单位: Hong Kong Polytechnic University; National Yang Ming Chiao Tung University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.39.5.616
• 发表日期: 1993
• 页码: 616-625
• 关键词: FLOWSHOP; Scheduling; ASSEMBLY-TYPE PRODUCTION

摘要

This paper considers minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. After problem formulation, we present a proof to show that the general version of this problem is strongly NP-complete. We 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.