A stack-based algorithm for deadlock avoidance in flexible manufacturing systems

Author

Lipset, Robert ; Deering, Paul E. ; Judd, Robert P.

Author_Institution

Dept. of Ind. & Manuf. Syst. Eng., Ohio Univ., Athens, OH, USA

Volume

2

fYear

1998

fDate

21-26 Jun 1998

Firstpage

1252

Abstract

A method to detect deadlock in manufacturing systems that contain single capacity resources is presented. The proposed stack-based algorithm is polynomial in complexity, and is very simple to implement for any flexible manufacturing system in this class. This algorithm determines whether a system is in deadlock by trying to calculate a sequence of safe part movements that empties the manufacturing system of parts. If such a sequence exists, then the system is not in deadlock. Some examples showing the application of the algorithm are provided

Keywords

computational complexity; directed graphs; flexible manufacturing systems; resource allocation; deadlock avoidance; flexible manufacturing systems; polynomial complexity; safe part movements; single capacity resources; stack-based algorithm; Circuits; Computer aided manufacturing; Computer industry; Flexible manufacturing systems; Manufacturing industries; Manufacturing systems; Polynomials; Sufficient conditions; System recovery; Systems engineering and theory;

fLanguage

English

Publisher

ieee

Conference_Titel

American Control Conference, 1998. Proceedings of the 1998

Conference_Location

Philadelphia, PA

ISSN

0743-1619

Print_ISBN

0-7803-4530-4

Type

conf

DOI

10.1109/ACC.1998.703615

Filename

703615