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

作者：Yang Jaehwan^*

来源：International Journal of Production Research, 2010, 48(5): 1531-1538.

DOI：10.1080/00207540802691374

• 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.

• 出版日期2010