Computational complexity of determining resource loops in reentrant plow lines

This paper presents a comparison study of the computational complexity of t he general job shop protocol and the more structured flow line protocol in a flexible manufacturing system. Tt is shown that the representative proble m 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 importa nce of correctly selecting part flow and job routing protocols in flexible! manufacturing systems to reduce complexity is thereby conclusively demonst rated.