A two-stage deadlock control policy with maximally reachable number for ordinary Petri nets
LI Shao-yong
XIAO Xing-da
CAI Ying
HOU Cai-qin
HAN Xi-lian
MA Bing-shan
Abstract：This paper develops a two-stage deadlock control policy (DCP) with maximally reachable number (MRN) for the deadlock problems in ordinary Petri nets (OPNs).First,this DCP solves elementary siphons (ESs) and dependent siphons (DSs) in the original uncontrolled net (No,Mo) and then adds a control place (CP) and a control transition (CT) for each ES.Accordingly,an extended net system (N',M') is obtained.Second,the controllability test for DSs in No is executed by means of constructing an integer programming problem (IPP) of P-invadants of N'.If all DSs meet the controllability,then a live controlled system (N*,M*) is achieved directly,implying that the extended net system (N',M') is live.Conversely,the corresponding CPs and CTs are added for those DSs that cannot meet the controllability.Therefore,the live controlled system (N*,M*) can be obtained as well.Theoretical analysis and examples show the correctness and efficiency of the proposed DCE Compared with the relevant deadlock prevention policies with number of maximally permissive behavior (NMPB) in the existing literature for OPNs,the reachable number of the live controlled system (N*,M*) obtained by the proposed DCP is the same as that of the original uncontrolled net (No,Mo),i.e.,maximally reachable number (MRN) is greater than NMPB.
Keywords：Petri netsdeadlock controlelementary siphon (ES)maximally reachable number (MRN)number of maximally permissive behavior (NMPB)
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：8( 243-250 )