A note on scheduling alternative operations in two-machine flowshops

Abstract

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.

Keywords:

• alternative operations
• dynamic programming algorithm
• flowshop scheduling