Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

¡@

Journal of Information Science and Engineering, Vol. 23 No. 6, pp. 1817-1831 (November 2007)

A Graphic-Algebraic Computation of Elementary Siphons of BS3PR

Daniel Yuh Chao
National Chengchi University
Taipei, 116 Taiwan
E-mail: yaw@mis.nccu.edu.tw

Unlike other techniques, Li et al. add control nodes and arcs for only elementary siphons, thus reducing the number of control nodes and arcs required for deadlock control in Petri net supervisors. Their method suffers from the expensive computation of all SMS (Strict Minimal Siphons). We propose a graphic-algebra approach to compute elementary siphons without the knowledge of SMS. We show that each SMS corresponds to a strongly connected resource subnet (sub-SCC) whose characteristic T-vector £a can be computed as a linear sum of that of all resource places in the subnet. An SMS includes all resource places in the subnet plus all input operation places of transitions with positive components in £a. We propose Algorithm 2 to find all sub-SCC. We prove that any sub-SCC N¡¦, containing an elementary resource circuit c as a proper subset and N¡¦ = N¡¨ ¡å c, N¡¨ ¡ä c = {r}, corresponds to a dependent siphon. Hence, elementary siphons are closely related to (and can be constructed from) elementary (called basic) circuits and in general, combinations of elementary circuits may contribute to elementary siphons. For a simple basic subclass of S3PR (called BS3PR), the set of elementary siphons is identical to that synthesized from elementary (basic) circuits. As a result, we simplify Algorithm 2 to find all elementary circuits. It is more efficient than traditional algorithms by terminating earlier upon detecting that the net is not a BS3PR.

Keywords: flexible manufacturing systems, deadlock control, Petri nets, siphons, elementary siphons, S3PR

Retrieve PDF document (200711_11.pdf)

Received October 11, 2005; revised March 6 & May 18, 2006; accepted June 8, 2006. Received September 23, 2005; revised November 2, 2006; accepted January 9, 2007.
Communicated by Chin-Teng Lin.