A Quick Heuristic Algorithm for Enforcing the Liveness of S3PR Petri Nets

The optimal deadlock avoiding, deadlock recovery, as well as deadlock detection in Petri nets are the NP-hard problems. For this reason, heuristic algorithms for finding the approximate solutions of such problems are of a great interest. In the paper a heuristic method of deadlock recovery for the S
³
PR nets, which are often used for modelling of manufacturing systems, is proposed. The method is based on the idea of resetting the process instances in the S
³
PR nets and a heuristic for breaking the cycles in the wait-for graphs. The method does not require any time consuming operations such as construction of the reachability graph, explicit detecting of all reachable deadlocks or all elementary cycles in a wait-for graph, hence it is quick. The simple recovery transitions are added to the net providing recovery from both global and local deadlocks.