LAUSR

Elementary siphons play an important role in designing deadlock prevention policies for flexible manufacturing systems modeling by Petri nets. This article proposes a deadlock control algorithm with maximally reachable number to cope with deadlock problems in ordinary Petri nets. First, we solve all elementary siphons and dependent siphons and then add both a control place and a control transition to each elementary siphon so that an extended net system ( N ′ , M ′ ) is obtained. Second, by constructing an integer programming problem of P-invariants of ( N ′ , M ′ ) , the controllability test for dependent siphons in N ′ is performed via this integer programming problem. Accordingly, a few of control places and control transitions are added for those dependent siphons that do not meet controllability as well. Therefore, a live controlled system ( N * , M * ) with maximally reachable number rather than number of maximally permissive behavior can be achieved. The correctness and efficiency of the proposed deadlock control algorithm is verified by a theoretical analysis and several examples that belong to ordinary Petri nets. Unlike these deadlock prevention policies with number of maximally permissive behavior in the existing literature, the proposed deadlock control algorithm can generally obtain a live controlled system ( N * , M * ) whose reachable number is the same as that of an original uncontrolled net (N0, M0), that is, maximally reachable number is greater than number of maximally permissive behavior.