Optimization And Implementation Of Some Algorithms In Liveness-enforcement For WS~3PR

Strict minimal siphon (SMS) is the structural cause of the occurrence of deadlock in Petri nets. As long as there is a strict minimal siphon that is insufficiently marked, there is a deadlock in the Petri net. Therefore, the strategies of deadlock prevention in Petri nets are derived according to this structural objects . The number of SMS in a Petri net grows exponentially with respect to the size of net model. Most of the strategies of deadlock prevention based on SMS suffer from computational complexity problems. To evaluate the computational efficiency of various strategies of deadlock prevention, this thesis investigates a new algorithm that can search all SMS in a Petri net.This research firstly uses an iterative method with MIP to search all the maximal siphons unmarked in a Petri net, then all SMS contained in every maximal unmarked siphon are searched. The main achievements of the research are the two algorithms that can search all SMS from a maximal unmarked siphon as well as enumeration and backtracking methods of siphon computation. The algorithm complexity of enumeration is too high and that of backtracking one is low enough (linear). However, the use of the backtracking algorithm is limited by the structure derived from the maximal unmarked siphon. It only could be used for a maximal unmarked siphon that contains at least one certain place.