# Computationally Improved Optimal Control Methodology for Linear Programming Problems of Flexible Manufacturing Systems

Authors: Yen-Liang Pan; Yi-Sheng Huang; Yi-Shun Weng; Weimin Wu; MuDer Jeng
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Deadlock prevention policies are used to solve the deadlock problems of FMSs. It is well known that the theory of regions is the efficient method for obtaining optimal (i.e., maximally permissive) controllers. All legal and live maximal behaviors of Petri net models can be preserved by using marking/transition-separation instances (MTSIs) or event-state-separation-problem (ESSP) methods. However, they encountered great difficulties in solving all sets of inequalities that is an extremely time consuming problem. Moreover, the number of linear programming problems (LPPs) of legal markings is also exponential with net size when a plant net grows exponentially. This paper proposes a novel methodology to reduce the number of MTSIs/ESSPs and LPPs. In this paper, we used the well-known reduction approach Murata (1989) to simply the construct of system such that the problem of LPPs can then be reduced. Additionally, critical ones of crucial marking/transition-separation instances (COCMTSI) are developed and used in our deadlock prevention policy that allows designers to employ few MTSIs to deal with deadlocks. Experimental results indicate that the computational cost can be reduced. To our knowledge, this deadlock prevention policy is the most efficient policy to obtain maximal permissive behavior of Petri net models than past approaches.


---

## Body

## 1. Introduction

Many deadlock prevention schemes are developed for solving deadlock problem of FMSs based on structural analysis [1]. Particulary, most of them employed the concept of siphons in their deadlock prevention methods [2–9].  The main advantage of siphon control just requires a few control places to rapidly revive the system. Further, Li and Zhou proposed elementary siphon [10] to reduce the problem of redundant minimal siphons. However, whatever how these experts [11–14] make efforts in it, the siphon control algorithm cannot obtain a maximally permissive controlled system.  On the other hand, some pioneers use reachability graph technology to achieve the goal of a live system behavior [11–23].  Among them, the theory of regions [24] can not only obtain an optimal (i.e., maximally permissive states) deadlock prevention controller, but also without confining to a certain class of FMSs.Uzam [16] followed the theory of regions to further define the deadlock zone (DZ) and the deadlock-free zone (DFZ) for preventing deadlocks.  Based on the theory of regions, an optimal controller can be obtained when the concept of DZ and DFZ is used to solve ESSPs.  However, it suffers from many redundant control places problems due to numerous ESSPs.  Ghaffari et al. [20] proposed a unique interpretation of the theory of regions and defined forbidden marking, dangerous marking, legal marking, and the set of MTSI.  Under the method of MTSI, an optimal PN controller synthesis method for FMSs is proposed. Unfortunately, the problem of the redundant control places cannot be entirely avoided in large FMSs.  To solve the problem of state explosion, Uzam [18] uses the reduction technology to improve the previous ones based on the theory of regions.  This technology is also used in this paper to simplify the structure of FMSs.  For reducing the number of MTSIs, Li et al. [25] adopted a combined algorithm based on siphon control method and the theory of regions.  However, it still fails to need to determine all sets of MTSIs in second stage, and its application seems to be limited in S3PR [1] nets.  Wei and Li [26] also proposed a suboptimal deadlock prevention policy using structural analysis and the theory of regions. However, the maximally permissive behavior cannot be obtained once the initial markings of the controlled net are changed.  Uzam and Zhou [11] use a simple iterative skill for removing all markings in the deadlock zone based on the theory of regions. However, the reachability graph must be generated at each iterative stage.  As a result, as indicated by [27], the computational efficiency is lower than the conventional policy [16, 20].It is worthy to notice that Piroddi et al. [28, 29] proposed combined selective siphons and critical markings in a reachability graph algorithm to obtain maximally permissive controllers via iterations. All uncontrolled siphons are needed first to be identified. And then the relation between uncontrolled siphons and critical markings is further located. However, the main drawback is that the reachability graph is still generated at each iterative stage until all critical markings are controlled.  Nevertheless, the policy not only solves the deadlock problem successfully, but also obtains a maximally permissive controller. To our knowledge, the policy is the first deadlock prevention policy to achieve the goal that can obtain maximally permissive controllers for all S3PR models in the existing literature. On the other hand, CMTSI is proposed to enhance the computational efficiency of the conventional MTSI algorithm [12, 14, 30].  The three articles show the CMTSI policy is capable of obtaining an efficient and optimal controller in small S3PR nets.  In this paper, the selective siphon method and reduction technology are merged in our new deadlock prevention policy. The advantage of the proposed method is that the number of two types CMTSI can then be simplified. And LPP is also reduced.The rest of this paper is organized as follows. Section2 presents the basic definitions, properties of PNs, and the theory of regions.  Section 3 then describes the proposed deadlock prevention policy.  Next, Section 4 presents the experimental results. Section 5 gives the comparison results.  Conclusions are made in Section 6.


