A note on scheduling alternative operations in two-machine flowshops
研究了两机流水车间中每项作业包含两个连续操作且机器可替代执行操作的调度问题，目标是极小化最大完工时间，并提出了一个伪多项式动态规划方案，证明该问题仅为普通NP完全问题。
In this note, we consider a class of problems for scheduling a set of jobs each of which consists of two consecutive operations. The jobs are to be processed in a two-machine flowshop in which either or both machines are versatile. A versatile machine can perform both operations of a job. The objective is to minimise the makespan. While the whole class of problems has been shown to be NP-complete, we provide a general pseudopolynomial dynamic programming scheme which solves the problems analytically. This also establishes that the problems are only NP-complete in the ordinary sense. The solution scheme can be modified to solve another class of similar two-machine flowshop scheduling problems.