Sage Journals: Discover world-class research

Abstract

After our researches on the effect of a non-sharing resource in a kth order which is the concept of customization manufacturing, in this article we extend the research on the closed-form solution of control-related states to the so-called A-net which has one top non-sharing circle subnet connected to the idle place of left process in a deficient kth order system and is the fundamental model of different productions sharing the same common parts in manufacturing. The formulas just are depended on the parameter k and states’ function of top non-sharing circle subnet for a subclass of nets with k sharing resources. By combining the concept of the partial deadlock avoidance/prevention policy, the moment to launch resource (controller) allocation based on the current state, and the construction of closed-form solution for deficient kth order system, it can realize the concept of dynamic non-sharing processes’ allocation.

Keywords

Control systems discrete event systems flexible manufacturing systems Petri nets

Introduction

Petri nets (PNs) have been used for modeling and analyzing concurrent systems such as flexible manufacturing system (FMS) or resource allocation system (RAS).^1–10 The net behavior depends not only on the graphical structure but also on the initial marking of the net. Therefore, they cannot be determined by static analysis such as dependency analysis; rather, they can be obtained with reachability analysis.^11–16 It has been shown that the complexity of the reachability analysis of the PNs is exponential.¹⁵

When using the Integrated Net Analyzer (INA)¹⁷ as reachability analysis tools, there are some potential risks in large model systems: the first is the time-consuming risk as it may take 1 month to complete the reachability analysis; the second is validating the input net structure data by a human; it may take a long time to waiting an error result while the input net structure is wrong; the third is non-significant error due to the fact that presently INA cannot detect the so-called livelock states as shown in section “Computation of CRSs of an ordinary A-net”; the information of reachability analysis will become not valuable.

The deadlock avoidance/prevention policy for PNs presently is to find critic first-met bad markings (FBMs) for maximally permissive control purpose which is the policy based on the net structure.^18–23 The structural analysis based deadlock prevention has been extensively studied by researchers, in which siphon computation and control play an essential role.^24–30 However, current advanced approaches such as those in Chen et al.³¹ produce maximally permissive supervisors while not being able to synthesize large controllers since reachability analysis of the PN must be employed; Chen et al.²⁰ applied the methodology of interval inhibitor arcs to optimal supervisory control under resources containing multi-token circumstance while suffering from the exponential increment state explosion problem. One solution is to apply mathematics to solve the reachability-related problem of PN in terms of closed-form solutions. As a result, an infinitely large system can be handled with ease.

To efficiently break the ever exponential time plight of getting control states’ information into reasonable waiting time, Chao³² applied the concept of complete reachability graph and graph theory to split the reachability graph of the control net into reachable, live, forbidden, deadlock, non-reachable, and non-reachable + empty-siphon states (below we call all different types of states as control-related states (CRSs), described in section “Methodology of closed-form solution of kth order system”). Enumerating the tokens’ distribution and applying combinatorial mathematics, Chao³² pioneered the very first closed-form solution of the number of CRSs for kth order system (defined in Definition 1). This is the first step that allows the exponential computation time for particular and very large PNs to be reduced into intra-seconds. We have also progressed one step further to analyze the effect of non-sharing resources of kth order and k-net systems based on the token number of idle place in each process being equal to the number of resource places in the associated process^33–37 and proposed the “proof by model” methodology to accelerate the construction of the closed-form formula for PNs.^36,37

One of contributions of the closed-form solution of PN is that the solution can enhance the capability of dynamically modeling large real-time systems. Examples of application are the concept of moment to launch resource (MLR) (controller) allocation and the deadlock avoidance algorithm introduced below.

On the research of the deadlock prevention policy topic, Chao¹⁸ showed that in a kth order system, it needs additional 10 controllers; Li et al.²⁸ showed that in a kth order–like system where k = 3 and initial marking = 4, it needs additional three controllers where the total token number in these additional controllers is 5. The derived problem is, “Should we need a deadlock prevention policy for very (infinitely) large nets?” Meanwhile in the structural analysis method, there is no indicator to show when to allocate the controllers for a partial deadlock prevention policy.

To solve this problem, based on the contributions of our closed-form solution researches listed above, we proposed a partial deadlock avoidance/prevention policy concept for a very large real-time dynamic RAS: the MLR^35,38 for such policy. Presently, the moment can be calibrated by the future deadlock ratio (the number of deadlock states/the number of reachable states) of the current state, which can be derived real-time by closed-form solution, as the indicator. Letting the deadlock thread-holder (DTH) be regarded as a dummy non-sharing waiting resource that can provide one process holding this DTH and wait for the other processes’ work flow, a simple deadlock avoiding algorithm with the transitory maximum number of int(k/2)+1 DTH is proposed in Yu.³⁷ The decision-making of a DTH allocation is based on the maximum value of the reachable states that the DTH can be allocated at different location in a kth order system subnet, which will consume heavy computation time by applying mixed integer programming (MIP) method for a large system due to the non-deterministic polynomial-time hard (NP-hard) characteristic of the MIP problem³⁹ but can be derived by closed-form solution intra-seconds.

