Electrical & Computer Engineering Faculty Publications
Document Type
Article
Publication Date
3-1-2000
Abstract
This paper presents a comparison study of the computational complexity of the general job shop protocol and the more structured flow line protocol in a flexible manufacturing system. It is shown that the representative problem of finding resource invariants is NP-complete in the case of the job shop, while in the flow line case it admits a closed form solution. The importance of correctly selecting part flow and job routing protocols in flexible manufacturing systems to reduce complexity is thereby conclusively demonstrated.
Publisher
IEEE
Publication Title
IEEE Transactions on Systems
ISSN
1083-4427
First Page
222
Last Page
229
DOI
10.1109/3468.833105
Language (ISO)
English
Sponsorship
IEEE
Keywords
Computational complexity, Control systems, Flexible manufacturing systems
Recommended Citation
Abdallah, Chaouki T.; F. L. Lewis; and B. G. Horne. "Computational complexity of determining resource loops in re-entrant flow lines." IEEE Transactions on Systems (2000): 222-229. doi:10.1109/3468.833105.
