A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines
研究了一个两阶段混合流水车间调度问题，其中第二阶段有两台专用机器，目标是最小化最大完工时间。论文先介绍问题并给出初步结果，然后举反例反驳了Riane等人的复杂度证明，最后重新确立了该问题的计算复杂性。
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.