However, another symmetry system problem that we propose to solve is the effect of top non-sharing subnet connected to idle place (we call this kind of subnet as top non-sharing circle subnet below (TNCS)) in which structure the position of subnet will affect the token distribution for CRSs caused by some tokens flowing into TNCS but not going through the entire process of kth order system. In other words, with a TNCS connected to a kth order system, we have to construct the closed-form solution of CRSs of a modified kth order system, in which case the number of tokens of idle place is less than the number of places in the belonging process. Here, we call such a modified kth order system as deficient kth order system, defined in Definition 1, and an A-net as a net composed by TNCS and deficient kth order system, defined in Definition 4.

In this article, an example of A-net called a-net adopted from Liu et al.⁴⁰ will be deconstructed and analyzed, followed by the construction of the closed-form solution for the deficient kth order system to compute the number of CRSs of the a-net.

It is important to use A-net as a target net for research: first, it is most suitable and easy understanding net structure to enter the new research domain, especially the concept of states’ classification, the methodology for closed-form solution of kth order system, integration analysis of different net structures, and the generalization of both deficient kth order system and TNCS adopted in this article. Second, the information obtained from the INA tool shows that A-net has no deadlock states, as explained in section “Computation of CRSs of an ordinary A-net.” Hence, we focus on the characteristic of livelock states where the corresponding kth order system is in deadlock states, which can be analyzed by our methodology. Here, we improve the blind spot of INA tools. Third, by combining the concept of the partial deadlock avoidance/prevention policy, MLR, and the construction of closed-form solution for deficient kth order system, it can realize the concept of dynamic non-sharing processes’ allocation.

The rest of the article is organized as follows. Appendix 2 presents the preliminaries about PNs and S³PR, respectively. Section “Methodology of closed-form solution of kth order system” defines deficient kth order system and lists the relative methodology of closed-form solution of kth order system. Section “Computation of CRSs of an ordinary A-net” analyzes and deconstructs an ordinary A-net structure to compute the number of CRSs. In sections “Computation of CRSs of deficient kth order system” and “Computation of CRSs of A-net,” we construct the closed-form solution of CRSs for both deficient kth order system and A-net. Section “Conclusion” concludes the article. Appendix 3 shows how to apply our methodology to construct the closed-form solution for AR⁺-net which is a net structure extended from A-net and contains multi-processes on the right-hand side.

Methodology of closed-form solution of kth order system

Let N be a PN and N^r be the reverse net of N. N^r is the net that all the input arcs in N reverse to output arcs; output arcs reverse to input arcs. Chao³² defined the kth order system (as shown in parts of Definition 1); proposed the concept of complete reachability graph (Figure 5) that lists all states and all paths that any state can be reachable from all states in a kth order system; split the reachability graph of the control net into reachable, live, forbidden, deadlock, non-reachable, and non-reachable+empty-siphon states; and called all the different types of states as CRSs. Table 1 lists all the CRSs of a third-order system. Based on the concept of complete reachability graph, the relationship of the number of different types of CRSs in a kth order system is that the number of non-reachable states is the number of total states − R (R is the number of reachable states); L = R − ϑ where L (resp., ϑ) is the number of live (resp., forbidden) states.

Table 1.

Control-related states of third-order system.

Types of states	Lists of states
Reachable	(0 0 0), (0 0 −1), (0 −1 0), (0 −1 −1), (−1 0 −1), (−1 −1 0), (−1 −1 −1), (−1 0 0), (1 0 0),(0 1 0), (1 1 0), (1 0 1), (0 1 1), (1 1 1), (0 0 1)
Forbidden	(1 0 −1), (1 −1 0), (0 1 −1)
Non-reachable	(0 −1 1), (−1 1 0), (−1 0 1), (−1 −1 1), (−1 1 1)
Deadlock	(1 −1 −1), (1 1 −1)
Non-reachable + empty-siphon	(1 −1 1), (−1 1 −1)

According to graph theory, Chao found and proved Lemma 1, Lemma 2, and Theorem 1; Lemma 3 (resp., Theorem 2) enumerated the number of live (resp., reachable) states of a kth order system; based on the relationship between each type of CRSs, Corollary 2 derived the closed-form formulas of the number of forbidden, non-reachable, and non-reachable+empty-siphon states, respectively.

Here, we first define more general form of the kth order system, called deficient kth order system below. A kth order system is just one of its special cases.

Definition 1

A deficient kth order system is a subclass of S³PR with k resource places r₁, r₂, …, r_k shared between two processes N₁ and N₂:³²

For all r ∈ P_R, M₀(r) = 1.³²

N₁ (resp., N₂) uses r₁ − r_k (resp., r_k − r₁) in that order.³²

