# A Multistep Look-Ahead Deadlock Avoidance Policy for Automated Manufacturing Systems

Authors: Chao Gu; Zhiwu Li; Abdulrahman Al-Ahmari
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

For an automated manufacturing system (AMS), it is a computationally intractable problem to find a maximally permissive deadlock avoidance policy (DAP) in a general case, since the decision on the safety of a reachable state is NP-hard. This paper focuses on the deadlock avoidance problem for systems of simple sequential processes with resources (S3PR) by using Petri nets structural analysis theory. Inspired by the one-step look-ahead DAP that is an established result, which is of polynomial complexity, for an S3PR without one-unit-capacity resources shared by two or more resource-transition circuits (in the Petri net model) that do not include each other, this research explores a multiple-step look-ahead deadlock avoidance policy for a system modeled with an S3PR that contains a shared one-unit-capacity resource in resource-transition circuits. It is shown that the development of an optimal DAP for the considered class of Petri nets is also of polynomial complexity. It is indicated that the steps needed to look ahead in a DAP depend on the structure of the net model. A number of examples are used to illustrate the proposed method.


---

## Body

## 1. Introduction

Automated manufacturing systems (AMSs) are a burgeoning production mode so as to respond to the undulation of the market and the requirements of customization. Such a system is based on computer control, which is composed of a finite set of resources. In an AMS, the whole system or a portion of it cannot terminate its task and remains eventually blocked if deadlocks occur due to the interactional parts and the shared resources [1]. It is required to harmonize the shared resources to ensure that the AMS is deadlock-free, and then the system resources will be fully utilized [2–4].The occurrences of deadlocks in highly automated systems may lead to serious problems or considerable economy loss. Deadlock problems in AMSs stem from the limited production, storage, and transportation resources, which may bring about a system-wide standstill. In [5], deadlocks will happen if the following four conditions are satisfied: no preemption, hold and wait, circular wait, and mutual exclusion. Mutual exclusion means that a resource can be utilized by one process and there is no other process that can use it at the same time. To break this condition, it is trivial to make all resources not shared by processes, which, however, may lead to a significant increase of system construction cost.Petri nets [6] are an effective tool for modeling and control of discrete event systems [7, 8]. They become a popular mathematical formalism to deal with deadlock problems in discrete event systems [9, 10] as well as scheduling and supervisory control [11–18]. To manage the problem of deadlocks in a system, three methods have been developed by researchers and practitioners. They are prevention, detection and recovery, and avoidance [19–27]. By setting up an offline resource scheduling or allocation policy, a system can be deadlock-free with deadlock prevention. Detection and recovery methods make use of a monitoring controller for detecting the deadlock occurrence and then recover the production process by terminating some deadlocked processes such that some involved resources are released. The implementation of deadlock avoidance usually deploys an online control method, which is motivated by the traditional feedback control in linear time-invariant systems. At each state, a controller decides to disable some enabled events such that a feasible event sequence, keeping the system being deadlock-free, is generated. This paper is devoted to the deadlock avoidance for a class of automated manufacturing systems by formulating a multistep look-ahead DAP.Currently, the research on deadlock control is mainly based on structural analysis techniques such as siphons [28, 29] and resource circuits or reachability graphs [30]. The work in [22] reports a siphon-based deadlock control policy by exploring the fact that an unmarked siphon at a reachable marking implies the occurrence of a deadlock or unsafe state. A control place, sometimes called a monitor, is designed for each siphon that can be empty at reachable markings. However, it suffers from the structural complexity problem, since the number of control places is in theory equal to that of siphons to be controlled. In 2004, Li and Zhou proposed the notion of elementary siphons. It proves that deadlocks can be prevented by adding a control place for each elementary siphon to ensure that, under some conditions, it is always marked at any reachable marking. This method requires less control places and thus is applicable to large-sized Petri nets. In order to avoid a complete siphon enumeration, the work finds a mixed integer programming (MIP) based deadlock detection method that enumerates a portion of siphons only. A survey on a variety of deadlock control approaches in the Petri net formalism is reported in the studies from the standpoint of structural complexity, behavior permissiveness, and computational complexity of a liveness-enforcing supervisor.Based on the reachability graph analysis, many researchers develop plentiful approaches to control a system. Chen and Li [31] use a vector covering approach to reduce the legal markings and first-met bad markings (FBMs) to two small sets. By designing control places, a maximally permissive control method can be established. Based on place invariants, Chen and Li [32] develop a deadlock prevention method that can find an optimal liveness-enforcing Petri net supervisor with the minimal number of control places. The authors in [33] present a new notion of interval inhibitor arcs as well as their applications to deadlock prevention. An optimal Petri net supervisor that can prevent a system from reaching illegal markings is designed. Recently, a method about designing an optimal Petri net supervisor with data inhibitor arcs is developed [34]. Data inhibitor arcs can enhance the modeling and expression convenience of a Petri net such that an optimal liveness-enforcing supervisor can be computed even if the legal state space of a plant is nonconvex.Inspired by the work in [24, 25], this paper investigates the synthesis problem of an optimal DAP, with polynomial complexity, for AMSs in the framework of Petri nets. Deadlocks can be described as a perfect maximal resource-transition circuit (MPRT-circuit). As its name suggests, a resource-transition circuit in a Petri net modeling an AMS is a circuit consisting of resource places and transitions only. It is said to beperfect if the output transitions of the operation places associated with the circuit are exactly the transitions in this circuit. If a resource-transition circuit is saturated at a reachable state in an S3PR, then the state is not safe, implying that it does not belong to the legal state set. The concept of ξ-resources plays an important role in the development of the DAP in [24]. A resource is said to be a ξ-resource if its capacity is one and shared by two or more MPRT-circuits that do not include each other. With the utilization of deadlock characteristic description, it is first proved that there are only two types of reachable markings that are safe ones and deadlocks, in an AMS modeled with an S3PR without ξ-resources [19]. Under the circumstance, a DAP only needs to prohibit the transitions whose firing leads a system to deadlocks. Consequently, an optimal DAP can be formulated by a one-step look-ahead policy [19, 35] to check whether the forthcoming state is safe or not. Furthermore, the proposed optimal DAP is of polynomial complexity with respect to the system scale.For the case that an S3PR contains ξ-resources, the work in [35] indicates that it is worth exploring a multiple-step look-ahead policy such that its computation remains tractable. The research conducted in the current paper initially provides a positive answer to this problem. Enlightened by the work in [19, 35], this paper investigates an optimal DAP for a class of S3PR with a ξ-resource by formulating a multiple-step look-ahead policy. It is shown that the number of steps to look ahead to check the safety of a state depends on the structure of a net model only. Furthermore, the optimal DAP is of polynomial complexity.The rest of the paper is organized as follows. Section2 reviews some basic notions and characterizations of Petri nets and S3PR. Section 3 develops a multiple-step look-ahead DAP for an S3PR model with a ξ-resource. By demonstrating examples, a conservation law has been put forward. In Section 4, a k-step look-ahead DAP for an S3PR model with a ξ-resource is presented. Finally, some conclusions and future work are summarized in Section 5.


