Efficient computation of strict minimal siphons for a class of Petri nets models of automated manufacturing systems
Transactions of the Institute of Measurement and Control, 33 (1):
182--201 (Feb 1, 2011)DOI: 10.1177/0142331208095678
Abstract
As a structural object of Petri nets, siphons play a key role in the development of deadlock prevention policies for resource allocation systems. The siphon solution in Petri nets has been extensively investigated in the literature. Since the number of siphons in a net grows quickly and in the worst case grows exponentially with respect to the size of a net, their computation is expensive. This paper aims to find the strict minimal number of siphons in a class of Petri nets, called extended systems of linear simple sequential process with resources, which can model flexible manufacturing systems where there exist no flexible processing routings except for the idle state and each operation state may require more than one sort of resources. First, a relationship between structural properties and strict minimal siphons in the class of Petri net is verified. Second, we define the resource digraph of the class net. Finally, based on the obtained results, a method to find the set of strict minimal siphons is proposed. A running example is used to demonstrate the proposed methods.