A note on scheduling alternative operations in two-machine flowshops

作者：Cheng TCE^*; Wang G

来源：Journal of the Operational Research Society, 1998, 49(6): 670-673.

DOI：10.1038/sj.jors.2600575

• alternative operations
• dynamic programming algorithm
• flowshop scheduling

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.

• 出版日期1998-6
• 单位香港理工大学