## 2. Preliminaries [23]

A PN is a 5-tuple,PN=(P,T,F,W,M0), where P is a finite set of places; T is a finite set of transitions, with P∪T≠∅ and P∩T=∅; F⊆(P×T)∪(T×P) is the set of all directed arcs, W:(P×T)∪(T×P)→N is the weight function where N={0,1,2,…} and M0: P→N is the initial marking.  N is said to be ordinary, denoted as (P,T,F), if for all f∈F,W(f)=1. N+(p,t)=W(p,t) is the input function that means the multiplicity of a directed arc from p to t if (p,t)∈F. N-(p,t)=W(t,p) is the output function that means the multiplicity of a directed arc from t to p if (t,p)∈F. The set of input (resp., output) transitions of a place p is denoted by p• (resp., p•). Similarly, the set of input (resp., output) places of a transition t is denoted by t• (resp., t•). A PN structure (P,T,F,W) is denoted by N. A PN with a given initial marking is denoted by (N,M0).  A PN is said to be pure if no places are both input and output places of the same transition. The so-called incidence matrix [N] of a pure PN is defined as [N]=[N]--[N]+. A transition t is said to be enabled at marking M if, for all p∈t•,  M(p)≥W(p,t) or p is marked with at least W(p,t) tokens, as denoted by M[t>. A transition may fire if it is enabled. In an ordinary net, it is enabled if and only if for all p∈t•, M(p)≥1.  Firing t at M gives a new marking M′ such that, for all  p∈P,  M′(p)=M(p)-W(p,t)+W(t,p). It is denoted as M[t>M′]. M indicates the number of tokens in each place, which means the current state of the modeled system.  When marking Mn can be reached from M0 by firing a sequence of transitions σ, this process is denoted by M[σ>Mn] and satisfies the state equationMn=M+[N]σ→. Here, σ→ is a vector of nonnegative integers, called counting vector, and σ→(t) indicates the algebraic sum of all occurrences of t in σ. The set of all reachable markings for a PN given M0 is denoted by R(N,M0). In this paper, we only focus on the reachable markings. The spurious ones are not under consideration. A transition t is said to be liveif for any M∈R(N,M0) there exists a sequence of transitions whose firing leads to M′ that enables t.  A PN is said to be live if all the transitions are live.  Liveness of a PN means that for each marking M∈R(N,M0) reachable from M0 it is finally possible to fire t, for all t∈T through some firing sequence. (N,M0) is said to be reversible if for each marking M∈R(N,M0)M0 is reachable from M.  Thus, in a reversible net it is always possible to go back to initial marking (state) M0.  A marking M′ is said to be a home state if for each marking M∈R(N,M0)M′ is reachable from M.  Reversibility is a special case of the home state property; that is, if the home state M′=M0, then the net is reversible.  A PN contains a deadlockif there is a marking M∈R(N,M0) at which no transition is enabled.  Such a marking is called a dead marking.  Deadlock situations are as a result of inappropriate resource allocation policies or exhaustive use of some or all resources.On the other hand, a conventional MTSI [21]/ESSP [16] is proposed to prevent deadlock PN systems. The two methods concerned about the forbidden state problem for liveness requirements. It is assumed that MF is the set of forbidden markings.  For convenience, we employed its several definitions which are related with our approach as follows.Definition 1.
Let the setML of legal/admissible markings be the maximal set of reachable markings in R(N,M0).
Clearly,ML=R(N,M0)-MF. To solve the control problem, one has to identify the set of MTSI from a legal/admissible marking to a nonadmissible marking.  The additional monitors are used to prevent these transitions from occurring in order to keep the state space of the controlled system in the set of legal markings.Definition 2.
The set of MTSI that the supervisor has to disableΩ={(M,t)∣∃Mt>M′∧  ∈  ML∧M′∉ML}. An optimal controller is the one that ensures the reachability of all markings in ML and that forbids all state transitions in Ω.
Additionally, the theory of regions is proposed for the synthesis of pure nets given a finite transition system [22], which can be adopted to synthesize the liveness-enforcing net supervisor (LENS) for a plant model. Ghaffari et al. [20] give a new interpretation of the theory of regions using net notations and show how to adopt it to synthesize the liveness-enforcing net supervisor for a PN modeled net. This theory is briefly introduced below.
LetT be a set of transitions and G a finite directed graph whose arcs are labeled by transitions in T.  Assume that there exists a node v in G such that there exists a path from it to any node.  The objective of the theory of regions is to find a pure PN  (i.e.,  (N,M0)), having T as its set of transitions and characterized by its incidence matrix [N](p,t) and its initial marking M0, such that its reachability graph is G and the marking of node v is M0.  In the following, M denotes both a reachable marking and its corresponding node in G.Consider any placep of the net (N,M0) we look for. Because (N,M0) is pure, p can be fully characterized by its corresponding incidence vector [N](p,·)Γ→M, where Γ→M is the counting vector of path ΓM.  For any transition t that is enabled at M, that is, t is the label of an outgoing arc of the node M in G,
(1)M′(p)=M(p)+[N](p,·)Γ→M,∀(M,M′)∈G,andM[t>M′.
Consider now any oriented cycle γ of a reachability graph.  Applying the state equation to a node in γ and summing them up give the following cycle equation:
(2)∑t∈T[N](p,t)γ→(t)=0,∀γ∈C,
where γ is an oriented cycle of G,γ⃑(t) is a T-vector, γ(t) denotes the algebraic sum of all occurrences of t in γ, and C is the set of oriented cycles of G.According to the definition ofG, there exists an oriented path ΓM from M0 to M. Applying (1) along the path leads to M(p)=M0(p)+[N](p,·)Γ→M. There are several paths from M0 to M.  Under the cycle equations, the product [N](p,·)Γ→M is the same for all these paths.  As a result, ΓM can be arbitrarily chosen.  The reachability of any marking M in G implies that
(3)M(p)=M0(p)+[N](p,·)Γ→M≥0,∀M∈G.
The above equation is called the reachability condition.  Notably, (3) is necessary but not sufficient. Here spurious markings may be generated. However, their consideration is beyond this study.It is now clear that the cycle equations and reachability conditions hold for any placep.  For each pair (M,t) such that M is a reachable marking of G and t is a transition not enabled at M, t should be prevented from happening by some place p.  Since the net is pure, t is prevented from happening at M by a place p if and only if
(4)M0(p)+[N](p,·)Γ→M+[N](p,t)≤-1.
The above is called the event separation condition of (M,t).  The set of all possible pairs (M,t) where M is a reachable marking and t is not enabled at M is called the set of event separation instances or marking/transitions-separation instance (MTSI). To solve the control problem, the set of MTSI needed to be identified firstly. The corresponding control places can then be located to prevent transitions of the controlled system from firing in order to keep the state space of legal markings only.Accordingly, every markingM in the legal behavior of the reachability graph must still be reachable after the control place (pc) is added. It implies that pc must satisfy reachability condition of the legal behavior, cycle equations, and the event separation condition of (M,t). The three conditions are listed below:
(5)M(pc)=M0(pc)+[N](pc,·)Γ→M≥0,∀M∈ML,∑t∈T[N](pc,t)γ→(t)=0,∀γ∈C,M0(pc)+[N](pc,·)Γ→M+[N](pc,t)≤-1.
Equation (5) is used to determine the additional control place pc.  Notably, different MTSIs may obtain the same solutions.  As a result, the number of control places will be much smaller than the sets of MTSIs. In the following section, a more efficient method to reduce the number of MTSIs will be introduced.  For convenience, our proposed new deadlock prevention method will follow the above interpretation of the theory of regions.


## 3. Optimal Control Methodology for Linear Programming Problems

We suppose that a deadlock-prone PN model contains at least a dead marking in its reachability graph at which no transitions are enabled.  Therefore, the dead markingMD is defined formally as follows.Definition 3.
Thedead markingsMD={M∈R(N,M0)∣ at M, no transitions are enabled}.Definition 4.
A zone consisting of all dead markings is calleddead zone, denoted by ZD.
Once reachable markings enter the dead zone, the system is deadlock. If there is no marking in the dead zone for a reachability graph, the system is called a live one. Therefore, the final goal of this research is to control a deadlock-prone system and then it can become live. For this purpose, the markings in a deadlocked system must be identified. All markings of a reachability graph can be divided into three groups: legal markings (ML), quasi-dead markings (MQ), and dead markings (MD).Definition 5.
Thequasi-dead markingsMQ={M∈R(N,M0)∣M must eventually evolve to a dead one regardless of transition firing sequences}.Definition 6.
A zone consisting of all quasi-dead markings is called thequasi-dead zone, denoted by ZQ.
Markings except quasi-dead markings and dead markings are legal ones. Once a legal marking is enforced into the quasi-dead zone, the net will eventually become deadlock.Definition 7.
A zone consisting of all legal markings is calledlegal zone, that is, ZL=R(N,M0)-ZD-ZQ.
Ramadge and Wonham [31] have demonstrated that a system has maximally permissive behavior if ZL exists and the system behavior cannot be led outside ZL. Therefore, all quasi-dead and dead markings are needed to remove and all legal markings are reverse in the reachability graph if one wants to obtain the maximally permissive behavior.In our previous work [12], we first proposed the concept of CMTSI. Only one type CMTSI is identified to replace with all MTSIs.  And also it can make the dead-prone PN model alive. In [14, 30], two types of CMTSIs are introduced.  For detailed information please refer to [14, 30]; this work just shows the main definitions.Definition 8.
Type I CMTSI:Ω′={(M,t)∣M∈ML,  t∈T, and ∃M′∈MD, such that M[t>M′]}. Denote the set of all the dead markings related to Ω′ as MD′, that is, MD′={M′∈MD∣∃(M,t)∈Ω′ such that  M[t>M′]}.Definition 9.
σ
k is defined as a transition firing sequence starting in a quasi-dead marking (MQ) and ending in a deadlock marking in MD, where i=|σk| is the number of transitions in σk, called its length. Denote a firing sequence with the shortest length (i.e., smallest i) from any quasi-dead marking to M′ as σ*(M′) given M′∈MD-MD′.Definition 10.
Type II CMTSI:Ω′′={(M,t)∣M∈ML,t∈T,∃M′∈MQ,M′∈MD, and a firing sequence σ=σ*(M′′) from M′ to M′′ such that  M[t>M′]  and  M′[σ>M′′]}. The set of dead markings associated with type II CMTSI is denoted as MD′′, called type II deadlocks. MD′′={M′′∈MD∣∃(M,t)∈Ω′′,  M′∈MQ, and a firing sequence σ from M′ to M′′ such that M[t>M′] and σ=σ*(M′′)}.Definition 11.
A dead marking is always with its corresponding CMTSI. As a result, the corresponding CMTSI is of either type I or II. Note that type I may be regarded as a special case of type II CMTSI by definingσ*=0 (no need to enter ZQ but directly to ZD), and type I CMTSI should be processed first.In [33], the selective siphon with critical marking control approach [28] is merged in the new deadlock prevention. Based on [33], we propose critical ones of crucial marking/transition-separation instance (COCMTSI) that allows us to locate one COCMTSI from CMTSI. Once the COCMTSIs are controlled, all the paths from legal markings to critical markings are accordingly forbidden.  In other words, one selective siphon can control two (or above two) critical markings if those critical markings are in the same minimal siphon.  In the following, uncontrolled siphons, critical markings, and selected siphons are defined.Definition 12.
Uncontrolled siphons and critical markings [28].
LetΠ={S1,…,Sn} the set of minimal siphons of PN.(i)
The setΠu={Sj∈Π∣ESj≠∅}, where ESj={M∈R(N,M0)∣λSjTM=0}, is the set of uncontrolled siphons.(ii)
The setΠM={Sj∈Πu∣λSjTM=0} denotes the set of empty siphons in the marking M.(iii)
For anyΠ*⊆Πu,EΠ*=∪Sj∈Π*ESj is the set of markings where at least one siphon in Π* is empty.(iv)
The setEΠu denotes the set of critical markings.(v)
A covering set of uncontrolled siphons (CSUS) is a subset of siphons Πc⊆Πu, such that EΠc=EΠu.Definition 13.
The set CMTSI (type I and type II) belong to COCMTSI (WC) once they can be included in same selective siphons.Definition 14.
The set CMTSI (type I and type II) belongs to COCMTSI (Ωc) once they can be included in the same selective siphons.
For example, based on Table1, there are five CMTSIs needed to process. Further, it is obvious that CMTSI a and CMTSI b are included in selective siphon I. Similarly, CMTSI c and CMTSI d are included in selective siphon II. According to Definition 14, CMTSI a and CMTSI b can be considered as the same set of the COCMTSI x. Similarly, CMTSI c and CMTSI d are the same set of the COCMTSI y.  Therefore, one can just choose anyone CMTSI (i.e., CMTSI a or CMTSI b) to calculate since both belong to COCMTSI x. As a result, only three CMTSIs needed to process if the COCMTSI algorithm is used.Table 1
The relations between selective siphons and CMTSIs.
CMTSIa
CMTSIb
CMTSIc
CMTSId
CMTSIe
Selective siphon I (S1)
⊚
⊚
Selective siphon II (S2)
⊚
⊚
Selective siphon III (S3)
⊚
COCMTSIx
COCMTSIy
COCMTSIzDefinition 15.
One CMTSI which is not included in any selective siphon needs to be processed.
Petri nets reduction approach is a well-known method to derive the properties of a complex PN model, while preserving the concerned properties, such as boundedness, liveness, and reversibility [31]. By simplifying the PN structure, it is an efficient analysis way to derive the properties of a complex PN model. Here, six simple reduction rules are used. They are (a) fusion of series places; (b) fusion of series transitions; (c) fusion of parallel places; (d) fusion of parallel transitions; and (e) elimination of self-loop places; (f) Elimination of self-loop transitions. Besides, if we assume that (N,M0) is an original PN, and (N′,M0′) is the simplified PN then (N′,M0′) is live, safe, and bounded if and only if (N,M0) is live, safe, and bounded.


## 4. Our New Deadlock Prevention Algorithm

For convenience, we employ a flowchart (i.e., shown in Figure1) to present our new deadlock prevention algorithm that consists of six stages. The detailed steps are as follows. First of all, the reduction technology is used to simply the construct of Petri net system. Second, we have to locate all reachable markings. Then, we need to identify CMTSIs. Next, we have to check all dead/quasi-dead markings of CMTSIs whether they are included in selective siphons or not. It is worthy to notice that if CMTSIs are included in the same siphons, they are called COCMTSIs. Additionally, we can choose any CMTSI to be processed if the CMTSI belongs to COCMTSIs.  Finally, control places can be obtained to control the deadlock problem.Figure 1
The flowchart of our deadlock prevention policy.Obviously, the reduction approach is able to reduce the number of LPPs. According to the conventional theory of regions, every MTSI is needed to process with all reachability condition equations and cycle equations. Hence, COCMTSIs can reduce the number of LPPs. It means that less MTSI needs less LPPs to be handled. Since COCMTSI(ΩC)⊆(Ω′∪Ω′′)⊆Ω, the number of LPPs will be reduced.  Based on the above discussion, we can infer that our proposed deadlock prevention policy is more efficient than the relative methods in [12, 14, 16, 20]. For instance, a classical FMS (i.e., shown in Figure 2) which is taken from [32] is employed as an example. In this case, it is with 16 dead markings, 61 quasi-dead markings, and 205 legal markings.  One can realize that there are 205 LPPs needed to process since 205 legal markings will generate 205 reachability condition equations.  Our new deadlock prevention policy will be introduced as follows.Figure 2
A classical Petri net-based S3PR model [32].In reduction approach stage, one can then obtain the reduced model shown in Figure3 due to fusion of series transitions rule.Figure 3
The reduced model of Figure2.In reachability graph stage, one can locate 176 reachable markings (i.e.,M1-M176) by PNTOOL [34]. Then 16 dead markings (i.e., M80,  M93,  M125, M130,  M134,  M137,  M152, M153,  M154,  M156,  M163,  M170,  M171,  M172,  M174, and M176) can be identified.  Additionally, according to Definition 3, 41 quasi-dead markings (i.e., M26, M35,  M42,  M52, M59, M68,  M72, M75,  M79,  M85,  M89, M96,  M99, M100, M106, M107, M111, M116, M118, M119, M120, M124, M126, M127,  M136, M138, M141, M142, M143, M146, M150, M151, M155, M159, M162, M164, M166, M168, M169, M173, and M175) can be obtained.  For convenience, the detailed information of the dead markings and the quasi-dead markings is listed in Tables 2 and 3.Table 2
The detailed information of dead markings.
Marking number
Information of marking[p1, p2, p3, p4, p5, p6, p8, p9, p10, p11, p12, p14, p15, p16, p17, p18, p19]
Marking number
Information of marking[p1, p2, p3, p4, p5, p6, p8, p9, p10, p11, p12, p14, p15, p16, p17, p18, p19]
M
80
[3, 1, 1, 1, 0, 0, 4, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0]
M
93
[5, 0, 1, 0, 0, 0, 3, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0]
M
125
[4, 0, 0, 0, 1, 1, 4, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
M
130
[4, 0, 1, 1, 0, 0, 3, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0]
M
134
[4, 1, 0, 1, 0, 0, 3, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0]
M
137
[6, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0]
M
152
[2, 1, 1, 1, 0, 1, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
M
153
[3, 0, 1, 0, 1, 1, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0]
M
154
[3, 0, 0, 1, 1, 1, 4, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]
M
156
[4, 0, 1, 0, 0, 1, 3, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0]
M
163
[5, 0, 0, 1, 0, 0, 2, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0]
M
170
[3, 0, 1, 1, 0, 1, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
M
171
[3, 1, 0, 1, 0, 1, 3, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]
M
172
[4, 0, 0, 0, 1, 1, 3, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0]
M
174
[5, 0, 0, 0, 0, 1, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]
M
176
[4, 0, 0, 1, 0, 1, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]Table 3
The detailed information of quasi-dead markings.
Marking number
Information of marking[p1, p2, p3, p4, p5, p6, p8, p9, p10, p11, p12, p14, p15, p16, p17, p18, p19]
Marking number
Information of marking[p1, p2, p3, p4, p5, p6, p8, p9, p10, p11, p12, p14, p15, p16, p17, p18, p19]
M
26
[3, 1, 1, 1, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1]
M
35
[5, 0, 1, 0, 0, 0, 5, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1]
M
42
[3, 1, 1, 1, 0, 0, 5, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0]
M
52
[5, 0, 1, 0, 0, 0, 4, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0]
M
59
[3, 1, 1, 1, 0, 0, 5, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
M
68
[4, 0, 1, 1, 0, 0, 5, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1]
M
72
[5, 0, 1, 0, 0, 0, 4, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1]
M
75
[4, 1, 0, 1, 0, 0, 5, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1]
M
79
[6, 0, 0, 0, 0, 0, 4, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1]
M
85
[4, 0, 1, 0, 1, 0, 4, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0]
M
89
[4, 0, 1, 1, 0, 0, 4, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0]
M
96
[4, 1, 0, 1, 0, 0, 4, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0]
M
99
[6, 0, 0, 0, 0, 0, 3, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0]
M
100
[2, 1, 1, 1, 0, 1, 6, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
M
106
[4, 0, 1, 0, 0, 1, 4, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0]
M
107
[4, 0, 1, 0, 0, 1, 5, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1]
M
111
[4, 0, 1, 1, 0, 0, 4, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1]
M
116
[4, 1, 0, 1, 0, 0, 4, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1]
M
118
[5, 0, 0, 1, 0, 0, 4, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1]
M
119
[6, 0, 0, 0, 0, 0, 3, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1]
M
120
[2, 1, 1, 1, 0, 1, 5, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]
M
124
[3, 1, 1, 0, 0, 1, 4, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0]
M
126
[4, 0, 1, 0, 0, 1, 4, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0]
M
127
[3, 1, 0, 1, 0, 1, 4, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]
M
136
[5, 0, 0, 1, 0, 0, 3, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0]
M
138
[2, 1, 1, 1, 0, 1, 5, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
M
141
[3, 0, 1, 1, 0, 1, 4, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0]
M
142
[3, 0, 1, 1, 0, 1, 5, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1]
M
143
[4, 0, 1, 0, 0, 1, 4, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1]
M
146
[3, 1, 0, 1, 0, 1, 5, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1]
M
150
[5, 0, 0, 0, 0, 1, 4, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
M
151
[5, 0, 0, 1, 0, 0, 3, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1]
M
155
[3, 0, 1, 1, 0, 1, 4, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0]
M
159
[3, 1, 0, 1, 0, 1, 4, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0]
M
162
[5, 0, 0, 0, 0, 1, 3, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0]
M
164
[3, 0, 1, 1, 0, 1, 4, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
M
166
[3, 1, 0, 1, 0, 1, 4, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]
M
168
[4, 0, 0, 1, 0, 1, 4, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1]
M
169
[5, 0, 0, 0, 0, 1, 3, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1]
M
173
[4, 0, 0, 1, 0, 1, 3, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0]
M
175
[4, 0, 0, 1, 0, 1, 3, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]In identification CMTSI stage, according to Definitions8 and 10, one can identify all CMTSIs from MTSIs. The detailed information of identifying process please refers to [14, 30]. Table 4 shows all MTSIs.Table 4
The information of all MTSIs.
Marking number
MTSI number
Marking number
MTSI number
Marking number
MTSI number
M
26
{
M
16, t1}
M
35
{
M
20, t11}
M
42
{
M
26, t9}
M
52
{
M
34, t11}
M
59
{
M
42, t10}
M
59
{
M
47, t1}
M
68
{
M
47, t11}
M
72
{
M
52, t10}
M
75
{
M
55, t1}
M
79
{
M
57, t11}
M
80
{
M
67, t1}
M
85
{
M
63, t9}
M
85
{
M
67, t4}
M
89
{
M
67, t11}
M
96
{
M
74, t1}
M
99
{
M
77, t11}
M
100
{
M
81, t1}
M
106
{
M
84, t9}
M
106
{
M
90, t2}
M
107
{
M
84, t11}
M
116
{
M
95, t1}
M
118
{
M
95, t11}
M
120
{
M
103, t1}
M
124
{
M
104, t9}
M
125
{
M
105, t9}
M
125
{
M
109, t4}
M
127
{
M
108, t9}
M
127
{
M
109, t1}
M
134
{
M
115, t1}
M
136
{
M
115, t11}
M
138
{
M
123, t1}
M
141
{
M
123, t9}
M
142
{
M
123, t11}
M
146
{
M
129, t1}
M
150
{
M
132, t11}
M
153
{
M
139, t9}
M
154
{
M
140, t9}
M
159
{
M
145, t1}
M
162
{
M
148, t11}
M
166
{
M
158, t1}
M
168
{
M
158, t11}
M
171
{
M
165,  t1}
M
172
{
M
165,  t4}
M
172
{
M
167, t9}
M
173
{
M
165, t11}Hence, the number of legal markings(i.e.,176-(16+41)=119) can then be determined. Additionally, types I and II CMTSIs can be obtained that are listed in Tables 5 and 6.Table 5
The information of type I CMTSIs.
Dead marking number
MTSI number
Dead marking number
MTSI number
Dead marking number
MTSI number
M
80
{
M
67, t1}
M
125
{
M
105, t9}
M
125
{
M
109, t4}
M
134
{
M
115, t1}
M
153
{
M
139, t9}
M
154
{
M
140, t9}
M
171
{
M
165, t1}
M
172
{
M
165, t4}
M
172
{
M
167, t9}Table 6
The information of type II CMTSIs.
Dead marking number
Quasi-dead marking number
MTSI number
Dead marking number
Quasi-dead marking number
MTSI number
M
93
M
52
{
M
34, t11}
M
130
M
89
{
M
64, t11}
M
137
M
99
{
M
77, t11}
M
152
M
138
{
M
123, t1}
M
152
M
141
{
M
123, t9}
M
156
M
106
{
M
84, t9}
M
156
M
106
{
M
90, t2}
M
156
M
107
{
M
84, t11}
M
163
M
136
{
M
115, t11}
M
170
M
141
{
M
123, t9}
M
170
M
142
{
M
123, t11}
M
174
M
162
{
M
148, t11}
M
176
M
173
{
M
165, t11}In siphon classification stage, according to the definition in [28], there are three sets of selective siphons S1={p2,p5,p15,p18},  S2={p5,p14,p15,p18}, and S3={p2,p11,p16,p17,p18,p19} in this example. Please note that there are six sets of minimal siphons in it initially.In identification COCMTSI stage, all CMTSIs need to identify whether CMTSIs belong to COCMTSIs or not. Therefore, we just need to identify the markingsM80, M125, M134, M153, M154, M171, and M172 (i.e., type I CMTSI) and M52, M89,  M99,  M138, M141, M106, M107, M136, M142, M162, and M173 (i.e., type II CMTSI) if they are included in S1, S2, and S3 or not. After this stage, the identified COCMTSIs are listed in Tables 7 and 8. From Tables 7 and 8, it is obvious that M52,  M89, M99, M107, M136, M142, M162, and M173 are included in S1; M80, M134, M171, and M152 are included in S2; and M125, M153, M154,  and M172 are included in S3. In addition, the other two markings M141 and M106 are not included in any selective siphons. Therefore, M52,  M89, M99, M107, M136, M142, M162, and M173 belong to same COCMTSI group. Similarly, M80, M134, M171, and M152 belong to the same COCMTSI group, and M125, M153, M154, and M172 belong to the same COCMTSI group. Just one CMTSI is picked up from same COCMTSI group. Conveniently, the type I CMTSI from the three sets of COCMTSI. They are {M34,t11}, {M67,t1}, and {M105,t9}, shown in Table 9. Besides, the two sets of CMTSI {M123,t9} and {M84,t9} are necessarily considered. In sum, there are five sets of COCMTSIs needed to be calculated.Table 7
The relation between type I CMTSIs and selective siphons.
Dead marking number
MTSI number
Critical marking
Selective siphon
M
80
{
M
67, t1}
M
80
S
2
M
125
{
M
105, t9}
M
125
S
3
M
134
{
M
115, t1}
M
134
S
2
M
153
{
M
139, t9}
M
153
S
3
M
154
{
M
140, t9}
M
154
S
3
M
171
{
M
165, t1}
M
171
S
2
M
172
{
M
165, t4}
M
172
S
3Table 8
The relation between type II CMTSIs and selective siphons.
Dead marking number
MTSI number
Critical marking
Selective siphon
M
93
{
M
34,  t11}
M
52
S
1
M
130
{
M
64,  t11}
M
89
S
1
M
137
{
M
77,  t11}
M
99
S
1
M
152
{
M
123,  t1}
M
138
S
2
M
152
{
M
123,  t9}
M
141
No match
M
156
{
M
84,  t9}
M
106
No match
M
156
{
M
84,  t11}
M
107
S
1
M
163
{
M
115,  t11}
M
136
S
1
M
170
{
M
123,  t11}
M
142
S
1
M
174
{
M
148,  t11}
M
162
S
1
M
176
{
M
165,  t11}
M
173
S
1Table 9
Total COCMTSIs.
Dead marking number
MTSI number
Critical marking
Selective siphon
M
93
{
M
34, t11}
M
52
S
1
M
80
{
M
67, t1}
M
80
S
2
M
125
{
M
105, t9}
M
125
S
3
M
152
{
M
123, t9}
M
141
No match
M
156
{
M
84, t9}
M
106
No matchIn control places stage, six control places can then be obtained by using the theory of regions. The detailed information of the six control places is listed in Table10.Table 10
The additional control places in this example.
Control places number
M
0(Cpi)
●(Cpi)
(Cpi)●
Information of control places
[
M
0
,
t
1
,
t
2
,
t
3
,
t
4
,
t
5
,
t
6
,
t
7
,
t
8
,
t
9
,
t
10
,
t
11
,
t
12
,
t
1
3
,
t
1
4
]
C
1
1
t
5,  t13
t
4,  t11
[1,  0,  0,  0, −1,  1,  0,  0,  0,  0,  0, −1,  0,  1,  0]
C
2
2
t
6,  t13
t
1,  t11
[2, −1,  0,  0,  0,  0,  1,  0,  0,  0,  0, −1,  0,  1,  0]
C
3
3
t
5,  t7,  t11
t
4,  t6,  t9
[3,  0,  0,  0, −1,  1, −1,  1,  0, −1,  0,  1,  0,  0,  0]
C
4
3
t
6,  t11
t
3,  t4,  t9
[3,  0,  0, −1, −1,  0,  1,  0,  0, −1,  0,  1,  0,  0,  0]
C
5
3
t
7,  t11
t
3,  t5,  t9
[3,  0,  0, −1,  0, −1,  0,  1,  0, −1,  0,  1,  0,  0,  0]
C
6
4
t
7,  t11
t
1,  t9
[4, −1,  0,  0,  0,  0,  0,  1,  0, −1,  0,  1,  0,  0,  0]


## 5. Comparison with Previous Methods

This section compares this work with the past deadlock prevention policies [13, 14, 16, 18, 22, 33].Obviously, based on Table11, this work presents a computationally improved optimal control algorithm among the existing literature.  The reason is that five sets MTSIs and 119 LPPs are needed to be handled by using our new policy.Table 11
Comparison of the controlled example.
Policy by
Number monitors
Reachable markings optimal?
Number MTSI
Number LPP
[16]
8
205
Yes
59
205
[18]
8
205
Yes
59
205
[14]
6
205
Yes
18
205
[13]
6
205
Yes
18
119
[33]
6
205
Yes
5
205
This Paper
6
205
Yes
5
119


## 6. Conclusion

Linear programming is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Our proposed policy can be implemented for simplifying the number of LPPs for solving deadlock prevention for FMSs.  The underlying notion of the conventional work is that many MTSIs and LPPs must be solved to prevent legal markings from entering the illegal zone in the original PN model. For this purpose, one must generate all MTSIs and LPPs in a reachability graph such that they need to pay for the high computation cost.  However, this work proposed an efficient way which used CMTSIs, the reduction technology, and COCMT to reduce the computation cost.  The proposed method can reduce numerous MTSIs and LPPs such that only a few CMTSIs and LPPs are required in this new deadlock prevention policy. Based on the experimental results, our new policy is more efficient than the existing optimal policies as mentioned above.  Additionally, our control policy can obtain simplified controlled Petri nets because less control places are needed and also the controlled nets are ordinary.In the future work, the existing literature [35–37] which first investigates the deadlock resolution in the paradigm of Petri nets allowing assembly operations, multiple-type and multiple-quantity resource acquisition, and production ratio among jobs maybe can be considered in our future work.



---

*Source: 294835-2013-06-19.xml*