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

被引：246

作者：

LEE, CY

CHENG, TCE

LIN, BMT

机构：

[1] HONG KONG POLYTECH,DEPT MANAGEMENT,KOWLOON,HONG KONG

[2] NATL CHAIO TUNG UNIV,DEPT COMP & INFORMAT SCI,HSINCHU 30050,TAIWAN

来源：

MANAGEMENT SCIENCE | 1993年 / 39卷 / 05期

关键词：

FLOWSHOP; SCHEDULING; ASSEMBLY-TYPE PRODUCTION;

D O I：

10.1287/mnsc.39.5.616

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：616 / 625

页数：10

共 23 条

[1] NOTE ON A PAPER BY SZWARC,W [J].