Abstract
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 language | English |
---|---|
Pages (from-to) | 187-190 |
Number of pages | 4 |
Journal | IEEE Transactions on Robotics and Automation |
Volume | 15 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Dec 1999 |
Keywords
- Flexible manufacturing cell
- Flowshop scheduling
- Make-span minimization
ASJC Scopus subject areas
- Control and Systems Engineering
- Electrical and Electronic Engineering