## 2. Basic Notions of Petri Nets and the S3PR Models

This section briefly presents some definitions and notations with respect to Petri nets and the S3PR net class.


### 2.1. Basic Definitions of Petri Nets

A Petri net is a four-tupleN=(P,T,F,W), where P is called the set of the places and T is called the set of the transitions, P and T are finite, nonempty, and disjoint sets, that is, P≠∅, T≠∅, and P∩T=∅. F⊆P×T∪T×P is called the set of directed arcs from places to transitions or from transitions to places. W:P×T∪T×P→N is a mapping that assigns a weight to each arc, that is, if f∈F, W(f)>0; otherwise, Wf=0, where N is a set of nonnegative integers. W is called the weight function of a Petri net. From graph theory point of view, a Petri net is a bipartite digraph.A markingM of a Petri net N=P,T,F,W is a mapping: P→N. N,M0 is referred to as a net system or marked net. M0 is the initial marking of N. The markings and vectors are usually described by using a multiset or formal sum notation for economy of space. For simplicity, a Petri net N with initial marking M0 can be written as (N,M0) or (P,T,F,W,M0). Let p∈P be a place of a Petri net N. Place p is marked at M if M(p)>0. A set of places D⊆P is marked at M if at least one place is marked; namely, ∃p∈D,M(p)>0. M(D)=∑p∈DM(p) is the total number of tokens in D at M.Letx∈P∪T be a node of a Petri net N=P,T,F,W. The preset of x, denoted by x•, is defined as x•=y∈P∪T∣(y,x)∈F. The postset x• is defined as x•=y∈P∪T∣(x,y)∈F. Given a place (transition) p(t), the elements in its preset are called the pretransitions (preplaces) of p(t); otherwise, they are named as posttransitions (postplaces).LetN=(P,T,F,W) be a Petri net. A transition t∈T is enabled at M if ∀p∈•t, M(p)⩾W(p,t), denoted by Mt. An enabled transition t can fire. After firing, the Petri net will transit to another state, generating a new marking M′, that is, ∀p∈P, M′(p)=M(p)-W(p,t)+W(t,p), which is denoted as M[t〉M′. A Petri net is said to be self-loop-free if there do not exist a place p and a transition t such that (p,t)∈F and (t,p)∈F. A self-loop-free Petri net can be represented by an incidence matrix [N] with [N](p,t)=W(t,p)-W(p,t) that is an integer matrix indexed by P and T.MarkingM′ is reachable from M if there exist a feasible firing sequence of transitions (transition sequence for the sake of simplicity) σ=t1,t2,…,tn and markings M1,M2,…,Mn-1 such that M[t1〉M1[t2〉⋯Mn-1[tn〉M′ holds. Given a Petri net (N,M0), the set of all markings generated from the initial marking M0 is called the reachability set of (N,M0), denoted by R(N,M0).A vectorI:P→Z indexed by P with Z being the set of integers is called aP-vector. I is called a P-invariant if IT[N]=0T. It is called a P-semiflow if ∀p∈P, I(p)≥0. Let I be aP-vector. I=p∣I(p)>0 is called the support ofP-vector I. A nonempty place subset S⊆P is a siphon if S•⊆S•. A siphon S is minimal if the removal of any place from S makes the fallacy of S•⊆S•. A siphon is strict if it does not contain the support of a P-semiflow. The set of strict minimal siphons in a Petri net is denoted by Π.A pathα in a Petri net is a string of nodes, that is, α=x1x2⋯xn, where xi∈P∩T, i∈1,2,…,n. A circuit is a path with x1=xn. A simple circuit is a circuit where no node can appear more than once except for x1 and xn.


### 2.2. S3PR Models

This section reviews the primary notions and properties of the system of simple sequential processes with resources, which is called an S3PR to be defined from the standpoint of Petri nets [22]. It represents an important net type that can model a large class of automated flexible manufacturing systems. This class of Petri nets has been extensively studied, in addition to its generality, because of its perfect structural and behavioral properties.Definition 1.
A simple sequential process (S2P) is a Petri net N=(PA∪{p0},T,F), satisfying the following statements:(1)
PA≠∅ is called the set of the activity (operation) places;(2)
p0∉PA is called the process idle place or idle place;(3)
N is a strongly connected state machine;(4)
every circuit ofN contains the place p0.Definition 2.
An S2P with resources (S2PR) is a Petri net N=({p0}∪PA∪PR,T,F), satisfying the following:(1)
The subnet generated fromX=PA∪{p0}∪T is an S2P;(2)
PR≠∅,PA∪p0∩PR=∅;(3)
∀p∈PA,∀t∈p•,∀t′∈p•,∃rp∈PR,t•∩PR=t′•∩PR={rp};(4)
∀r∈PR,r••∩PA=r••∩PA≠∅; ∀r∈PR,r•∩r•=∅;(5)
(••p0)∩PR=(p0)••∩PR=∅.Definition 3.
Given an S2PR N=(PA∪{p0}∪PR,T,F), an initial marking M0 is called an acceptable initial marking for N if(1)
M0p0≥1;(2)
M0p=0,∀p∈PA;(3)
M0(r)≥1,∀r∈PR.Definition 4.
An S3PR, that is, a system of S2PR, can be defined recursively as follows:(1)
An S2PR is an S3PR.(2)
LetNi=(PAi∪{pi0}∪PRi,Ti,Fi)(i∈{1,2}) be two S3PR, satisfying (PA1∪{p10})∩(PA2∪{p20})=∅, PR1∩PR2=PC≠∅. A Petri net N=(PA∪{p0}∪PR,T,F) composed of N1 and N2, denoted as N=N1∘N2, through PC is still an S3PR, defined as PA=PA1∪PA2, P0={p10}∪{p20}, PR=PR1∪PR2, T=T1∪T2, and F=F1∪F2.Definition 5.
Given an S3PR N, (N,M0) is an acceptably marked S3PR if(1)
(N,M0) is an acceptably marked S2PR;(2)
N=N1∘N2, where (Ni,M0i) (i=1,2) is an acceptably marked S3PR. Moreover, ∀i∈{1,2}, ∀p∈PAi∪{pi0}, M0(p)=M0i(p); ∀i∈{1,2}, ∀r∈PRi∖PC, M0(r)=M0i(r); ∀r∈PC, M0(r)=max⁡M01r,M02r.Given a resourcer∈PR in an S3PR, the set of holders of r is denoted as H(r)=r••∩PA. For a siphon S in an S3PR, S=SR∩SA, where SR=S∩PR and SA=S∩PA.


## 2.1. Basic Definitions of Petri Nets

A Petri net is a four-tupleN=(P,T,F,W), where P is called the set of the places and T is called the set of the transitions, P and T are finite, nonempty, and disjoint sets, that is, P≠∅, T≠∅, and P∩T=∅. F⊆P×T∪T×P is called the set of directed arcs from places to transitions or from transitions to places. W:P×T∪T×P→N is a mapping that assigns a weight to each arc, that is, if f∈F, W(f)>0; otherwise, Wf=0, where N is a set of nonnegative integers. W is called the weight function of a Petri net. From graph theory point of view, a Petri net is a bipartite digraph.A markingM of a Petri net N=P,T,F,W is a mapping: P→N. N,M0 is referred to as a net system or marked net. M0 is the initial marking of N. The markings and vectors are usually described by using a multiset or formal sum notation for economy of space. For simplicity, a Petri net N with initial marking M0 can be written as (N,M0) or (P,T,F,W,M0). Let p∈P be a place of a Petri net N. Place p is marked at M if M(p)>0. A set of places D⊆P is marked at M if at least one place is marked; namely, ∃p∈D,M(p)>0. M(D)=∑p∈DM(p) is the total number of tokens in D at M.Letx∈P∪T be a node of a Petri net N=P,T,F,W. The preset of x, denoted by x•, is defined as x•=y∈P∪T∣(y,x)∈F. The postset x• is defined as x•=y∈P∪T∣(x,y)∈F. Given a place (transition) p(t), the elements in its preset are called the pretransitions (preplaces) of p(t); otherwise, they are named as posttransitions (postplaces).LetN=(P,T,F,W) be a Petri net. A transition t∈T is enabled at M if ∀p∈•t, M(p)⩾W(p,t), denoted by Mt. An enabled transition t can fire. After firing, the Petri net will transit to another state, generating a new marking M′, that is, ∀p∈P, M′(p)=M(p)-W(p,t)+W(t,p), which is denoted as M[t〉M′. A Petri net is said to be self-loop-free if there do not exist a place p and a transition t such that (p,t)∈F and (t,p)∈F. A self-loop-free Petri net can be represented by an incidence matrix [N] with [N](p,t)=W(t,p)-W(p,t) that is an integer matrix indexed by P and T.MarkingM′ is reachable from M if there exist a feasible firing sequence of transitions (transition sequence for the sake of simplicity) σ=t1,t2,…,tn and markings M1,M2,…,Mn-1 such that M[t1〉M1[t2〉⋯Mn-1[tn〉M′ holds. Given a Petri net (N,M0), the set of all markings generated from the initial marking M0 is called the reachability set of (N,M0), denoted by R(N,M0).A vectorI:P→Z indexed by P with Z being the set of integers is called aP-vector. I is called a P-invariant if IT[N]=0T. It is called a P-semiflow if ∀p∈P, I(p)≥0. Let I be aP-vector. I=p∣I(p)>0 is called the support ofP-vector I. A nonempty place subset S⊆P is a siphon if S•⊆S•. A siphon S is minimal if the removal of any place from S makes the fallacy of S•⊆S•. A siphon is strict if it does not contain the support of a P-semiflow. The set of strict minimal siphons in a Petri net is denoted by Π.A pathα in a Petri net is a string of nodes, that is, α=x1x2⋯xn, where xi∈P∩T, i∈1,2,…,n. A circuit is a path with x1=xn. A simple circuit is a circuit where no node can appear more than once except for x1 and xn.


## 2.2. S3PR Models

This section reviews the primary notions and properties of the system of simple sequential processes with resources, which is called an S3PR to be defined from the standpoint of Petri nets [22]. It represents an important net type that can model a large class of automated flexible manufacturing systems. This class of Petri nets has been extensively studied, in addition to its generality, because of its perfect structural and behavioral properties.Definition 1.
A simple sequential process (S2P) is a Petri net N=(PA∪{p0},T,F), satisfying the following statements:(1)
PA≠∅ is called the set of the activity (operation) places;(2)
p0∉PA is called the process idle place or idle place;(3)
N is a strongly connected state machine;(4)
every circuit ofN contains the place p0.Definition 2.
An S2P with resources (S2PR) is a Petri net N=({p0}∪PA∪PR,T,F), satisfying the following:(1)
The subnet generated fromX=PA∪{p0}∪T is an S2P;(2)
PR≠∅,PA∪p0∩PR=∅;(3)
∀p∈PA,∀t∈p•,∀t′∈p•,∃rp∈PR,t•∩PR=t′•∩PR={rp};(4)
∀r∈PR,r••∩PA=r••∩PA≠∅; ∀r∈PR,r•∩r•=∅;(5)
(••p0)∩PR=(p0)••∩PR=∅.Definition 3.
Given an S2PR N=(PA∪{p0}∪PR,T,F), an initial marking M0 is called an acceptable initial marking for N if(1)
M0p0≥1;(2)
M0p=0,∀p∈PA;(3)
M0(r)≥1,∀r∈PR.Definition 4.
An S3PR, that is, a system of S2PR, can be defined recursively as follows:(1)
An S2PR is an S3PR.(2)
LetNi=(PAi∪{pi0}∪PRi,Ti,Fi)(i∈{1,2}) be two S3PR, satisfying (PA1∪{p10})∩(PA2∪{p20})=∅, PR1∩PR2=PC≠∅. A Petri net N=(PA∪{p0}∪PR,T,F) composed of N1 and N2, denoted as N=N1∘N2, through PC is still an S3PR, defined as PA=PA1∪PA2, P0={p10}∪{p20}, PR=PR1∪PR2, T=T1∪T2, and F=F1∪F2.Definition 5.
Given an S3PR N, (N,M0) is an acceptably marked S3PR if(1)
(N,M0) is an acceptably marked S2PR;(2)
N=N1∘N2, where (Ni,M0i) (i=1,2) is an acceptably marked S3PR. Moreover, ∀i∈{1,2}, ∀p∈PAi∪{pi0}, M0(p)=M0i(p); ∀i∈{1,2}, ∀r∈PRi∖PC, M0(r)=M0i(r); ∀r∈PC, M0(r)=max⁡M01r,M02r.Given a resourcer∈PR in an S3PR, the set of holders of r is denoted as H(r)=r••∩PA. For a siphon S in an S3PR, S=SR∩SA, where SR=S∩PR and SA=S∩PA.


## 3. DAP and Its Conservation Law in S3PR

This section develops an optimal DAP for a class of S3PR. The work in [19, 23] uses resource-transition circuits (RT-circuits) to characterize deadlock markings. An RT-circuit is a circuit that contains resource places and transitions only. An RT-circuit is said to beperfect if the pretransitions of the resources in the RT-circuit are exactly their posttransitions. When a maximal perfect RT-circuit (MPRT-circuit) is saturated, deadlocks occur in a system. A resource is called a ξ-resource if it is of one-unit (capacity) shared by two or more MPRT-circuits that do not contain each other. In fact, it is proved that, in an S3PR without ξ-resource, there only exist two types of reachable markings: safe and deadlock markings. The safe markings are states which belong to the live zone (LZ) that, from the viewpoint of the reachability graph, is the maximal strongly connected component including the initial marking. We need to prohibit the transitions whose firing leads to deadlock markings by a DAP.Definition 6.
Given an S3PR (N,M0), suppose that there exist two RT-circuits Θ1 and Θ2 that do not contain each other, such that (Θ1∩Θ2)∩PR={r}. The resource r is called a ξ-resource if M0(r)=1.For an S3PR without ξ-resource, that is, there are no one-unit resources shared by two or more resource-transition circuits that do not include each other, there is an algorithm with polynomial complexity to determine the safety of a state reachable from a safe one. Therefore, an optimal DAP with polynomial complexity can be constructed by a one-step look-ahead method.On the other hand, for an S3PR containing ξ-resources, by means of the theory of regions [21] or the reachability graph analysis of the net, we can obtain the number of steps to look ahead and accordingly derive an optimal DAP. However, this will enumerate all the reachable states since the number of markings grows fast and even exponentially with respect to the system scale and the initial marking. In the rest of the paper, we discuss a special class of S3PR that contains only one ξ-resource with some other structural constraints, which is called a unitary S3PR (US3PR).Definition 7.
LetS∈Π be a strict minimal siphon in an S3PR. Resource r∈SR is said to be independent if ∄p∈SA, p∈H(r). Otherwise r is said to be dependent. Let SinR denote the set of independent resources in a siphon S.Definition 8.
A holder-resource circuit (HR-circuit) with respect to a resourcer in an S3PR, denoted by H(r), is a simple circuit if it contains only one resource r with Hr=1, an activity place p∈H(r), and transitions. If a resource corresponds to one holder-resource circuit only, the holder-resource circuit is said to be monoploid.Definition 9.
An S3PR (N,M0) is said to be unitary if there is only one ξ-resource and ∀S∈Π, ∀r∈SinR, and r is associated with a monoploid holder-resource circuit.Different models may lead to different steps to look ahead in order to construct an optimal DAP. This paper shows that, in a unitary S3PR, no matter how the tokens distribute in resource places, the number of steps looking ahead remains the same, which is called aconservation law with respect to the structure of an S3PR. That is to say, in order to implement an optimal DAP for a US3PR, the number of steps to look ahead is independent of the initial marking.For example, Figure1 demonstrates an S3PR, where p9–p13 are resource places, p1–p8 are activity places, and p14 and p15 are idle places. There are three strict minimal siphons, that is, Π=S1,S2,S3 with S1=p3,p8,p9,p10,p11,p12, S2=p4,p6,p12,p13, and S3=p4,p8,p9,p10,p11,p12,p13. Initially, the activity places are void of tokens and the idle places contain a certain amount of tokens. Except for the RT-circuits, there also exist HR-circuits. An HR-circuit consists of a holder place, a resource place, and some transitions. In Figure 1, p2t3p10t2p2 and p7t9p11t8p7 are monoploid HR-circuits. Let M0(p14)=M0(p15)=10. As for the resource places, we assume that each of p9 and p13 has one token only at the initial marking since this resource configuration does not interfere with the steps to look ahead. We assume M0(p12)=1, implying that it is a ξ-resource. By Definition 9, the net is a US3PR. Suppose that M0p10=M0p11=1. It needs three steps to look ahead for an optimal DAP, as shown in Figure 2, which is analyzed in detail as follows.Figure 1
A US3PR model.Figure 2
Simulation results in Figure1 in the case of M0p10=M0p11=1.In Figure2, LZ represents the live zone and DZ denotes the dead zone [21]. Specifically, the markings in LZ form the set of legal states and those in DZ form the set of illegal states. An optimal DAP should ensure that all legal states are accessible while all illegal states are forbidden. DZ∗, as a subzone of DZ, represents the markings at which no strict minimal siphon is empty. Specifically, since p6 and p11 are marked at the markings in DZ∗, siphons S1, S2, and S3 are marked in DZ∗. In this case, a one-step look-ahead DAP is not applicable due to the presence of such states in DZ∗. That is to say, if DZ∗ is empty, an optimal one-step look-ahead DAP can be employed for this example. In the case of no confusion, we use LZ (DZ) to denote set of the markings in LZ (DZ).Definition 10.
A markingM∈ DZ is said to be pseudo-safe in an S3PR (N,M0) if ∄S∈Π,M(S)=0. The set of pseudo-safe markings is denoted by DZ∗.To further confirm the results, we change the number of tokens in resource places. AsM0p10 and M0p11 increase, it is found that the steps to look ahead remain three; that is to say, a three-step look-ahead method is applicable when M0(p10) and M0(p11) increase. In fact, in an S3PR, the allocation of resources in a system can be affected by idle places. We assume that M0(p14) and M0(p15) are big enough. In this sense, the removal of idle places does not affect the steps to look ahead. The simplified version of the S3PR is visualized in Figure 3. We set the same parameters as in Figure 2, that is, M0(p10)=M0(p11)=1. Figure 4 shows the simulation result.Figure 3
A simplified S3PR model based on Figure 1.Figure 4
Simulation results in Figure3 in the case of M0(p10)=M0(p11)=1.To generalize the result, we assume thatM0p10=x and M0(p11)=y, where x and y are arbitrary positive integers. However, it still needs three steps to look ahead in order to find an optimal DAP, as detailed in Figure 5. We could easily figure out that all of the six markings shown in Figure 4 increase by adding (x-1) tokens in p2 and (y-1) tokens in p7.Figure 5
Simulation results in Figure3 in the case of M0(p10)=x and M0(p11)=y.By this reduced model, it shows that a three-step look-ahead DAP is always optimal. By comparing and analyzing the reachability graph of the net in Figure1 and its reduced model, it is proved that, in a US3PR, the idle places initially with enough tokens will not affect the steps that are needed to look ahead. Thus, for convenience, we only consider its reduced version.Let us consider a US3PR shown in Figure 6, where p13–p21 are the resource places and p1–p12 are the activity places. We set M0(p16)=1 to ensure that p16 is a ξ-resource. Each of the places p13 and p21 has one token. Initial tokens in p14, p15, and p17–p20 can be variable to explore the relationship between the steps and their initial markings. Let each of them first contain only one token, respectively.Figure 6
A US3PR model.As shown in Figure7, we need three or four steps to reach a marking in DZ∖DZ∗ from a border marking in LZ. Note that a border marking in LZ means that it is the father of a marking in DZ. In summary we need four steps to look ahead in a DAP, as the worst case should be considered. Next we propose a result on the initial tokens in monoploid HR-circuits, which is called a conservation law with respect to independent resources.Figure 7
Simulation results of Figure6.Definition 11.
Given a Petri net(N,M0), a marking Mf∈DZ∗ is said to be a first-met marking in DZ∗ if ∃M∈LZ,∃t∈T,M[t〉Mf. The set of first-met markings in DZ∗ is denoted as Mf.Definition 12.
Given a Petri net(N,M0), LZ∗⊆LZ is defined as the set of the prestates of all first-met markings in DZ∗; that is, LZ∗=M∣M∈LZ,∃t∈T,∃Mf∈Mf,MtMf.Theorem 13.
Given a unitary S3PR (N,M0), the initial marking of the resource in a monoploid holder-resource circuit does not affect the maximal number of steps needed to look ahead in an optimal DAP.Proof.
We consider two cases: (1) a resourcer in a monoploid holder-resource circuit is not included in a strict minimal siphon and (2) a resource r in a monoploid holder-resource circuit is included in a strict minimal siphon. It is apparent that a resource not in a strict minimal siphon does not contribute to deadlocks in an S3PR. We hence consider the second case next.
Let(N,M0) be a US3PR with a ξ-resource, namely, p8, which is, without loss of generality, shown in Figure 8. Let m,n,p, and q represent the numbers of monoploid HR-circuits topologically associated with p8, where m,n,p,q∈N.
LetPrα and Phα represent the set of resource places and holder places of α monoploid HR-circuits ( α∈m,n,p,q, resp.). The node set of the α monoploid HR-circuits is Pα=Prα∪Phα, where we assume Prα=pr1,pr2,…,prα and Phα=ph1,ph2,…,phα.
As shown in Figure8, the holder places are initially unmarked. Then the simplest initial marking is(1)M0=p7+pr1m+pr2m+⋯+prmm+pr1n+pr2n+⋯+prnn+p8+pr1p+pr2p+⋯+prpp+pr1q+pr2q+⋯+prqq+p9,where pryx is a resource place in Figure 8, x=m,n,p,q and y=1,2,…,x. Note that, at M0, each resource place pryx contains only one token. It is apparent that we need several steps to reach the prestates of the markings in Mf, which belong to LZ∗. We use ψ to denote such a number in the worst case.
For a more general case, let us assume thatpr1x,pr2x,…,prxx contain Δ1,Δ2,…,Δx resource units at some initial marking M0′, respectively, where Δ=λ,μ,ν,ω for x=m,n,p,q (λ,μ,ν,ω∈N). In this case, we have(2)M0′=p7+∑i=1mλipri+∑i=1nμipri+p8+∑i=1pνipri+∑i=1qωipri+p9.
On the other hand, suppose that there is a markingM0∗ with M0∗=∑i=1m‍(λi-1)phi+∑i=1n‍(μi-1)phi+∑i=1p‍(νi-1)phi+∑i=1q‍(ωi-1)phi+p7+∑i=1m‍pri+∑i=1n‍pri+p8+∑i=1p‍pri+∑i=1q‍pri+p9. By comparing the reachability graphs of (N,M0) and (N,M0∗), we conclude that, through the same steps, that is, ψ steps, both M0′ and M0∗ can reach the markings in Mf and then move to other markings. That is to say, the parts of the reachability graphs with respect to M0 and M0∗ can both reach all the markings in DZ∗ along the same path; that is, it generates the same steps that are needed to look ahead. This is because the emptiness of a siphon depends on the last transition whose firing empties it. The length of a path from a marking in LZ∗ to DZ∖DZ∗ depends on the steps of firing transitions in HR-circuits; that is, it depends on the number of HR-circuits associated with the siphon. By the definitions of M0∗ and M0′, a feasible transition sequence σ can be constructed such that M0∗[σ〉M0′, that is, M0∗∈RN,M0′. We conclude that the initial number of tokens in the resource places of the monoploid holder-resource circuits does not affect the maximal number of steps needed to look ahead in an optimal DAP.Figure 8
Ak-step look-ahead S3PR model.In this section, we overview the step look-ahead method that can help us to find out the deadlock markings. Theconservation law shows that, in the considered S3PR model, the steps look-ahead are irrelevant to the resources capacity of the specific resource places. In fact, it is related to the structure of a US3PR only. Different US3PR structures may generate steps look-ahead differently for an optimal DAP, and the steps look-ahead may be the same for different S3PR structures. Nevertheless, once the structure of a US3PR remains unchanged, the steps look-ahead remain unchanged. It can be regarded as an inherent nature of the model.


## 4. A Multistep Look-Ahead Method for a US3PR

Section3 indicates that the steps look-ahead depend on the S3PR structure. In this section, our attention is restricted to specific relationship between the steps and the structure of an S3PR. Some laws behind the multiple-step look-ahead method of an optimal DAP for an S3PR model with a ξ-resource are discovered. We classify US3PR into two types: those whose structure is a linear S3PR, that is, LS3PR [36], and those whose structure is a general S3PR. Note that an LS3PR (linear system of simple sequential processes with resources), strictly speaking, is not an extended but a restrictive version of an S3PR. Their difference is that a special constraint is imposed on the state machines in an LS3PR. A state machine in it does not contain choices at internal states that are not the idle states. Note that idle states represent job requests. For economy of space, the definition of an LS3PR is not presented here. For details, one can refer to the work in [36]. Some examples and experimental results are provided to illustrate the laws. Finally, a k-step look-ahead DAP is formulated.


### 4.1. LS3PR Models with a ξ-Resource

In this section, an LS3PR model with a ξ-resource is investigated. Figure 9 shows the symmetrical structures of two reduced LS3PR models. According to the reachability graph analysis, Figure 9(a) needs three steps look-ahead to avoid deadlocks, while Figure 9(b) needs two. Although the two nets seem to be totally symmetric, different from our imagination, the steps needed are distinct. Unless otherwise stated, a US3PR in this subsection refers to as a unitary LS3PR.Figure 9
Two reduced S3PR models derived from Figure 3.
(a)
(b)Let us consider a Petri net in Figure10. In order to make a comparison, its four variants are demonstrated in Figures 11 and 12. Some HR-circuits in Figure 10 are removed. It is shown that the net in Figure 10 needs four steps to look ahead. The reduced models in Figures 11(a) and 12(a) need four steps to look ahead. However, Figure 11(b) needs three steps to look ahead and Figure 12(b) needs two steps only. Lemmas 14 and 15 are derived from Figure 8.Figure 10
An S3PR model.Figure 11
Two reduced S3PR models derived from Figure 10.
(a)
(b)Figure 12
Two reduced S3PR models derived from Figure 10.
(a)
(b)Lemma 14.
Let(N,M0) be a US3PR and m,n,p, and qm,n,p,q∈N represent the numbers of monoploid holder-resource circuits associated with the ξ-resource, as shown in Figure 8. The numbers n and p determine the steps of an optimal DAP to look ahead.Proof.
Without loss of generality, suppose that a unitary S3PR with a ξ-resource r contains two RT-circuits: Θ1 and Θ2, where r∈Θ1∩Θ2 and M0(r)=1. Let m,n,p, and q represent the numbers of monoploid HR-circuits structurally associated with the ξ-resource. For x (x=m,n,p,q) HR-circuits, the set of nodes in the x HR-circuits is Px=Prx∪Phx, where Prx={pr1x,pr2x,…,prxx} and Phα={ph1x,ph2x,…,phαx}. Prx and Phx represent the sets of resource and holder places in the x HR-circuits, respectively.
By analyzing the reachability graph, all the markings in theDZ∗ are divided into two parts: Part I associated with Θ1 and Part II with Θ2. In Part I, a resource will transmit only from pr1x to prnx in sequence and then reach p8, that is, the intersection of Θ1 and Θ2 as well as the ξ-resource place. On the other hand, for Part II, a resource will transmit from prpx to pr1x in order and then reach p8 as well. This resource transmission can generate several pseudo-safe markings, that is, markings that belong to DZ∗, which causes multistep to look ahead in a DAP. Thus, the numbers n and p determine the steps needed to look ahead in a US3PR model.Lemma 15.
Let(N,M0) be a unitary S3PR and m,n,p,q represent the numbers of monoploid holder-resource circuits structurally associated with the ξ-resource. Let (m,n)=(0,0). ∀(p,q)≥(0,0), the number of steps to look ahead in an optimal DAP is (p+2). Let (p,q)=(0,0). ∀(m,n)≥(0,0), the number of steps to look ahead in an optimal DAP is (n+2).Proof.
For a unitary S3PR with a ξ-resource, (m,n)=(0,0) means that Θ1 consists of only a pair of resource places and transitions. Based on Lemma 14, Θ1 only generates one pseudo-safe marking, which can lead to a two-step look-ahead process. For Part II, there is at least one pseudo-safe marking and the steps look-ahead depend on p only. Therefore, (p+2) steps are necessary in an optimal DAP. On the other hand, (p,q)=(0,0) means that Θ2 consists of a pair of resource places and transitions only. Similar to the above-mentioned reasoning, (n+2) steps are required to look ahead in an optimal DAP.Lemma14 proposes the relationship between the number of steps to look ahead and that of resource places. Lemma 15 shows that the number of steps relates to p and n only. In fact, m and q have no effect on the final results. As a matter of fact, these two cases, that is, (m,n)=(0,0) and (p,q)=(0,0), are the reverse patterns. The part of n HR-circuits corresponds to that of p HR-circuits if the net structure is totally inverted and vice versa, which is demonstrated in Figure 8. The resource places in the two RT-circuits may be increased. For the US3PR in Figure 6, there may exist two or more kinds of steps look-ahead methods. However, the laws above-mentioned are also valid. The overall step look-ahead method can be a recombination of two or more basic kinds of step look-ahead processes. It is noted that the applicable look-ahead steps in an optimal DAP should be the maximal one generated form all step look-ahead processes.In Figure6, the S3PR with a ξ-resource consists of two RT-circuits. One needs three steps to look ahead, while the other needs four steps. Therefore, four steps should be an effective strategy for an optimal DAP, which is shown in Figure 7 in detail. According to the aforementioned conclusions, a k-step look-ahead method based S3PR structure with a ξ-resource is presented.Theorem 16.
Let(N,M0) be a US3PR. A k-step look-ahead optimal DAP satisfies k=max⁡n+2,p+2.Proof.
Consider a US3PR with a ξ-resource shared by two RT-circuits: Θ1 and Θ2, where r∈Θ1∩Θ2, and M0(r)=1. Let m,n,p, and q represent the numbers of monoploid HR-circuits associated with the ξ-resource. According to Lemmas 14 and 15, in the Θ1 part, the resource transmission process will generate n+1 pseudo-safe markings. From the steps look-ahead point of view, it takes n+2 steps from a border legal marking to a marking in DZ∖DZ∗ which unmarks a strict minimal siphon. For the Θ2 part, similarly, p+1 states in DZ∗ will lead to a (p+2)-step look-ahead procedure. Throughout the whole system and considering the worst case, max⁡n+2,p+2 steps will be necessary to look ahead in an optimal DAP.If we want to find an S3PR with a four-step look-ahead DAP, that is, k=4, by Theorem 16, k=max⁡n+2,p+2=4. There are two situations.(1)
n+2=4,p+2≤4, that is, n=2,p≤2.(2)
n+2≤4,p+2=4, that is, n≤2,p=2.Theoretically speaking, sincem and q HR-circuits make no difference to the consequence, there are innumerable structures that can be acceptable. We choose the first case. Let m=4, n=2; p=0, q=0. According to Figure 8, we can generate the structure in Figure 13, where the initial marking of the net is set as M0=p13+p14+p15+p16+p17+p18+p19+p20+p21. It needs four steps look-ahead, as seen in Figure 14. By introducing the k-step look-ahead-based structure, it is easy to find a k-step look-ahead S3PR model. Indeed, this structure is obviously not unique.Figure 13
An example of a four-step look-ahead structure derived from Figure8.Figure 14
Computation result in Figure13.


### 4.2. US3PR Model

The model considered in this subsection is not restricted to a US3PR that is an LS3PR. Figure 15 shows a typical S3PR model with a ξ-resource. In this model, resource places p11, p12, p14, and p15 are shared by the process t1p1t2p2t3p3t4p4t5. Let us suppose a new initial marking M0′ with M0′(p11)–M0′(p15)= 1. The related result is demonstrated in Figure 16. To exactly explore the relationship between the steps and the net structure, the set of DZ∗ is divided into a number of subsets that are disjoint.Figure 15
A typical S3PR model.Figure 16
Simulation result of the net in Figure15.Definition 17.
Given an US3PR (N,M0), let DZ1∗,DZ2∗,…,DZh∗ be a partition of DZ∗, that is, DZ∗=⋃j=1hDZj∗ and ∀i,j∈1,2,…,hi≠j, DZi∗∩DZj∗=∅. DZi∗ is said to be a critical subset of first-met markings in DZ∗ if the subgraph derived from DZi∗ in the reachability graph of (N,M0) is connected and any node in DZi∗ and any node in DZj∗(i≠j) are not connected.Definition 18.
Given a Petri net(N,M0), a critical group of states, or simply group, derived by DZi∗, denoted as g(DZi∗), contains DZi∗ and their father nodes in LZ and their leaf nodes in DZ, that is, g(DZi∗)=DZi∗∪M∣M∈LZ∗,∃t∈T,∃M′∈DZ∗,MtM′∪M∣M∈DZ∖DZ∗,∃M′∈DZ∗,M′tM.From Figure16, there are two groups in the reachability graph. As it shows, each group contains two states belonging to DZ∗. That is, each of them contains a three-step look-ahead procedure; that is, it needs three steps to look ahead. As shown in Table 1, M0(p11) and M0(p15) remain unchanged, as being one, since they do not affect the steps to look ahead in an optimal DAP. To ensure that the system contains a ξ-resource, we set M0p14=1. By changing M0p12 and M0p13, some laws can be identified. Through this table, it is clear that a three-step look-ahead method is always acceptable for the net in Figure 15. On the other hand, M0p13 makes no difference on the steps look-ahead and the number of groups for three-step look-ahead procedures. Finally, it is easy to recognize that M0p12 is related to the number of groups.Table 1
Simulation results of Figure14.
M
0
(
p
12
)
1
1
1
1
1
2
2
2
2
2
3
3
3
4
4
5
6
10
15
20
30
40
50
75
100
M
0
(
p
13
)
1
2
3
4
5
1
2
3
4
5
1
2
3
1
2
3
1
5
10
15
1
2
15
20
25
M
0
(
p
14
)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Steps
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
Number of groups
2
2
2
2
2
3
3
3
3
3
4
4
4
5
5
6
7
11
16
21
31
41
51
76
101Compared with an LS3PR, the appearance of such multiple groups stems from multiple processes in a system. There should exist some relation between the number of groups and that of processes, which is to be explored further. The obtained results are also in accord with the condition of the k-step look-ahead model; that is, it only relates to n and q. In this model, obviously we have n=1 and q=0. According to k=max⁡n+2,p+2, the steps that are needed to look ahead are exactly three. Theorem 19 presents the step look-ahead law based on this kind of type.Theorem 19.
Let(N,M0) be a US3PR. r and t represent the numbers of the HR-circuits as shown in Figure 17. A k-step look-ahead optimal DAP satisfies k=max⁡s+2,t+2.Figure 17
Ak-step look-ahead S3PR model.Proof.
It is similar to the proof of Theorem16.Note thats and t determine the number of steps look-ahead. However, because of the presence of the extra processes in a unitary S3PR, the resource transmitting procedure in holder places and resource places will be enlarged. Therefore, in this kind of model, the steps look-ahead may not be only one. It depends on the number of the extra processes in the model and the tokens distribution of the resource places.


## 4.1. LS3PR Models with a ξ-Resource

In this section, an LS3PR model with a ξ-resource is investigated. Figure 9 shows the symmetrical structures of two reduced LS3PR models. According to the reachability graph analysis, Figure 9(a) needs three steps look-ahead to avoid deadlocks, while Figure 9(b) needs two. Although the two nets seem to be totally symmetric, different from our imagination, the steps needed are distinct. Unless otherwise stated, a US3PR in this subsection refers to as a unitary LS3PR.Figure 9
Two reduced S3PR models derived from Figure 3.
(a)
(b)Let us consider a Petri net in Figure10. In order to make a comparison, its four variants are demonstrated in Figures 11 and 12. Some HR-circuits in Figure 10 are removed. It is shown that the net in Figure 10 needs four steps to look ahead. The reduced models in Figures 11(a) and 12(a) need four steps to look ahead. However, Figure 11(b) needs three steps to look ahead and Figure 12(b) needs two steps only. Lemmas 14 and 15 are derived from Figure 8.Figure 10
An S3PR model.Figure 11
Two reduced S3PR models derived from Figure 10.
(a)
(b)Figure 12
Two reduced S3PR models derived from Figure 10.
(a)
(b)Lemma 14.
Let(N,M0) be a US3PR and m,n,p, and qm,n,p,q∈N represent the numbers of monoploid holder-resource circuits associated with the ξ-resource, as shown in Figure 8. The numbers n and p determine the steps of an optimal DAP to look ahead.Proof.
Without loss of generality, suppose that a unitary S3PR with a ξ-resource r contains two RT-circuits: Θ1 and Θ2, where r∈Θ1∩Θ2 and M0(r)=1. Let m,n,p, and q represent the numbers of monoploid HR-circuits structurally associated with the ξ-resource. For x (x=m,n,p,q) HR-circuits, the set of nodes in the x HR-circuits is Px=Prx∪Phx, where Prx={pr1x,pr2x,…,prxx} and Phα={ph1x,ph2x,…,phαx}. Prx and Phx represent the sets of resource and holder places in the x HR-circuits, respectively.
By analyzing the reachability graph, all the markings in theDZ∗ are divided into two parts: Part I associated with Θ1 and Part II with Θ2. In Part I, a resource will transmit only from pr1x to prnx in sequence and then reach p8, that is, the intersection of Θ1 and Θ2 as well as the ξ-resource place. On the other hand, for Part II, a resource will transmit from prpx to pr1x in order and then reach p8 as well. This resource transmission can generate several pseudo-safe markings, that is, markings that belong to DZ∗, which causes multistep to look ahead in a DAP. Thus, the numbers n and p determine the steps needed to look ahead in a US3PR model.Lemma 15.
Let(N,M0) be a unitary S3PR and m,n,p,q represent the numbers of monoploid holder-resource circuits structurally associated with the ξ-resource. Let (m,n)=(0,0). ∀(p,q)≥(0,0), the number of steps to look ahead in an optimal DAP is (p+2). Let (p,q)=(0,0). ∀(m,n)≥(0,0), the number of steps to look ahead in an optimal DAP is (n+2).Proof.
For a unitary S3PR with a ξ-resource, (m,n)=(0,0) means that Θ1 consists of only a pair of resource places and transitions. Based on Lemma 14, Θ1 only generates one pseudo-safe marking, which can lead to a two-step look-ahead process. For Part II, there is at least one pseudo-safe marking and the steps look-ahead depend on p only. Therefore, (p+2) steps are necessary in an optimal DAP. On the other hand, (p,q)=(0,0) means that Θ2 consists of a pair of resource places and transitions only. Similar to the above-mentioned reasoning, (n+2) steps are required to look ahead in an optimal DAP.Lemma14 proposes the relationship between the number of steps to look ahead and that of resource places. Lemma 15 shows that the number of steps relates to p and n only. In fact, m and q have no effect on the final results. As a matter of fact, these two cases, that is, (m,n)=(0,0) and (p,q)=(0,0), are the reverse patterns. The part of n HR-circuits corresponds to that of p HR-circuits if the net structure is totally inverted and vice versa, which is demonstrated in Figure 8. The resource places in the two RT-circuits may be increased. For the US3PR in Figure 6, there may exist two or more kinds of steps look-ahead methods. However, the laws above-mentioned are also valid. The overall step look-ahead method can be a recombination of two or more basic kinds of step look-ahead processes. It is noted that the applicable look-ahead steps in an optimal DAP should be the maximal one generated form all step look-ahead processes.In Figure6, the S3PR with a ξ-resource consists of two RT-circuits. One needs three steps to look ahead, while the other needs four steps. Therefore, four steps should be an effective strategy for an optimal DAP, which is shown in Figure 7 in detail. According to the aforementioned conclusions, a k-step look-ahead method based S3PR structure with a ξ-resource is presented.Theorem 16.
Let(N,M0) be a US3PR. A k-step look-ahead optimal DAP satisfies k=max⁡n+2,p+2.Proof.
Consider a US3PR with a ξ-resource shared by two RT-circuits: Θ1 and Θ2, where r∈Θ1∩Θ2, and M0(r)=1. Let m,n,p, and q represent the numbers of monoploid HR-circuits associated with the ξ-resource. According to Lemmas 14 and 15, in the Θ1 part, the resource transmission process will generate n+1 pseudo-safe markings. From the steps look-ahead point of view, it takes n+2 steps from a border legal marking to a marking in DZ∖DZ∗ which unmarks a strict minimal siphon. For the Θ2 part, similarly, p+1 states in DZ∗ will lead to a (p+2)-step look-ahead procedure. Throughout the whole system and considering the worst case, max⁡n+2,p+2 steps will be necessary to look ahead in an optimal DAP.If we want to find an S3PR with a four-step look-ahead DAP, that is, k=4, by Theorem 16, k=max⁡n+2,p+2=4. There are two situations.(1)
n+2=4,p+2≤4, that is, n=2,p≤2.(2)
n+2≤4,p+2=4, that is, n≤2,p=2.Theoretically speaking, sincem and q HR-circuits make no difference to the consequence, there are innumerable structures that can be acceptable. We choose the first case. Let m=4, n=2; p=0, q=0. According to Figure 8, we can generate the structure in Figure 13, where the initial marking of the net is set as M0=p13+p14+p15+p16+p17+p18+p19+p20+p21. It needs four steps look-ahead, as seen in Figure 14. By introducing the k-step look-ahead-based structure, it is easy to find a k-step look-ahead S3PR model. Indeed, this structure is obviously not unique.Figure 13
An example of a four-step look-ahead structure derived from Figure8.Figure 14
Computation result in Figure13.


## 4.2. US3PR Model

The model considered in this subsection is not restricted to a US3PR that is an LS3PR. Figure 15 shows a typical S3PR model with a ξ-resource. In this model, resource places p11, p12, p14, and p15 are shared by the process t1p1t2p2t3p3t4p4t5. Let us suppose a new initial marking M0′ with M0′(p11)–M0′(p15)= 1. The related result is demonstrated in Figure 16. To exactly explore the relationship between the steps and the net structure, the set of DZ∗ is divided into a number of subsets that are disjoint.Figure 15
A typical S3PR model.Figure 16
Simulation result of the net in Figure15.Definition 17.
Given an US3PR (N,M0), let DZ1∗,DZ2∗,…,DZh∗ be a partition of DZ∗, that is, DZ∗=⋃j=1hDZj∗ and ∀i,j∈1,2,…,hi≠j, DZi∗∩DZj∗=∅. DZi∗ is said to be a critical subset of first-met markings in DZ∗ if the subgraph derived from DZi∗ in the reachability graph of (N,M0) is connected and any node in DZi∗ and any node in DZj∗(i≠j) are not connected.Definition 18.
Given a Petri net(N,M0), a critical group of states, or simply group, derived by DZi∗, denoted as g(DZi∗), contains DZi∗ and their father nodes in LZ and their leaf nodes in DZ, that is, g(DZi∗)=DZi∗∪M∣M∈LZ∗,∃t∈T,∃M′∈DZ∗,MtM′∪M∣M∈DZ∖DZ∗,∃M′∈DZ∗,M′tM.From Figure16, there are two groups in the reachability graph. As it shows, each group contains two states belonging to DZ∗. That is, each of them contains a three-step look-ahead procedure; that is, it needs three steps to look ahead. As shown in Table 1, M0(p11) and M0(p15) remain unchanged, as being one, since they do not affect the steps to look ahead in an optimal DAP. To ensure that the system contains a ξ-resource, we set M0p14=1. By changing M0p12 and M0p13, some laws can be identified. Through this table, it is clear that a three-step look-ahead method is always acceptable for the net in Figure 15. On the other hand, M0p13 makes no difference on the steps look-ahead and the number of groups for three-step look-ahead procedures. Finally, it is easy to recognize that M0p12 is related to the number of groups.Table 1
Simulation results of Figure14.
M
0
(
p
12
)
1
1
1
1
1
2
2
2
2
2
3
3
3
4
4
5
6
10
15
20
30
40
50
75
100
M
0
(
p
13
)
1
2
3
4
5
1
2
3
4
5
1
2
3
1
2
3
1
5
10
15
1
2
15
20
25
M
0
(
p
14
)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Steps
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
Number of groups
2
2
2
2
2
3
3
3
3
3
4
4
4
5
5
6
7
11
16
21
31
41
51
76
101Compared with an LS3PR, the appearance of such multiple groups stems from multiple processes in a system. There should exist some relation between the number of groups and that of processes, which is to be explored further. The obtained results are also in accord with the condition of the k-step look-ahead model; that is, it only relates to n and q. In this model, obviously we have n=1 and q=0. According to k=max⁡n+2,p+2, the steps that are needed to look ahead are exactly three. Theorem 19 presents the step look-ahead law based on this kind of type.Theorem 19.
Let(N,M0) be a US3PR. r and t represent the numbers of the HR-circuits as shown in Figure 17. A k-step look-ahead optimal DAP satisfies k=max⁡s+2,t+2.Figure 17
Ak-step look-ahead S3PR model.Proof.
It is similar to the proof of Theorem16.Note thats and t determine the number of steps look-ahead. However, because of the presence of the extra processes in a unitary S3PR, the resource transmitting procedure in holder places and resource places will be enlarged. Therefore, in this kind of model, the steps look-ahead may not be only one. It depends on the number of the extra processes in the model and the tokens distribution of the resource places.


## 5. Conclusion

Based on S3PR models, this paper shows that, in an S3PR with a ξ-resource, there is a kind of markings that belong to DZ∗. These markings in DZ∗ do not empty the strict minimal siphons of a Petri net but belong to the dead zone. Due to their presence, the one-step look-ahead method is not applicable. By multiple-step look-ahead, the states in DZ∗ can be identified and an optimal DAP with polynomial complexity can be obtained. Then, by introducing aconservation law of the steps look-ahead, it is proved that the steps to look ahead in an optimal DAP merely depend on the structure of the considered net class, which is the inherent nature of the model. Finally, a k-step look-ahead method is presented through the analysis of the considered models. By following the laws, an S3PR structure with a ξ-resource needing k-step to look ahead can be obtained. A significative question is whether these results can be extended to more general cases such as an S3PR model with multiple ξ-resources or more general types of Petri nets.



---

*Source: 8687035-2017-08-21.xml*