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.
Original language | English |
---|---|
Pages (from-to) | 670-673 |
Number of pages | 4 |
Journal | Journal of the Operational Research Society |
Volume | 49 |
Issue number | 6 |
DOIs | |
Publication status | Published - 1 Jan 1998 |
Keywords
- Alternative operations
- Dynamic programming algorithm
- Flowshop scheduling
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research
- Marketing