1 ≤ M₀(p₀) < k, $M_{0} (p'_{0}) = k$ , where p₀ and $p'_{0}$ are the idle places in processes N₁ and N₂, respectively. When $M_{0} (p_{0}) = M_{0} (p'_{0}) = k$ , the system is called a kth order system.

Holder places of r_j in N₁ and N₂ are denoted as p_j and $p'_{j}$ , respectively.³²

The compound circuit containing r_i, r_i₊₁, …, r_j₋₁, r_j is called (r_i − r_j) region.³²

There are three possibilities for the token initially at r_i to sit at p_i (N₁), $p'_{i}$ , (N₂), and r_i. The corresponding token or r_i state is denoted by 1, −1, and 0, respectively.³²

Examples are shown in Figures 1 –4. Figure 4 is an example of deficient fourth-order system with M₀(p₀) = 3.

Figure 1.

First-order system.

Figure 2.

Second-order system.

Figure 3.

Third-order system.

Figure 4.

Deficient fourth-order system.

Definition 2³²

s = (x₁, x₂, …, x_k), x_i = 1, 0, or −1, i = 1 to k, is a state for a kth order system N, x_i is the token at r_i to sit at p_i (N₁), r_i, or $p'_{i}$ (N₂), respectively. (x_i, x_i₊₁, …, x_q, x_q₊₁), k ≥ i ≥ 1, k ≥ q ≥ i ≥ 1 (embedded in s) is a sub-state of s.

For example, (0 0 0) is the state of third-order system that only resource places r₁, r₂, and r₃ carry tokens.

In Figures 3 and 4, reversing all the input arcs to output arcs, output arcs to input arcs, and inverting the net structures, we can find the reverse net of a (deficient) kth order system is also a (deficient) kth order system but the index of sharing resource is reversed. The reverse state of state (a b c) in third-order system N is (c b a) in its reverse net N^r. This implies that a (deficient) kth order system and its reverse net have the same number of each type of CRSs. In Table 1, the reverse state of the forbidden state (1 0 −1) in N is (−1 0 1) in N^r which is a non-reachable state as shown in Lemma 1. For the third-order system, there are three kinds of unmarked (resp., non-reachable) siphon states: (1 −1 x), (x 1 −1), and (1 0 −1) (resp., (−1 1 x), (x−1 1), and (−1 0 1)), where x = −1, 0, 1. Extending Lemmas 1 and 2, Chao et al.³⁶ found that the reverse state of a live state in a PN N is a live state in its reverse net N^r, and the number of live states in N is equal to the number of live states in N^r which is the main theory of the concept of proof by model.

Lemma 1³²

Any forbidden state in N is non-reachable in N^r.

Lemma 2³²

Any non-reachable state s in N is a forbidden one or a non-reachable one in N^r.

Theorem 1³²

ϑ(k) = ¥(k) − B(k), where ϑ(k), ¥(k), and B(k) are the number of forbidden, non-reachable, and non-reachable+empty-siphon states in a kth order system, respectively.

Lemma 3³²

(1) s is a live state if and only if (iff) s = {y₁, …, y_k)|y_i = −1 or 0}, or s = {(x₁, …, x_k)|x_i = 1 or 0}. (2) The set of live states L_k = {(x₁, …, x_k)|x_i = 1 or 0} ∪ {(y₁, …, y_k)|y_i = −1 or 0} = L_a ∪ L_b. (3) The total number of live states is 2^k+1 − 1.

Theorem 2³²

The possible reachable states are s = {(x₁, x₂, …, x_j, y_j₊₁, …, y_k)|0 ≤ j ≤ k} = {(x₁, …, x_j 1 y_j₊₂, …, y_k)|1 ≤ j ≤ k} ∪ {(y₁, …, y_k)}, where x_i = 1 or 0 (i = 1 to j) and y_p = 0 or −1 (p = j+2 to k) = R_c ∪ R_d.

The total number of reachable states is (k+2)2^(k−1).

Corollary 2³²

(1) The number of forbidden states ϑ(k) = (k − 2)2^(k−1)+1. (2) The number of non-reachable states ¥(k) = 3^k − (k+2)2^(k−1). (3) The number of non-reachable+empty-siphon states B(k) = 3^k − k2^k − 1.

Theorem 3³²

In kth order system, a deadlock state has the pattern: (1₁ 1₂, …, 1_m−1_m+1−1_m+2, …, −1_k), 1 ≤ m < k. The total number of deadlock states D(k) = k − 1.

To sum up, shown below are the total number of each type of CRSs in a kth order system that Chao³² proved.

The total number of states is 3 ^k .

The total number of live states L(k) = 2^k+1 − 1.

The total number of reachable states R(k) =(k+2)2^(k−1).

The number of forbidden states ϑ(k) = R(k) − L(k)= (k − 2)2^(k−1)+1.

The number of non-reachable states ¥(k) = 3^k − R(k) = 3^k − (k + 2)2^(k−1).

The number of non-reachable+empty-siphon states B(k) = ¥(k) − ϑ(k) = 3^k − k2^k − 1.

The total number of deadlock states D(k) = k − 1.

Based on the concept of complete reachability graph (Figure 5) and letting a livelock state be the state that has a directed path to itself state but has no path to initial state, here we extend the definition of forbidden states as the states that have no directed path to the initial state but have a directed path to a deadlock or livelock states. Due to that, the sets of live and forbidden states are two independent sets in a static complete reachability graph, and the number of forbidden states still is ϑ = R − L.

Figure 5.

Complete reachability graph of a third-order system (Figure 3).³²

Computation of CRSs of an ordinary A-net

Compared with Figure 3, Figure 6 is a kth order–like system connecting with the TNCS on the left-side process formed by (t₁, t₁₁, p₁₂, p₁₁, t₁₂, p₁₃, t₁₃, p₁₄, p₀), where the link point is t₁.

Figure 6.

a-net, an ordinary A-net: composed by deficient kth order system and TNCS.⁴⁰

Since there is no empty siphon in TNCS, it will have no deadlock states in this subnet. The tokens in p₁₂ can either fire t₁ or t₁₂, which shows that TNCS and the left process can be concurrently processed. However, there are so-called livelock states where tokens can only flow in the left process TNCS when the kth order–like system contains the deadlock states’ pattern as shown in Theorem 3. When tokens flow into left process TNCS, it will affect the A-net’s state.

We follow the kth order system to compute the number of states. Since p₁₁ and p₁₄ are resources, and p₁₂ is a holder of p₁₁; p₁₃ is a holder of p₁₄. We can focus on tokens’ distribution of resource set of {p₁₁, r₁, r₂, r₃, p₁₄} to simplify presentation and computation of CRSs, where {r₁, r₂, r₃} is a resources’ set of a third-order system; {p₁₁, p₁₄} is a resources’ set of TNCS.

Let z be the token number that has flowed into TNCS. We can use (^g(f(z),i)x₁, x₂, x₃) to denote the state of an A-net, where x₁, x₂, x₃ are r₁, r₂, r₃ states defined in step (6) of Definition 1; f(z) is a sequence function mapping to two-dimensional vector set which is token distribution of {p₁₁, p₁₄}. In this case, f(0) = {(0₁₁, 0₁₄)}; f(1) = {(1₁₁, 0₁₄)), (0₁₁, 1₁₄)}; f(2) = {(1₁₁, 1₁₄)} where 0₁₁ (resp., 0₁₄) is token in p₁₁ (resp., p₁₄); 1₁₁ (resp., 1₁₄) is token in p₁₂ (resp., p₁₃). |f(0)| = 1; |f(1)| = 2; |f(2)| = 1. g(f(z), i) is a function mapping to a TNCS state according to given f(z) and i, 1 < = i < = |f(z)|, i is the sequence of the set of f(z). For example g(f(1), 1) = (1₁₁, 0₁₄); g(f(1), 2) = (0₁₁, 1₁₄); g(f(2), 1) = (1₁₁, 1₁₄).

