Title :
A note on scheduling the two-machine flexible flowshop
Author :
Cheng, T. C Edwin ; Wang, Guoqing
Author_Institution :
Dept. of Res. & Postgraduate Studies, Hong Kong Polytech. Univ., Kowloon, Hong Kong
fDate :
2/1/1999 12:00:00 AM
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 (1988). 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
Keywords :
computational complexity; dynamic programming; flexible manufacturing systems; heuristic programming; production control; FMS; NP-complete one-setup version; heuristic; pseudopolynomial dynamic programming algorithm; two-machine flexible flowshop; two-machine flexible manufacturing cell scheduling; worst-case error bound; Dynamic programming; Flexible manufacturing systems; Heuristic algorithms; Job shop scheduling; Milling machines; Production systems;
Journal_Title :
Robotics and Automation, IEEE Transactions on
