A Polynomial Algorithm for Computing Elementary Siphons in a Class of Petri Nets

A set of elementary siphons plays a key role in the development of deadlock prevention policies for automated manufacturing systems. This paper addresses the computation problem for elementary siphons in a subclass of Petri nets which are basic systems of simple sequential processes with resources (BS³PR) and can model many automated manufacturing systems. An algorithm for enumerating elementary siphons is established by the one‐to‐one relationship between maximal perfect resource‐transition circuits (MPCs) and strict minimal siphons. A set of MPCs is first computed, followed by a set of elementary siphons in a BS³PR. The presented algorithm is proved to have polynomial‐time complexity. An example is used to illustrate the algorithm.