Up to now, we have constructed the presentation of state of an a-net that not only can show the sequence of state transformation but also provide the important variable, f(z), to compute the number of CRSs.

Computation of CRSs of a-net

Let R(k) (resp., L(k) and D(k)) be the number of reachable (resp., live and deadlock) states of the kth order system; R_D(k, q) (resp., L_D(k, q) and D_D(k, q)) be the number of reachable (resp., live and deadlock) states of deficient kth order system with the token number of left idle place being q; R′(3) (resp., L′(3) and D′(3)) be the number of reachable (resp., forbidden and livelock) states of a-net. We have the below:

The number of reachable states of a-net is R′(3) = |f(0)|R(3)+|f(1)|R_D(3, 2) + |f(2)|R_D(3, 1) = R(3)+2R_D(3, 2) + R_D(3, 1).

The number of live states of a-net is L′(3) = |f(0)|L(3)+|f(1)|L_D(3, 2) + |f(2)|L_D(3, 1) = L(3)+2L_D(3, 2) + L_D(3, 1).

The number of livelock states of a-net is D′(3) = |f(0)|D(3)+|f(1)|D_D(3, 2) + |f(2)|D_D(3, 1) = D(3)+2D_D(3, 2) + D_D(3, 1).

When the token number in TNCS is 0, the number of reachable states in the right third-order system is |f(0)|R(3) since there is only one state (0₁₁, 0₁₄); hence, the number of reachable states is R(3) for the third-order system. The case of |f(1)|R_D(3, 2) is when the token number in TNCS is 1; there being two states (1₁₁, 0₁₄) and (0₁₁, 1₁₄), the number of reachable states is 2R_D(3, 2), in which case the token number of the left idle place is 2. The case of |f(2)|R_D(3, 1) is the token number in TNCS being 2, the token number of left idle place being 1, and the state of TNCS being (1₁₁, 1₁₄) only. The analysis of L′(3) and D′(3) is similar to that for R′(3).

By Theorem 2, R(k) = (k+2)2^(k−1) => R(3) = (3+2)2⁽³⁻¹⁾ = 20.

Extending Theorem 2, R_D(3, 2) = |R_c|+|R_d| = (2⁽³⁻¹⁾+2 × 2⁽³⁻²⁾+2⁽³⁻¹⁾ − 1)+(2³) = 19, where R_c = {(1 y₂y₃)} ∪ {(x₁ 1 y₃)} ∪ {(0₁ 0₂ 1₃), (0₁ 1₂ 1₃), (1₁ 0₂ 1₃)}, where x₁ = 0 or 1, y₂ and y₃ can be 0 or −1. R_d = {(y₁, …, y₃)} y_p = 0 or −1, p = 1 to 3.

R_D(3, 1) = |R_c|+|R_d| = (2⁽³⁻¹⁾+2^(2–1)+2^(1–1))+(2³) = 15, where R_c = {(1 y₂y₃)} ∪ {(0₁ 1 y₃)} ∪ {(0₁ 0₂ 1₃)}, where y₂ and y₃ can be 0 or −1. R_d = {(y₁, …, y₃)} y_p = 0 or −1, p = 1 to 3.

Hence, R′(3) = R(3)+2R_D(3, 2)+R_D(3, 1) = 20+2 × 19+15 = 73.

By Lemma 3, L(k) = 2^k+1 − 1 => L(3) = 2³⁺¹ − 1 = 15.

