Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources

Access Full Text

Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Control Theory & Applications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grows quickly and exponentially with the size of the net. They assumed that the siphon constructed from each resource circuit is an elementary one and proposed a polynomial algorithm to compute elementary siphons. However, the author demonstrates a counter example where there may be an exponential number of resource circuits. Hence, constructing elementary siphons from resource circuits will result in an exponential number of elementary siphons, which is wrong. The author then develops a polynomial algorithm to find elementary siphons, which also constructs all SMS on the way. This is because, in the method proposed by Li et al., a linear algebraic expression must be established for each dependent siphon, which implies, all SMS must be located. However, all elementary siphons with polynomial complexity can be located.

Inspec keywords: flexible manufacturing systems; linear algebra; computational complexity; Petri nets

Other keywords: elementary siphon; incremental approach; Petri net; deadlock control; flexible manufacturing system; linear algebraic expression; polynomial complexity; polynomial algorithm; strict minimal siphon

Subjects: Combinatorial mathematics; Computational complexity; Algebra; Control applications in manufacturing processes; Manufacturing systems; Algebra; Combinatorial mathematics; Control technology and theory (production)

References

    1. 1)
      • D.Y. Chao . A graphic-algebraic computation of elementary siphons of BS3PR. J. Inf. Sci. , 6 , 1817 - 1831
    2. 2)
      • Z. Li , M. Zhou . Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Trans. Ind. Inf. , 4 , 313 - 325
    3. 3)
      • D.Y. Chao , D.T. Wang . Two theoretical and practical aspects of knitting technique – invariants and a new class of Petri net. IEEE Trans. Syst. Man Cybern. , 962 - 977
    4. 4)
      • Z.W. Li , J. Zhang , M. Zhao . Liveness-enforcing supervisor design for a class of generalized Petri net models of flexible manufacturing systems. IET Control Theory Applic. , 4 , 955 - 967
    5. 5)
      • P. Kemper , M.A. Marsan . (1993) Linear time algorithm to find a minimal deadlock in a strongly connected free-choice net, ‘Application and Theory of Petri Nets’, 691, Lecture Notes in Computer Science.
    6. 6)
      • Li, Z., Hu, H., Zhou, M.: `A polynomial algorithm to find a set of elementary siphons in a class of Petri nets', Proc. IEEE Int. Conf. Syst., Man, Cybern, October 2004, The Hague, The Netherlands, p. 4861–4866.
    7. 7)
      • D.Y. Chao , Z. Li . On structural conditions of S3PR nets without weakly dependent siphons. IEEE Trans. Syst. Man Cybern. A.
    8. 8)
    9. 9)
    10. 10)
      • Li, Z., Hu, H., Zhou, M.: `An algorithm for an optimal set of elementary siphons in Petri nets for deadlock control', Proc. IEEE Int. Conf. Syst., Man, Cybern, October 2004, The Hague, The Netherlands, p. 4849–4854.
    11. 11)
      • D.Y. Chao . Petri net synthesis and synchronization using knitting technique. J. Inf. Sci. Eng. , 543 - 568
    12. 12)
      • Iordache, M.V., Moody, J.O., Antsaklis, P.J.: `A method for the synthesis liveness enforcing supervisors in Petri nets', Proc. American Control Conf., 2001, p. 4943–4948.
    13. 13)
      • D.Y. Chao . An incremental approach to extract minimal bad siphons. J. Inf. Sci. , 1 , 203 - 214
    14. 14)
    15. 15)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta_20070130
Loading

Related content

content/journals/10.1049/iet-cta_20070130
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading