A note on scheduling alternative operations in two-machine flowshops

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

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 languageEnglish
Pages (from-to)670-673
Number of pages4
JournalJournal of the Operational Research Society
Volume49
Issue number6
DOIs
Publication statusPublished - 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

Cite this