Extending Lemma 3, L_D(3, 2) = |L_a|+|L_b| = (2⁽³⁻³⁾+2⁽³⁻²⁾+2⁽³⁻¹⁾ − 1)+(2³) = 14, where L_a = {(1₁ 0₂ 0₃)} ∪ {(x₁ 1₂ 0₃)} ∪ {(0₁ 0₂ 1₃), (0₁ 1₂ 1₃), (1₁ 0₂ 1₃)} where x₁ = 1 or 0}, L_b = {(y₁y₂y₃)|y_i = −1 or 0, i = 1 to 3}.

L_D(3, 1) = |L_a|+|L_b| = (2⁽³⁻³⁾+2⁽³⁻²⁾ − 1+1)+(2³) = 11.

Hence, L′(3) = L(3)+2L_D(3, 2)+L_D(3, 1) = 15 + 2 × 14+11 = 54.

By Theorem 3, D(k) = k − 1. Since the total number of deadlock states corresponds to the position m, hence D(3) = D_D(3, 2) = D_D(3, 1) = 2. D′(3) = D(3) + 2D_D(3, 2) + D_D(3, 1) = 8.

The number of forbidden states of a-net is R′(3) − L′(3) = 73 − 54 = 19.

To sum up, shown below are the total number of reachable, live, forbidden and livelock states of a-net.

The total number of reachable states R′(3) = 73.

The total number of live states L′(3) = 54.

The number of forbidden states ϑ′(3) = 19.

The total number of livelock states D′(3) = 8.

Computation of CRSs of deficient kth order system

To extend to general A-net, we have to complete the general formula of R_D(k, q) and L_D(k, q) of the deficient kth order system described in section “Computation of CRSs of an ordinary A-net” first.

The phenomenon of the deficient kth order system in an A-net is when the token number flowing into TNCS is greater than 1 as described in section “Computation of CRSs of an ordinary A-net.”

Construct general formula of R_D(k, q) and L_D(k, q)

Let k_q be a deficient kth order system with q (q ≤ k) tokens in the left idle place; that is, M(p₀) = q and $M (p'_{0}) = k$ .

Definition 3

An impossible state in a deficient kth order system is a reachable state in kth order system, but not a legal state due to the token number in left process being greater than that of the left idle place p₀.

For example, state s = (1₁ 1₂ 1₃ 1₄ 0₅) is a reachable state in fifth-order system but an impossible state in deficient 5₃-th order system, since the token number in left process is 4, greater than 3 which is the token number of the left idle place in deficient 5₃-th order system.

Theorem 4

Let R(k) be the reachable states of a kth order system and R_D(k, q) be the number of reachable states of k_q, a deficient kth order system, then

R_{D} (k, q) = R (k) - \sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i)) (2^{k - l})

where C(l − 1, l − 1 − i) = (l − 1)!/[(l − 1 − i)!i!], is a binomial coefficient.

Proof

The line of thinking is R_D(k, q) = R(k) − (the impossible states in k_q but are all reachable states in kth order system). According to Theorem 2, comparing with R_D(k, q) and R(k), the same value both in R_D(k, q) and R(k) is |R_d|, where R_d = {(y₁, …, y_k)|y_i = 0 or −1 (p = 1 to k)}, which is the token distribution on the right S²PR (Definition 7 in Appendix 2). In R_c, the same number of reachable states’ subsets both in R_D(k, q) and R(k) are from subset {(1₁, y₂, …, y_k)|1 ≤ q ≤ k, y_p = 0 or −1 (p = 2 to k)} till subset {(x₁, …, x_q₋₁ 1_qy_q₊₁, …, y_k)|1 ≤ q ≤ k, where x_i = 1 or 0 (i = 1 to q − 1) and y_p = 0 or −1 (p = q+1 to k)}. By induction, the impossibility of reachable states in subset R_q₊₁ = {(x₁, …, x_q 1_q+1y_q₊₂, …, y_k)|…} of R_D(k, q) is subset I_q = {(x₁, …, x_q 1_q+1y_q₊₂, …, y_k)|where x_i = 1, i = 1 to q, y_p = 0 or −1 (p = q+2 to k)}, and |I_q| = C(q, q)2^(k−q−1). When R_q₊₂ = {(x₁, …, x_q₊₁ 1_q+2y_q₊₃, …, y_k)|…}, the set of impossibility is I_q₊₁ = {(x₁, …, x_q₊₁ 1_q+2y_q₊₃, …, y_k)} where x_i = 1, i = 1 to q+1 (the number is 2^(k−q−2)C(q+1, q+1)) ∪ {(x₁, …, x_q₊₁ 1_q+2y_q₊₃, …, y_k)|x_i = 0 or 1, i = 1 to q+1, x₁+···+x_q₊₁ = q, y_p = 0 or −1 (p = q+3 to k)} (the number is 2^(k−q−2)C(q+1, q)); hence |I_q₊₁| = [C(q+1, q+1))+C(q+1, q)]2^(k−q−2), till R_k = {(x₁, …, x_k₋₁ 1_k)|…} the subset of impossibility is I_k−1 = {(x₁, …, x_q₊₁x_q₊₂x_q₊₃… 1_k)|x_i = 0 or 1, i = 1 to k − 1, x₁+···+x_k₋₁ ≥ q}, and |I_k₋₁| = [C(k − 1, k − 1))+···+C(k − 1, q)]2^(k−k). We have all subsets of impossibility occurring from R_q₊₁ to R_k, and the number of impossibility counts from C(q, q)2^(k−q−1) to [C(k − 1, k − 1)) + ···+C(k − 1, q)]2^(k−k) = $\sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i)) (2^{k - l})$ .

