A note on scheduling the two-machine flexible flowshop

Edwin Tai Chiu Cheng, Guoqing Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


In this note we consider the NP-complete one-setup version of the two-machine flexible manufacturing cell scheduling problem studied by Lee and Mirchandani [5]. We provide a pseudopolynomial dynamic programming algorithm to solve the problem, thus establishing that the problem is NP-complete in the ordinary sense. We derive a tight worst-case error bound for the heuristic presented by Lee and Mirchandani, and propose another heuristic with a tight worst-case error bound of 3/2.
Original languageEnglish
Pages (from-to)187-190
Number of pages4
JournalIEEE Transactions on Robotics and Automation
Issue number1
Publication statusPublished - 1 Dec 1999


  • Flexible manufacturing cell
  • Flowshop scheduling
  • Make-span minimization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'A note on scheduling the two-machine flexible flowshop'. Together they form a unique fingerprint.

Cite this