A Fast Algorithm To Find A Set Of Elementary Siphons For A Class Of Petri Nets

As a typical discrete event system, the flexible manufacturing systems (FMS) are one of the important application fields of Petri nets. In an FMS, the competition for shared resources can cause deadlocks. The deadlock prevention approach is a deadlock control based on siphons. The siphons emptied lead to deadlocks in the system. It is proved that if the elementary siphons in a net are controlled, the whole net is live and can not deadlock. Elementary siphons are a special subset of strict minimal siphons (SMS), and their number is much smaller than one of the SMS, and not beyond the size of the net.All the known SMS are the prerequisite for the elementary siphons in existing methods. However, the number of siphons grows in general exponentially with respect to the size of the Petri nets. This paper proposes an algorithm for a set of elementary siphons from part of SMS for a subclass of Petri nets - S~3PR net. According to the structure of S~3PR net, a resource circuit corresponds to a siphon and an SMS in the case that branch arcs are not included in an S~3PR. So an S~3PR is abstracted to a directed resource graph. The concept of complementary matrix is proposed in this work, and it is proved that elementary siphons are a basis in the siphon space of complementary matrix. Also, the complementary set of an SMS is obtained from a resource circuit. As a result, with graph theory, we convert the computation of the SMS to the resource circuit satisfying some conditions in a directed resource graph. According to many examples we have done, our method is applied to the large net, runs in a short time and is much efficient.