Hence, $R_{D} (k, q) = R (k) - \sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i)) (2^{k - l})$ .■

Let k = 8, q = 2, impossible states of R_D(8, 2) are shown below. l is the first position of x_i = 1 (Table 2).

Table 2.

Counts of impossible states of R_D(k, q) where k = 8, q = 2.

l	i	x ₁	x ₂	x ₃	x ₄	x ₅	x ₆	x ₇	x ₈	Total
1	−	1	0: there is no impossible state							0
2	−		1	0: there is no impossible state						0
3	0–0	C(2, 2) = 1		1	2⁵: x_j = 0 or −1, j = 4 to 8 (k − l = 8 − 3 = 5)					32
4	0–1	C(3, 3) + C(3, 2) = 4			1	2⁴: x_j = 0 or −1, j = 5 to 8 (k − l = 4)				64
5	0–2	C(4, 4) + C(4, 3) + C(4, 2) = 11				1	2³: (k − l = 8 − 5 = 3)			88
6	0–3	C(5, 5) + C(5, 4) + C(5, 3) + C(5, 2) = 26					1	2²: (k − 6 = 2)		104
7	0–4	C(6, 6) + C(6, 5) + C(6, 4) + C(6, 3) + C(6, 2) = 57						1	2¹	114
8	0–5	C(7, 7) + C(7, 6) + C(7, 5) + C(7, 4) + C(7, 3) + C(7, 2) = 120							1	120
Total impossible state										522
R_D(8, 2) = R(8) − 522 = 1280 − 522 = 758

Theorem 5

Let L(k) be the live states of a kth order system, L_D(k, q) be the number of live states of kth order system with token number of left idle place being q

$L_{D} (k, q) = L (k) - \sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i))$ , where C(l − 1, l − 1 − i) = (l − 1)!/[(l − 1 − i)!i!] is a binomial coefficient.

Proof

The proof is similar to that of R_D(k, q). The difference is that by Lemma 3, s is a live state if and only if s = {(y₁, …, y_k)|y_i = −1 or 0}, or s = {(x₁, …, x_k)|x_i = 1 or 0}. Hence, comparing to R_D(k, q), the impossibility of live states in subset L_q+₁ = {(x₁, …, x_q 1_q+1y_q+₂, …, y_k)|…} of L_D(k, q) is subset I_q = {(x₁, …, x_q 1_q+1 0_q+2… 0_k)| where x_i = 1, i = 1 to q, y_p = 0 (p = q+2 to k)}, |I_q| = C(q, q). I_q+₁ = {(x₁, …, x_q+₁ 1_q+2 0_q+3… 0_k)} where x_i = 1, i = 1 to q + 1(the number is C(q + 1, q + 1)) ∪ {(x₁, …, x_q+₁ 1_q+2 0_q+3… 0_k)|x_i = 0 or 1, i = 1 to q+1, x₁+···+x_q+₁ = q} (the number is C(q+1, q)), hence |I_q+₁| = C(q + 1, q+1)) + C(q + 1, q). Similar to R_D(k, q), we have all the subsets of impossibility occurring from L_q+₁ to L_k; the number of impossibility counts from C(q, q) to [C(k − 1, k − 1)) + ··· +C(k −1, q) = $\sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i))$ .

Hence, $L_{D} (k, q) = L (k) - \sum_{l = q + 1}^{k} (\sum_{i = 0}^{l - q - 1} C (l - 1, l - 1 - i))$ .■

The forbidden states of k_q is $ϑ_{D} (k, q) = R_{D} (k, q) - L_{D} (k, q)$ . Table 3 shows the number of reachable, live and forbidden states of k_q where k = 8 and q = 1 to 7

Table 3.

The value of R_D(k, q), L_D(k, q), and L_D(k, q), where k = 8, q = 1 to 7.

q	8	7	6	5	4	3	2	1
R_D(8, q)	1280	1279	1270	1233	1140	977	758	511
L_D(8, q)	511	510	502	474	418	348	292	264
ϑ_D(8, q)	769	769	768	759	722	629	466	247

Computation of CRSs of A-net

According to R_D(k, q) and L_D(k, q) of deficient kth order system derived in section “Computation of CRSs of deficient kth order system,” and a given state function of TNCS, f(z), in this section we construct closed-form solution to compute CRSs of A-net.

Definition 4

An A-net system is a subclass of S³PR composed by a kth order system and a deadlock-free TNCS connected to idle process of left process:

The link point of kth order system and TNCS is the top-left transition of kth order system.

None of transition of TNCS is firable by the resources and places of kth order system.

Let m be the maximum token number that can flow into TNCS; the limitation of m is m < k.

Under the limitation of m < k, both kth order system and TNCS can expand its net structure independently.

There is a measurable state function of TNCS f(z), where z is the number of tokens flowing into TNCS, such that |f(z)| can map to a non-ambiguous number of different states of combination under current information of z in TNCS.

Let R_D(k, k) = R(k). Hence, we have the following:

The reachable state of A-net is $R'_{A} (k, m) = \sum_{l = 0}^{m} (| f (l) |) R_{D} (k, k - l))$ .

The live state of A-net is $L'_{A} (k, m) = \sum_{l = 0}^{m} (| f (l) |) L_{D} (k, k - l))$ .

