Intelligent Control and Automation, 2011, 2, 310319 doi:10.4236/ica.2011.24036 Published Online November 2011 (http://www.SciRP.org/journal/ica) Copyright © 2011 SciRes. ICA Controllability of Strongly and Weakly Dependent Siphons under Disturbanceless Control* Daniel Yuh Chao1, KuoChiang Wu2, JiunTing Chen1, Mike Y. J. Lee1,3 1Department of Management and Information Systems, National Chengchi University, Taipei, Chinese Taipei 2Department of Computer Science & Engineering, Tatung University, Taipei, Chinese Taipei 3Department of Business Administration, China University of Technology, Taipei, Chinese Taipei Email: yuhyaw@gmail.com, d9206006@ms2.ttu.edu.tw, andy@mail.shu.edu.tw, yjlee@cute.edu.tw Received April 1, 2011; revised June 28, 2011; accepted July 5, 2011 Abstract Li and Zhou propose to add monitors Vs to elementary siphons S only while controlling the rest of dependent siphons—important for large systems but far from being maximally permissive. The control policy for weakly dependent siphons (WDS) is rather conservative due to some negative terms in the controllability. We show that this is no longer true as can be shown that it has the same controllability as that for strongly dependent siphons. Keywords: Petri Nets, Siphons, Controllability, FMS, S3PR 1. Introduction A flexible manufacturing systems (FMS) consists of several concurrent processes competing for resources such as machines, robotics, etc. to produce different kinds of parts. Each process performs a sequence of operations to manufacture a part of a product. Mutual waiting for resources can bring the system into a deadlock where no process can proceed. An FMS can be modeled by a Petri net (PN). System properties such as boundedness, liveness and reversi bility are fundamental for an FMS to operate in a sTable, deadlockfree, and periodic fashion. Deadlock prevention approaches [123] create the con trol policy in a static way by building a Petri net model first and then adding necessary control to it such that the controlled model is deadlockfree. Control places and rel ated arcs are often used to attain such purpose resulting in less states reached, but the system runs quicker as a result of no online computation. A siphon (trap, respectively) is a set of places [where tokens can leak out (inject in, respectively)] of a PN modeling an FMS. Once the siphon has lost all its tokens, output transitions of places in the siphon can never be executed and the net is not live. Control places and related arcs are often added upon emptiable siphons to disallow them to become unmarked (no tokens). This disturbs the original model and loses some reachable good states; i.e., less permissive, impact ing the performance of the supervisor. Ezpeleta et al. [11] propose adding a monitor upon each problematic siphon for an S3PR which stands for systems of simple sequential processes with resources. This method generally requires adding too many moni tors due to the fact that there are too many emptiable siphons. The iterative control method in [12] reduces the number of monitors by finding all emptiable siphons in each iteration step. The method becomes very difficult and remains complex even for a moderatesize model. Furthermore, Ezpeleta et al. [11] move all output (called Type2, or source) arcs of each monitor S to the output (called source) transition of the entry (called idle place) of input raw materials to limit their rate into the system to avoid generaing new emptiable siphons, called SMSless approach. This may overly constrain the system to reach much fewer reachable states (6287, the same as that by Li et al. [13,14] but with a lot more control elements) than the maximal permissive one using the region method by Uzam and Zhou [15]. V It is impractical to add a monitor to each emptiable siphon for large systems since the number of emptiable siphons or control elements grows quickly with respect to the size of a Petri net. Li and Zhou [13,14,16,17] tackle this problem by classifying siphons into elemen tary and dependent ones. *This work was supported by the National Science Council under Gant SC 992221E004002.
D. Y. CHAO ET AL.311 By adding monitors to only elementary siphons, Li and Zhou [13] greatly reduce the number of control nodes and arcs, essential for large systems. Some of the rest of emptiable (called dependent) siphons may already be controlled depending on the controllability. Otherwise, the control depth variable may need to be increased to avoid the siphon unmarked and reach fewer states. The control policy for weakly dependent siphons is rather conservative [13] (such that fewer states are reached) by ignoring some negative terms in the controllability. The control place and arcs for siphon , similar to resource places, form a number of elementary circuits. Hence, there is an elementary circuit containing adjacent control places, from which we can synthesize new problematic siphons. To avoid such, output arcs of a control place are moved from sink transitions of the siphon to source transitions of the processes. As a result, the region S S (called controller region) covered by control arcs is larger than the region (called the complementary set of ) to trap tokens from . The disturbed region becomes larger after the movement of output arcs. This loses more states due to the presence of control places and arcs, which disturbs the markings of the original model. B S S We [14,6,7] show that elementary (resp. strongly dependent) siphons in an S3PR (systems of simple sequential processes with resources) may be synthesized from elementary (resp. compound) resource circuits. There is no need to compute the basis for the set of elementary siphons from the vector space containing all characteristic Tvectors. Furthermore, we add monitors for different types of siphons in some sequence to avoid redundant monitors and losing live states. It is unclear whether the same advantage can be extended to weakly dependent siphons. We don’t know from what circuits can we synthesize a weakly dependent siphon , and the condition that is controlled. This paper shows that weakly dependent siphons have a similar controllability to that for strongly dependent siphons under the disturbanceless control policy even though Li et al. prove that the policy for weakly dependent siphon is more conservative than strongly dependent siphons. S S The rest of the paper is organized as follows: Section 2 and 3 presents the basis to understand the paper. Section 4 reviews the theory on controllability of strongly dependent siphons in Li and Zhou [13,14]. Section 5 develops the theory to weakly dependent siphons based on Proposition 1. It is interesting to observe that weakly and strongly dependent siphons have the same controll ability for compound siphons. Section 6 concludes the paper. 2. Preliminaries Please refer to [1] for terms related to Petri nets. We now define characteristic Tvectors, elementary and depend ent siphons. Definition 1. [13,14]: Let be a subset of places of N. Pvector P is called the characteristic Pvector of iff , 1pp ; otherwise 0p . is called the characteristic Tvector of , if , where [N] is the incidence matrix. = TT [N] Physically, the firing of a transition t where 0,t =0t , and 0t increases, maintains and de creases the number of tokens in , respectively S Definition 2. [13,14]: Let N = (P, T, F) be a net with P = m, which has k siphons 1, , ···, , , S2 Sk Smk IN, where IN = {0, 1, 2, ···}. Define 12 T k km and 12 . T k km (resp. ) is called the characteristic P(resp. T)vector matrix (resp. ) of the siphons in N. Let S , S , ···, and S ( , , 1, 2, ···, k) be a linear independent maximal set of matrix . Then , ES,,SS is called a set of elementary siphons. S is called a strongly depen dent siphon if Si SiE aiS where . 0 i a S is called a weakly dependent siphon if nonempty A, B , such that AB and = SiSi i SA SB ii aa S i where . 0 i a In [13,14], a strongly dependent siphon is also called a strict redundant one. Li and Zhou propose to find elementary siphons by constructing the characteristic Pvector (resp. Tvector)vector matrix [λ] (resp. [η]) of the siphons in N followed by finding linearly inde pendent vectors in [λ] (resp. [η]) The siphons corre sponding to these independent vectors are the elementary siphons in the net system. Note that Def. 2 and the above calculation of linearly independent vectors do not assume N to be an S3PR and are applicable to arbitrary nets. Figure 1(a) shows an example of weakly dependent siphon. Table 1 below lists the four strict minimal siphons and their η, where 412 =3 . 3. Types of SMS In [2,3,6], we show that SMS can be synthesized from resource or core subnets. New types (such as control siphons) of SMS can be synthesized from control subnets formed by control places. If we add monitors to these different types of siphons in a certain order, then some siphons may be redundant. We construct an SMS based on the concept of handles. Roughly speaking, a “handle” is an alternate disjoint path Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL. Copyright © 2011 SciRes. ICA 312 Table 1. Four SMS in Figure 1(a) and their , where 4 = 1 + 2 − 3. S η Set of places [S] S1 t2 – t4 + t8 – t9 p4, p12, p13, p14, p15 p2, p3, p8, p9, p10, p11 S2 t1 – t3+t7 – t10 p5, p11, p14, p15, p16 p3, p4, p7, p8, p9, p10 S3 t2 – t3 – t4 + t7 p4, p11, p14, p15 p3, p8, p9, p10 S4 t1 + t8 – t9 – t10 p5, p12, p13, p14, p15, p16 p2, p3, p4, p7, p8, p9, p10, p11 (a) (b) Figure 1. (a) Example weakly dependent siphon [14]. ra = p16, rb = p15, rc = p14, rd = p13, ta = t1, tb = t2, tc = t3, td = t8, c t = t4; (b) controlled model of that in Figure 1(a). between two nodes. A PThandle starts with a place and ends with a transition while a TPhandle starts with a transition and ends with a place A core subnet can be obtained from an elementary circuit, called core circuit, by repeatedly adding handles. The control place and arcs for siphon S, similar to resource places, form a number of elementary circuits. Hence, there is an elementary circuit containing adjacent control places, from which we can synthesize new problematic siphons. Definition 3. An elementary resource circuit is called a basic circuit, denoted by . The siphon constructed from is called a basic siphon. A compound circuit 12 1nn b c b c cccc c is a circuit consisting of multi ply interconnected elementary circuits , , ···, 1 c2 cn c , pp ii r rR such that 1ii cc (i.e., and 1i c in i c tersects at a resource place i). The SMS synthesized from compound circuit c using the HandleConstruction Procedure in [9] is called an ncompound (resp. control, mixture) siphon S, denoted by . r 12 1 SS S nn SS 4. Controllability for Strongly Dependent Siphons We review the controllability for strongly dependent siphons to compare with that for weakly ones to be derived in Section 5. We first present the theory below to decide whether a monitor to a compound siphon is redundant. To disturb the controller region the least, we should allow M([S1]) to reach its maximum; thus setting 001 = S MVM S1 1; S is said to be limit controlled. In general, 0 =MV M 01 S 11 SS , where 1 S is the control depth variable. 1 S 1 is adjusted to be greater than 1 if some dependent siphons are not controlled. As a result, max M([S1]) is less than and the controller region is more disturbed causing more states lost. 01 1MS Definition 4. Let 00 =MV MS SS where 1 S S is called the control depth variable. S is said to reach its limit state when M(S) = 1; it is limitcontrolled iff it is able to reach its limit state but not able to reach unmarked state; i.e., 1 or minM(S) = 1. Theorem 1. [21]: Let (N0, M0) be a net system and 0 be a strongly dependent SMS w.r.t. elementary siphons S 1 S2 Sn S =1 n i i , , ···, and such that where , and 0= 1, 2,,in SS, ij iff 1 i ij. is ex tended by n control places 1 S, 2 S, ···, and S such that 1, 2, ···, and are limitcontrolled. can never be emptied iff , 0 N V V n bM V 01 S n S SS0 S 1 ==S ii 1, 2,,1in . Note that for strongly dependent siphon 01ii ,SS S is a single resource , 01 implies that there is only one token in the initial marking of . ii MS S =1 r r
D. Y. CHAO ET AL.313 5. Controllability for Weakly Dependent Siphons This section shows that if 0 S weakly depends on 1 and 2, then there exists a third siphon 3—syn thesized from core circuits 1 and 2, respectively, such that 0123 S S S c c = . Other properties will also be derived, from which we will derive the controllability of a weakly 2compound siphon. Chao [2,3,6], show that in an S3PR, an SMS can be synthesized from a strongly connected resource subnet and any strongly dependent siphon corresponds to a compound circuit where the intersection between any two elementary circuits is at most a resource place. Let be a strongly dependent siphon, , , ···, and be elementary siphons, with 012 S S n 0 S n SS 1 S2 S S = . It is shown in Chao [2,3,6] that 0 (the core circuit from which to synthesize ) is a compound resource circuit containing 12 , and the intersection between any two i and c0 S , n c,,cc c c c , i = j − 1 > 0, is exactly a resource place, where i (i =0, 1, 2, ···, n) is the core circuit from which to synthesize i. Thus, if S0 is a WDS (weakly dependent siphon), the intersection between any two ci and cj, i = j − 1 > 0, must contain more than one resource place. S Let and be the SMS synthesized from basic circuits 1 and 2, respectively, where 12 . One can synthesize a third SMS, denoted by 0, from the strongly connected resource subnet 12 . For S0 to be a WDS, must contain more than one resource place. 1 S c 2 S c 1 c cc S cc 2 c To simplify the presentation, 12 is assumed to be cc bbc rt r ,,r r r on Process 1, where b, are two resource places, and r c r c r ,, ab Rcrr 1 2bcd as shown in Figure 1(a). The more complicated case can be treated similarly as in [9]. For Rc instance, in Figure 2, 114151 ,,Rcp p p6 and 1415 ,pp 21 (one more place than the above one). 213 ,,Rc pp It is assumed, that a core circuit spans between process 1 (WP1) and process 2 (WP2) and () denotes path 12 k rr r 11 2 211kkk rtr trtr . Let 1trtr aab crtrbcca and 2bbccd d b crtrtrtr span between process 1 and process 2 [see Figure 1(a), where , 16a rp15b rp , 14 p c r , 13d rp , 1a tt , 2b, 3, 8d tttt c tt , 4c tt ]. Note that a, b, c, c and d t may not be in the same process; some are in process 1 and the rest are in process 2. Consider the resource path on process 1. There are only 2 possible cases satisfying the above conditions are as follows: 1) 2) . Case 2 is equivalent to Case 1 by relabeling by and by , respectively. t t r r t t abc rdbca rrrr a d r r rrr d r r rrr r rr d a Note that it is possible that abcbcbcd , which can be treated similarly as in Chao [10]. For Case 1, 1 can be broken two paths: one, c aabbc rt rt r, in process 1, denoted by 1 bc r aab rt rt; another, cca rtr , in process 2, denoted by 2; i.e., cc rt a r 1aabbc Similarly, c2 can be broken two paths: one, 12 . ca rtr c trtrcr bb c cd rtrrt , in process 1, denoted by 1 ccd rtr bb rt ; another, dd rt b r, in process 2, denoted by 2; i.e., ddb rtr 212 bbcdd d b. In the sequel, i crtrtrtr refers to the Tcharacteristic vector of siphon Si synthesized from ci. Theorem 2. [9]: Let . Then 1 =SSS2 012 =3 . On the Process 2 side in Figure 1(a), there should be no PP'path of the form [c ] (resp. []) to form basic circuit 4 (resp. 4 c) consisting of only two resource places of d and c (resp. a and b r), since 0 is no longer a weakly dependent siphon as derived below. First, and . This leads to d rtr r 3 * ba rt 3 c c = r 14 cc r S c25 =cc Figure 2. Example a 3dependent weakly dependent siphon. S0 = S6 = S1 S2 S3, S4 = S1,2, S5 = S2,3 and 0 = 1 + 2 + 3 − 4 − 5. Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL. Copyright © 2011 SciRes. ICA 314 13 =4 , 23 =5 == , and 233401 5 S S 5 S 0 S ; 0 strongly depends on 3, 4, and and is no longer a weakly dependent siphon. S Lemma 1. [9]: Let (0,0 N ) be a net system and 0 be a weakly dependent SMS w.r.t. elementary siphons , , and where S 1 S2 S3 S01 =23 . Then 1) 3b BS PHr, where 12 = SS , 21 =BS Sb , . 3 rS 2) 3c rS and 0c rS. 3) rMS r 30 0 == cb MminM S. Consider the S3PR in Figure 1(a), 124 == SS p 15 = b , , 21 11 =[]=BS Sp 3. BHr p Sc Furthermore, 14, =rp 3810 ()=, , c3 38910 , , , r ppp S pppp and 8910 ,,,,, 0 237c r Spp pppp . Define S12 = S3 and S0 = S1 S 2 since . 12 is similar to 12 S in that can never be emptied if for both cases. 12 is different than 12 in that 12 3 RS SRS 0 S SS SS S S 1b S 12 SRS for the former contains more than one resource place while the latter contains only one resource place. Consider the S3PR in Figure 2. Table 2 lists eight SMS , and core circuits in Figure 2. Note that S 12 15214 cc ptp SSS is not a single resource place and hence 712 cannot be a strongly dependent siphon and is a weakly dependent siphon. Similarly, 213 1812 cc ptp SS S 3 is not a single resource place and hence 82 3 cannot be a strongly dependent siphon and is a weakly dependent siphon. Note that c2 contains 4 rather than 3 resource places assumed above. Yet, all relevant theory remains true. Theorem 3. Let be a net system and 0 be a weakly dependent SMS w.r.t. elementary siphons 1, 2, and 3 where 00 ,NM = S S SS0123 VV . 0 is ex tended by control places 1 S, 2 S, and , such that , , and are limitcontrolled. Let N 3 VS 1 S2 S3 S 10 = SS, 20 BS S =, and 3 = BSP Hr, (by Proposition 1) 3 rS , 0 can never be emptied iff ; 2) is limit controlled iff . S 0 ==bMr 1 S 1 0 S 0 ==bMr Proof. 1) () Assume 0 is unmarked (hence , ), while each of 1, 2, and is marked; i.e., , =0Mr 0 S r 1 MS S S3 S 0 2 MS 0, and 30MS . By Proposition 1, it holds that 3 = BS P Hr . Let 2 =S 10 since 1 and are marked. 0 S1 S MS SM 2 S ==r H 0 Mr since 1M =0Mr and . Now 0 Mr =1 =2B 3 MS M MHr 1= MH P 3 S M 2 A r . However, , which is impossible. Thus, it is impossible that 10 S2 S 0 =1MS MS. This leads to that either 0MS S 10 or 20 0MSS , which implies that S0 can never be emptied. () Assume contrary and 0 =0bMr. Then it is possible that 0MA and 0MB such that each of , , and 3 is marked, while 1 S2 S S =0SS S 1020 or 0 is unmarked against the assumption that 0 is marked. 2) ( =SMS SM ) If 0 ==bMr 1, then there is a reachable marking such that =1MA, =0 MBMB or , =1 =1MA . Either one implies that . () Assume contrary and 0=1MS 1r S 0. The proof of part 1 of this theorem indicates that 0 is unmarked. Hence cannot be limit controlled against the assumption. =bM 0 S Thus, it is similar to a strongly dependent siphon synthesized from a compound circuit where is also controlled if 1 b and both 1 and 2 are limit controlled. For the S3PR in Figure 2 where each elementary siphon is limitcontrolled and 04 is controlled as well. Assume otherwise and 4 is empty. Then S 12 ccS S S =SS S =1 10 MS 20 ==MS S1S. Let 410 == SSp , 20 ==BS S 11 p, 311 == BSP Hrp. If 0 Mr=1=b , then it is impossible that 10 . Thus, can never be emptied. 20 ==S S1MS SM 0 The condition (i.e., S 3 = BS PHr, 3 rS ) in Theorem 3 is generally true for vertically stacked S3PR (in most literatures); that is sink transitions of 1 and 2 are in the same processes. The condition may not hold for horizontally stacked S3PR; that is, sink transitions of and are in different processes. In this case, S S 1 S2 S 110 = SS Hr and r 2, 1. However, it remains true that 0 =BS S22 rrH 3 = BSP0 S. can become unmarked when 0 =0M r 10 S1 MS , =0 20 02 MSSM r MS , . 0MA B 3 Define S12 = S3 and S0 = S1 S 2 since 12 3 . 12 =RS SRSSS is similar to 12 in that can never be emptied if for both cases. 12 SS 0 S SS =1b is different than 12 in that SS RS S 12 for the former contains more than one resource place while the latter contains only one resource place. Theorem 4. Let 00 ,NM be a net system and be a weakly dependent SMS such that 0 S 012 =SSS n S 1, 2,,in denoting the fact that , ij SS holds iff 1ij. Let 0 = ii SS, 10 S= ii BS , ,1 i = ii ii BSPHr , where ,1iii rS 0 N 2V3 S V S S3 S 0 S 1 . is extended by control places 1 S V, , 12 S, , , ···, and , such that 1 S, 2, 12, , 23 , ···, and n, 1,n are limitcontrolled, 1) can never be emptied iff 0ii , S V ==bMr 32 S VSn V SS 1,n n S V Sn 1, 2,,1in ; 2) is limit controlled iff 0 S
D. Y. CHAO ET AL.315 Table 2. Eight SMS S, and core circuits in Figure 2. S Set of places c S1 p516 = c1 [p14 t4 p16 t1 p15 t2 p14] + HPP' p15 t5 p14], [p14 t6 p15] and [p15 t7 p14]. , p17, p14, p15, p1 e c [ S2 p c = c 2 [p15 t2 p [p15 t7 p14] p PP p 5, p27, p15, p16 4, p26, p12, p13, p14, p15 2 e 14 t3 p13 t18 p12 t8 p15]+ HPP' [p13 t11 p12], [p12 t12 p13 ], [p15 t5 p14], [p14 t6 p15] and S3 2, p27, p11, p12, p13 3 e c = c 3 [p13 t18 p12 t17 p11 t14 p13] + HPP' [p13 t11 p12], [p12 t12 p13], and [p13 t13 p12] S4 p 4, p17, p14, p15 4 c = c 4[p15 t2 p14 t6 p15] + HPP' [p15 t5 p14] + H [p15 t7 p14] e S5 p 2, p26, p12, p13 5 e c = c 5 [p13 t18 p12 t12 p13]+HPP' [p13 t11 p12], and [p13 t13 p12] S6 11, p12, p13, p14, p6123 eeee cc c c S7 p 5, p26, p12, p13, p14, p15, p16 71 2 ee e ccc S8 p 4, p27, p11, p12, p13, p14, p15 82 3 ee e ccc By Theorem 3, the theorem holds f Assume ilds for 0ii bM Proof. 1) Prov =1r, 1, 2,,in =1. e by induction. or t ho =2n.=1kn . We need to prove that it also holds for =kn . Let * 1 =nn SS S , 12 1un SSS S , = 0 =u SS, ** 1 =n SS and 0 =B S. n S By Theorem 3.2, that *= u S is limit controlled. It is easy to see A and * 1, 1 nn n = BSP . Hence Hr 1,nn 1n BSP Hr and ,1unn BSH 3. 2. ( never be em r Theorem ntrolled art 1 of this theorem, 0 ==1 ii bMr , 2, ,in. () If 0 =()=1 ii bMr, 1, 2,,in . Consider * S, u S, . ) If 0 S ed. By 1, 0 S can never is limit co ti p be em , ptied by then it can p , * and B theorem. Prov knn that it als ==SS S trolled. ro pa e Assume it hs =1. Theu S is limit controlled since 0 ==1 ii bMr , 1, 2,,2in. We need to prove o holdsr =kn . By Theorem 3, it 0un Su n S are limit con trolled and 01 ==1 nn bM . Thus, 0 S is limit con This theoif the cdition in the theorem defined by in fo since both 1 in the pof of duction. S and r rt 1 of this old for holds for rem implies that on is satisfied, then the compound siphon is already co c nd ntrolled. Thus, Theorem 4 shows that the control lability for 01 2 =n SSS S for a weakly depen dent siphon 0 S is similar to that for a strongly depen dent siphon. Aol for WDS needs no longer be thatonservative as by Li and Zhou. Table 3 lists eight SMS S and their [S]. 0 ==SS SSS, 4 =SS, =SS a s a result, the contr 612 31,252,3 = 0 12345 . It can be verified that =[]= 11 217 SS p, 12 14 p, =[]=SBS 1 1151,2 BHpS . 22326 == SSp, 23 22 ==Sp, BS 2 2132,3 BHpS By Theorem 3, S . 6can never be emptied iff 10 1520 13 ==bMpb Mp. firmed using the INA (Integrated resulting controlled net (see sta model, where ==1 This has been con Net Analyzer). The Table 4) reaches 32298 trolled tes out of the total 45135 states of the uncon 016 014012011 ====2Mp MpMpMp and 01 06 ==2Mp Mp. Note that even though some new siphons (such as control siphons) are generated by the presence of Why this research. Physically, for 6 S to become empty under monitor places without adding monitors for these n is so is a subject for future , the controlled ew siphons. net is live , =0Mr , for every resource place in 6 S. Thus, all tokens in 0 r must stay in r. If 013 1Mp, it is possible that both p and p 226 plies both 2 S an3 S are marked. Even if are marked, which im d Mp 015 1 , this token may go to p such that 1 S is also mark6 may becomark tokens in 16 p and pgo to 7 and 20 p, respec tively. Thus, en though each of 1 S, 2 S, an adding a monitor, 6 Say still become unmarked and nes a monitor. On the othand, if 17 unmed w p m ed. Se 11 ev marked by ed her hen d all 3 S is 10 1520 13 ====1bMpb Mp, we sh that i6 S becomes unmarked, at least one o1 S, 2 S, and 3 S is also unmarked contradicting th ow f fact that each ding a monitor. f 1 S, 6 S to e 2 S by ad to become unmarked, all tokens of For , and 3 S is controlled in 16 p and 11 p go 7 p and 20 p, respectively. Hence, for 1 S and 3 S to be marked, 17 p and 2 must be both marked since p 16 17 =SS p and 362 =SS p. Now, both 4 p an26 p are marked e d un sinc 5 pp Hp, 417 1 , 13 Hp , and 226 ,pp 015 013 ==1p MpBut then S isnmark contradicting the fact that M. each o adding a monitor. Thus, the assum ked is incorrect and we pr 2 u f S 6 ove that S ed is controlled by 2 ption that S becomes unmar 0 is con Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL. 316 Ta , [Sble 3. Eight SMS S] and in Figure 2. S [S] p3, p4, p7, p8, p9, p10 S1 t1 – t3 + t7 – t10 S2 p2, p3, p8, p9, p10 21, p23, p24, p25 , p17, pt2 – t4 + – t17 t13 S3 p 20, p21, p23, p24, p25, p26 – t8 + t14 – t16 + t18 S4 p3, p8, p9, p10 t2 – t3 – t4 + t7 S5 p21, p23, p24, p25 –t8 + t13 – t17 + t18 S6 p2, p3, p4, p7, p8, p921, p23 , p24, p25, p26 , p10, p17, p20, pt1 – t10 + t14 – t16 S7 p2, p3, p4, p7, , p23, p24, p25 p8, p9, p10, p17, p21 t1 – t10 + t13 – t17 S8 p2, p3, p8, p9, p10, p17, p20, p21, p23 , p24, p25, p26 t2 – t4 + t14 – t16 Table 4. Disturbancess control model of the net in Figure 2. S Monitor le S V S V M0 S1 + c − 1 V1 t 3, t10 t 1, t7 a + b S2 V 2 t 4, t2, t13 b + c + d + e − 1 a + b +− 1 a + b− 1 17 t S3 V 3 t 8, t16 t 14, t18 d + e + f − 1 S4 V 4 t 3, t4 t 2, t7 b + c − 1 S5 V 5 t 8, t17 t 13, t18 d + e − 1 S6 V 6 t 10, t16 t 1, t14 c + d + e + f S7 V 7 t 10, t17 t 1, t13 + c + d + e S8 V 8 t 4, t16 t 2, t14 b + c + d + e + f − 1 trolled. Alternatively, we will prove based on the following bservations from Table 3 that: o 6 12345 =SSSSSS, 7124 =SSSS, and 823 =SSSS. 5 In general, ifj , then e following theorem. Theorem 5. Let be be a dependent S elementary siphons d where 0=1 =1 = nm SiSnjS in ij ab nm nj nj bS or =1 n nm inj S j b shown in th S 0=1 =i SS i a 0 =1 =1 =ii ij aS j as a net system and 00 NM, MS w.r.t. 2n S, ···, an 0 S 1 S, 2 S, ···, S, S, n1nnm 0=1 == nm SiSnjSab ab S =1 in j ij , =1 = n ai i a S i , and = b =1 n j m S j b . Then 1) 0121 2 ,,,,, ,,, nn nnm SSSS SSSS []SS , = (characteristic Tvector of the com tary set of siphon S equals the negative of that of pen ). 2) lem S 0=1 =1 = nm inj SS S inj ij ab , where , i a j bR(set of real numbers), a 1, 2,,in nd 1, 2j,,m (characteristic Pvectors of the comple mentary sets of siphon S, 1 S, 2 S, ···, n S, n S, 1 2n S , ···, nm S follow th 3) The Marking Equality (ME) holds:, of siphon e sam eristic Tvect e equation as that ors). of the corresponding charact 0 =1 =, , j MS MRNM =1 0 nm iinj nj i aMSbM S (1) (total tokens in the complementary sets , S, ···, S, S S, 1 S2n1n , S2n , ···, S follow t nmhe sa equation as that rresponding character me istic of the co Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL.317 Tvectors). Proof. 1) RrS R SSS Hr variant is the sup port of a Pin based on Property 1 and SS. Note that R SSP . pS S s , 1Ip (valid for OPN); otherwise, =0Ip. Thu, =SS I . ==0 TTT SS IN N (By the definition of Pinvariant), where 0 is a vector with all components b controlled, we have 00 max SMS or 0 =1 =1 max m nm iinj nj ij MSaM SbMS in (2) To be conseve, the term associated with the negative terms is set to zero0 N rvati . That is, if eing 0. = SS on equation 0b . 2) Based = Sa , the factt tha = SS and = TT N , we have 0=1 = nm i SS i ab SS =1 =1 0=1 =1 = =0 n j Snj ij nm TT T j inj SS S inj ij Na N bN abN 0=1 in SS S inj ij T nm If , then 0=1 =1 =0 nm inj SS S inj ij ab is a Pinvariant. However, all places in 0 S, 1 S, 2 S, ···, and nm S and he are not ma g ofnce the union of rked in the i nitial markin N 0 S, 1 S, 2 S, ···, and nm S m cannot be the Pinvariant. This i support of a plies that 0 0= nm inj SSS inj ab . =1 =1ij 3 Multiplyingoth sides of the equation in Equation (1) by T ) b , w have 0=1 = nm TT T i SS in MaM e =1 0 =1 =1 =. n j Sj ij nm i injnj ij b M MSaMSbMS This theorem holds for FMS modeled by OPN [not Genera (GPN)] sl PNuch as an S3PMR since we have assumed pS S, 1Yp odeled by GP . However, it can be extendedN such as S4PR and S3PGR2 to FMS m by replacing with W((M(A))), the weighted sum of tokens in S or [S]. This ME says that the total number of tokens trapped in [0 S] and [i S], follow the same linear algebraic relationship between 0 S and Si , i = 1, 2, ···, n, n + 1, ···, n +ically, m. This is becase puhys St is the number of tokens removed from S by firing t once. Now, max =1 ii tM SS 0 M (i S is said to be limit controlled) for i Sve tokens. In order for to be to ha0 S S than max ( =1 n ii i aM S holds. not hold that s large i enough to be greater), then Equa tion (2) necessarily However it may 0101202 11 n MSa MSaMS 0 11 nn i aMS S 0 =1 =i i n aM 0=1i =aMi a y not be controlled when After lowering That isma each is limit controlled. 0 S i S i S to 0 MS iS i , 1 Si where Si is the c in Li and Zhou [13], fo ontropth r each , it may hold that l de i S variable mentioned 01202 = n i Sa MS aM 01 SS MSa M 12 00 =1 0 =. nn S i ni i aM aMS S S This is exa the MLI (marking lin In the sequel, we do not negative terms to zero; t controllability. d 5 S (resp. 6 S, 7 S, and d) siphons; they are lim ctlyear inequality mentioned in [13]). set the term associated with theherefore achieving a better , , ···, an) are . compound 1 S basic (re by setting 2 S sp 8 S itcontrolle 01 S=1 Vabc , 02=1 S Vbcde , 03=1 S Vdef , 04=1 S Vbc , and 05=1 S Vde. 06 = S abcde , = 07 Sbcdef , and 08 = Sabcde f . Table 4 shows the disturbaf thnceless control model oe net in Figure 2. iS i max 0 = SMV, i =, 2, ···, 5, and 1 max 7maxn 4 =1max 2mi SMS SMSM part 3 oemma 1) 1 1 bcde c (by Theorem 4 and f L = abc =2abcdeb . Thus, is limfor control 7 Sitc ontrolled (no need Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL. 318 elements) iff 07max 7 SM S 7 S to be limitcont ==3b, of whichone toke 12 21 ps 2 S are marked ( oth S andS are one ontrol e ntr ility , which implies d control elemrolled. For instance, n goes to since Simila co that b < 2 or 013 ==1bMp . On the other hand, if b > 1, we need to ad ents for 3 ns to b rly, an 01 Mp two toke p , 4 p d) d 17 p, also a tokens in 16 p to 5 p and e tokens in p to . Thi makes 7 S emptied and yet both 1 S and consistent with the fact that 1 2 17 1 S and 42 pS and both 4 p and 17 p are marked. can argue that 8 S is limitcontrolled (no need for c elemnts) iff 013 =1Mp Now nsider the coollab of 6 S. controlle . max 61max2max 3 4 min = max min 5 SMS SMS SM M M 1 = def ce abcde f S (b 1 3 y Part 3 of Theorem 4) =1abcbcd e bd (by Part 3 of Lemma 1). where min4= Sc and 5= min Sd ntrol ele . Thus, is liments) 6 S mitco ntrolled (no need for co iff 06max 6 SM 3= S , which imp 013 015 ===pdMp 1 and lies that =1 . If bd 30 n bd ==1, theor bd bM 06 MS M max 6 S =1, other wise, 3bd and 06max 6 SM s rived the controllability fo eapendent siph at they he the same co proves the conservativ ao, “A GraphicAlgebr Siphons of BS3PR,” Jour ineering, Vol. 23, No. 6 . S; 6 S is emptie 6. Csion We hstrongly (SDS) akly deS It is surprisedavus, his paper im d. on avr both ons (WD). ntrollability. Th e control policy for aic Computation of Ele mentar nal of Information Sci , 2007, pp. 1817 , Vol. 2, No. 2, 2007, 1080/00207540701747210 clu e de nd w th y pp. 168179 t WDS in [8]. 7. References [1] D. Y. Chao, “Computation of Elementary Siphons in Petri Nets for Deadlock Control,” The Computer Journal, Vol. 49, No. 4, 2006, pp. 470479. [2] D. Y. Ch ence and Eng 1831. [3] D. Y. Chao, “Incremental Approach to Computation of Elementary Siphons for Arbitrary S3PR,” IEE Proceed ings Control Theory & Applications [4] D. Y. Chao, “Technical NoteReaching More States for Control of FMS,” International Journal of Production Research, Vol. 48, No. 4, 2008, pp. 12171220. doi:10. 9, No. 34, 2008, pp. 317318. [5] D. Y. Chao, “Comments on Deadlock Prevention and Avoidance in FMS: A Petri Net Based Approach,” The International Journal of Advanced Manufacturing Tech nology, Vol. 3 doi:10.1007/s001700071190x [6] D. Y. Chao, “An Incremental Approach to Extract Mini mal Bad Siphons,” Journal of Information Scien Engineering, Vol. 23, No. 1, 2007, ce and pp. 203214. [7] D. Y. Chao, “Revised Dependent Siphons,” The Interna tional Journal of Advanced Manufacturing Technology, Vol. 43, No. 1, 2009, pp. 182188, doi:10.1007/s0017000816841 [8] D. Y. Chao, “Conservative Control Policy for Weakly ptimal Siphon and a WellKnown S3PR,” Dependent Siphons in S3PR Based on Elementary Si phons,” IET Control Theory & Applications, Vol. 4, No. 7, 2010, pp. 12981302. [9] D. Y. Chao, “Structure of Weakly Dependent Siphons,” Unpublished Manuscript. [10] D. Y. Chao, “Improvement of Subo FBMBased Control Model of IEEE Transactions on Automation Science and Engi neering, Vol. 8, No. 2, 2011, pp. 404411. doi:10.1109/TASE.2010.2088120 [11] J. Ezpeleta, J. M. Colom and J. Martinez, “A Petri Net Transactions on Robotics and Based Deadlock Prevention Policy for Flexible Manu facturing Systems,” IEEE Automation, Vol. 11, No. 2, 1995, pp. 173184. doi:10.1109/70.370500 [12] M. V. Iordache, J. O. Moody and P. J. Antsaklis, “A Method for the Synthesis of Liveness Enfo visors in Petri Nets,” Proceedings rcing Super of the 2001 American ntion in Systems,” IEEE Transactions on ystems, Man, and Cybernetics Part A: Sys Systems and Hu Control Conference, Arlington, 2527 June 2001, pp. 49434948. [13] Z. W. Li and M. C. Zhou, “Elementary Siphons of Petri Nets and Their Application to Deadlock Preve Flexible Manufacturing Systems, Man, and Cybernetics Part A: Systems and Hu mans, Vol. 34, No. 1, 2004, pp. 3851. [14] Z. W. Li and M. C. Zhou, “Clarifications on the Defini tions of Elementary Siphons in Petri Nets,” IEEE Trans actions on S tems and Humans, Vol. 35, No. 6, 2006, pp. 12271229. [15] M. Uzam and M. C. Zhou, “An Iterative Synthesis Ap proach to Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Transactions on Systems, Man, and Cybernetics Part A: mans, Vol. 37, No. 3, 2007, pp. 362371. [16] Z. W. Li and M. C. Zhou, “Control of Elementary and Dependent Siphons in Petri Nets and Their Application,” IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, Vol. 38, No. 1, 2008, pp. 133148. [17] Z. W. Li and M. C. Zhou, “On Controllability of De Copyright © 2011 SciRes. ICA
D. Y. CHAO ET AL. Copyright © 2011 SciRes. ICA 319 ems, Man pendent Siphons for Deadlock Prevention in Generalized Petri Nets,” IEEE Transactions on Syst, and Cybernetics Part A: Systems and Humans, Vol. 38, No. 2, 2008, pp. 369384. doi:10.1109/TSMCA.2007.914741 [18] Z. W. Li and M. C. Zhou, “On Siphon Computation for Deadlock Control in a Class of Petri Net,” IEEE Transac tions on Systems, Man, and Cybernetics Part A: Sy p. an Part A: Systems and Humans, Vol. 39, No. 3, stems and Humans, Vol. 38, No. 3, 2008, pp. 667679. [19] L. Piroddi, R. Cordone and I. Fumagalli, “Selective Si phon Control for Deadlock Prevention in Petri Nets,” IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, Vol. 38, No. 6, 2008, p 13371348. [20] L. Piroddi, R. Cordone and I. Fumagalli, “Combined Siphon and Marking Generation for Deadlock Prevention in Petri Nets,” IEEE Transactions on Systems, M, and Cybernetics 2009, pp. 650661. [21] Y. Y. Shih and D. Y. Chao, “Sequence of Control in S3PMR,” Computer Journal, Vol. 53, No. 10, 2010, pp. 16911703. doi:10.1093/comjnl/bxp081 [22] M. Uzam, Z. W. Li and M. C. Zhou, “Identification and facturing Tech Elimination of Redundant Control Places in Petri Net Based Liveness Enforcing Supervisors of FMS,” The In ternational Journal of Advanced Manu nology, Vol. 35, No. 12, 2007, pp. 150168. doi:10.1007/s0017000607015 [23] C. F. Zhong and Z. W. Li, “Design of LivenessEnforcing Supervisors via Transforming Plant Petri Net Models of FMS,” Asian Journal of Control, Special Is “Control of Discrete Event System sue on the s”, Vol. 6, No. 2, 2010, pp. 270280.
