DocumentCode
1472071
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
Volume
15
Issue
1
fYear
1999
fDate
2/1/1999 12:00:00 AM
Firstpage
187
Lastpage
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 (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;
fLanguage
English
Journal_Title
Robotics and Automation, IEEE Transactions on
Publisher
ieee
ISSN
1042-296X
Type
jour
DOI
10.1109/70.744613
Filename
744613
Link To Document