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

Volume

30

Issue

2

fYear

2000

fDate

3/1/2000 12:00:00 AM

Firstpage

222

Lastpage

229

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;

fLanguage

English

Journal_Title

Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on

Publisher

ieee

ISSN

1083-4427

Type

jour

DOI

10.1109/3468.833105

Filename

833105