The forbidden state of A-net is $ϑ'_{A} (k, m) = R'_{A} (k, m) - L'_{A} (k, m) = \sum_{l = 0}^{m} (| f (l) |) (R_{D} (k, k - l) - L_{D} (k, k - l))$ .

The livelock state of A-net is $D'_{A} (k, m) = \sum_{l = 0}^{m} (| f (l) |) D_{D} (k, k - l)) = \sum_{l = 0}^{m} (| f (l) |) D (k)$ .

The important characteristic of A-net is that m and k can be expanded independently under the condition m < k. Extending k of A-net from 4 to 8, we have the value of $R'_{A} (k, m)$ , $L'_{A} (k, m)$ , and $ϑ'_{A} (k, m)$ as listed in Table 4.

Table 4.

The value of $R'_{A} (k, m)$ , $L'_{A} (k, m)$ , and $ϑ'_{A} (k, m)$ , where k = 4 to 8; m = 2.

k	4	5	6	7	8
$R'_{A} (k, m)$	184	439	1014	2293	5108
$L'_{A} (k, m)$	117	244	499	1010	2033
$ϑ'_{A} (k, m)$	67	195	515	1283	3075

These results of $R'_{A} (k, m)$ have been validated experimentally by INA.

Extending m of A-net from 3 to 5 with k = 8, we have the value of $R'_{A} (k, m)$ as listed in Table 5.

Table 5.

The value of $R'_{A} (k, m)$ , where m = 3 to 5; k = 8.

m	3	4	5
$R'_{A} (k, m)$	10,160	20,088	39,382

Application

Based on the closed-form solution and the concept of proof by model, we can accelerate the construction of the closed-form formula of the reverse net of A-net, rev(A-net), which is the fundamental model of merging two different manufacturing processes, due to that the live states’ pattern of rev(A-net) will be the reverse states of A-net’s live states and they have the same number of live states.

In Appendix 3, we will show how to extend our methodology to derivate the closed-form solution of AR⁺-net which is a net structure containing a non-sharing subnet and multi-processes on the right-hand side extended from A-net.

Conclusion

Here, we not only report the very first method to compute in closed form the number of CRSs of A-net without constructing a reachability graph but also demonstrate the procedure of how to construct deficient kth order system by particular case step by step. The most important line of thinking is R_D(k, q) = R(k) − (the impossible states in k_q but are all reachable states in kth order system), as shown in the proof procedure of Theorem 4. According to the procedure listed above, readers can derive the closed-form solution of more complicated A-net or even of which case non-sharing circle subnet can be any position in left or right process. Besides, by our closed-form solution, we can provide live, forbidden, and livelock states’ information that INA tool cannot offer, which show non-significant reachable states’ information only, due to no deadlock states in A-net and that INA tool cannot detect livelock states. This helps estimate the percentage of livelock (deadlock) and legal state losses due to the addition of a monitor and avoid the dire situation of mid-run abortion of reachability analysis due to exhausted memory. Furthermore, here we extend the MLR concept to the variant kth order system with non-sharing subnet.

Future work should extend the analysis method in this article to A-net with one non-sharing resource (e.g. used by only one process) located in any position of the system.

Footnotes

Appendix 1

Appendix 2

Appendix 3

Academic Editor: ZhiWu Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article:This work was supported by the National Science Council (Republic of China) under Grant NSC 103-2221-E-004-001.

References

Chao

DY.

Reachability of nonsynchronized choice Petri nets and its applications. IEEE T Syst Man Cyb A 2005; 35: 1203–1213.

Chao

DY.

Computation of elementary siphons in Petri nets for deadlock control. Comput J 2006; 49: 470–479.

Chao

DY.

Improvement of suboptimal siphon- and FBM-based control model of a well-known S³PR. IEEE T Autom Sci Eng 2011; 8: 404–411.

Chao

. Enumeration of lost states of a suboptimal control model of a well-known S³PR. IET Control Theory Appl 2011b; 5: 1277–1286.

Ezpeleta

Colom

Martinez

A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Robot Autom 1995; 11: 173–184.

Lee

Zhou

Hsu

PL.

An application of Petri nets to supervisory control for human-computer interactive systems. IEEE T Ind Electron 2005; 52: 1220–1226.

Sun

Jiang

Zhou

MC.

Interactive web service composition based on Petri net. T Inst Measure Control 2009; 33: 116–132.

Uzam

Zhou

MC.

An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems. Int. J Prod Res 2006; 44: 1987–2030.

Wang

Zhou

Ding

JH.

Software architectural modelling and verification: a Petri net and temporal logic approach. T Inst Measure Control 2010; 33: 168–181.

10.

Zimmermann

Technische Universitat Ilmenau, System and Software Engineering, D-98684 Ilmenau, Germany, 2012, http://www.tu-ilmenau.de/TimeNeT

11.

Ferrarini

On the reachability and reversibility problems in a class of Petri nets. IEEE T Syst Man Cyb 1994; 24: 1474–1482.

12.

Hiraishi

Ichikawa

A class of Petri nets that a necessary and sufficient condition for reachability is obtainable. T Soc Instrum Control Eng 1988; 24: 635–640.

13.

Ichikawa

Yokoyama

Kurogi

Control of event-driven systems: reachability and control of conflict-free Petri nets. T Soc Instrum Control Eng 1985; 21: 324–330.

14.

Kostin

AE.

Reachability analysis in T-invariant-less Petri nets. IEEE T Autom Control 2003; 48: 1019–1024.

