Title :
Computational complexity of determining resource loops in re-entrant flow lines
Author :
Lewis, F.L. ; Horne, B.G. ; Abdallah, C.T.
Author_Institution :
Inst. of Autom. & Robotics Res., Texas Univ., Arlington, TX, USA
fDate :
3/1/2000 12:00:00 AM
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
Keywords :
Petri nets; computational complexity; flexible manufacturing systems; production control; protocols; resource allocation; FMS; NP-complete problem; Petri net; computational complexity; flexible manufacturing system; flow line protocol; job routing; job shop protocol; production control; reentrant flow lines; resource allocation; Assembly; Computational complexity; Control systems; Dispatching; Flexible manufacturing systems; Job shop scheduling; Processor scheduling; Protocols; Robotics and automation; Routing;
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
DOI :
10.1109/3468.833105
