A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines

作     者：Yang, Jaehwan 

作者机构：Univ Seoul Sch Business Adm Seoul 130743 South Korea 

出 版 物：《INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH》 (国际生产研究杂志)

年 卷 期：2010年第48卷第5期

页      面：1531-1538页

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0802[工学-机械工程] 

主　　题：scheduling hybrid flow shop computational complexity 

摘      要：This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimise the makespan. There is one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and, depending upon the job type, the job is processed on either of the two machines at stage 2. We first introduce this special type of the two-stage hybrid flow shop scheduling problem and present some preliminary results. We then present a counter example to the known complexity proof of Riane et al. [Riane, F., Artiba, A. and Elmaghraby, S. E., 2002. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 40, 4353-4380.] Finally, we re-establish the complexity of the problem.