15.

Lee

Kumagai

Kodama

Reachability of LSFC nets. IEEE Int Symp Circuit Syst 1990; 4: 2666–2669.

16.

Liang

Chao

DY.

Enumeration of reachable states for arbitrary marked graphs. IET Control Theory Appl 2012; 6: 1536–1543.

17.

Starke

PH.

INA: Integrated Net Analyzer handbook. Germany: Humboldt University, 1992.

18.

Chao

DY.

Closed-form solution of controller synthesis for infinitely large systems of resource sharing systems of a subclass of Petri nets. T Inst Measure Control 2015; 38: 83–92.

19.

Zhao

On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE T Syst Man Cyb A 2008; 38: 369–384.

20.

Chen

Barkaoui

New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. IEEE T Syst Man Cyb Syst 2014; 44: 1384–1400.

21.

Uzam

Gelen

. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. J Intell Manuf 2016; 27: 1111–1129.

22.

Liu

Barkaoui

Necessary and sufficient liveness condition of GS3PR Petri nets. Int J Syst Sci 2015; 46: 1147–1160.

23.

. Policy to cope with deadlocks and livelocks for flexible manufacturing systems using the max-controlled new smart siphon. IET Control Theory Appl 2014; 8: 1607.

24.

Chao

DY.

A simple modification of deadlock prevention policy of S3PR based on elementary siphons. T Inst Measure Control 2010; 33: 93–115.

25.

Chao

Chen

J-T

A novel liveness condition for S3PGR2. T Inst Measure Control 2012; 35: 131–137.

26.

Chao

K-C.

An integrated approach for supervisory control of a subclass of Petri nets. T Inst Measure Control 2012; 35:117–130.

27.

Chen

Khalgui

. Design of a maximally permissive liveness: enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

28.

Liu

Hanisch

. Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. IEEE T Syst Man Cyb A 2012; 42:178–191.

29.

Zhou

MC.

Deadlock control of automated manufacturing systems based on Petri nets—a literature review. IEEE T Syst Man Cybt C 2012; 42: 437–462.

30.

ZW.

Solving siphons with the minimal cardinality in Petri nets and its applications to deadlock control. Int J Prod Res 2012; 50: 6203–6218.

31.

Chen

Zhou

MC.

Optimal supervisory control of flexible manufacturing systems by Petri Nets: a set classification approach. IEEE T Autom Sci Eng 2014; 11: 549–563.

32.

Chao

DY.

Enumeration of reachable (forbidden, live, and deadlock) states of K-th order system of Petri nets. IMA J Math Control Inf 2014; 32: 823–837.

33.

Chao

TH.

Computation of control related states of bottom k-th order system (with a non-sharing resource place) of Petri nets. T Inst Measure Control 2014; 37: 382–395.

34.

Chao

. Enumeration of reachable, forbidden, live states of gen-left k-net system (with a non-sharing resource place) of Petri nets. In: Proceedings of the 2014 IEEE symposium on computational intelligence in control and automation (CICA), Orlando, FL, 9–12 December 2014, pp.1–7. New York: IEEE.

35.

Chao

TH.

The fundamental closed-form solution of control related states of k-th order S3PR system with left-side non-sharing resource places of Petri nets. Int J Control 2015; 89: 169–178.

36.

Chao

Chi

. Proof by model: a new knowledge-based reachability analysis methodology for Petri net. IMA J Math Control Inf. Epub ahead of print 11 July 2016. DOI: 10.1093/imamci/dnw025.

37.

. Parameterized of control related states of Gen-Right k-th order system of Petri nets based on proof by model of Gen-Left. In: Proceedings of the 42nd annual conference of the IEEE industrial electronics society, IECON, Florence, Italy, 23–26 October 2016, pp.276–281. New York: IEEE.

38.

Chao

. MLR: a new concept to launch a partial deadlock avoidance policy for k-th order system of Petri nets. In: Proceedings of the 41st annual conference of the IEEE industrial electronics society, IECON, Yokohama, Japan, 9–12 November 2015, pp.003148–003152. New York: IEEE.

39.

Schrijver

Theory of linear and integer programming. Hoboken, NJ: John Wiley & Sons, 1998.

40.

Liu

Wang

ZW.

Supervisor reconfiguration for deadlock prevention by resources reallocation. J Appl Math 2013; 2013: 315894.

Construct the closed-form solution of A -net of Petri nets by case study

Abstract

Keywords

Introduction

Methodology of closed-form solution of kth order system

Definition 1

Definition 2 32

Lemma 1 32

Lemma 2 32

Theorem 1 32

Lemma 3 32

Theorem 2 32

Corollary 2 32

Theorem 3 32

Computation of CRSs of an ordinary A-net

Computation of CRSs of a-net

Computation of CRSs of deficient kth order system

Construct general formula of RD(k, q) and LD(k, q)

Definition 3

Theorem 4

Proof

Theorem 5

Proof

Computation of CRSs of A-net

Definition 4

Application

Conclusion

Footnotes

Appendix 1

Appendix 2

Appendix 3

Declaration of conflicting interests

Funding

References

Definition 2³²

Lemma 1³²

Lemma 2³²

Theorem 1³²

Lemma 3³²

Theorem 2³²

Corollary 2³²

Theorem 3³²

Construct general formula of R_D(k, q) and L_D(k, q)