A note on scheduling the two-machine flexible flowshop
Authors:
- T.C.E. ChengTCT.C.E. Cheng
- Guoqing WangGWGuoqing Wang
- 1 January 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics and Automation
- Vol. 15 (1) , 187-190
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.Department of Logistics and Maritime StudieKeywords
This publication has 7 references indexed in Scilit:
- Scheduling a two-stage hybrid flow shop with parallel machines at the first stageAnnals of Operations Research, 1997
- Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hardEuropean Journal of Operational Research, 1996
- Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One StageJournal of the Operational Research Society, 1995
- Minimizing makespan in hybrid flowshopsOperations Research Letters, 1994
- Concurrent routing, sequencing, and setups for a two-machine flexible manufacturing cellIEEE Journal on Robotics and Automation, 1988
- Scheduling Independent Tasks on Parallel ProcessorsManagement Science, 1966
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954