Controllability of Weakly Dependent Siphons under Elementary-Siphon Control

Abstract:

Monitors are added upon problematic siphons to avoid deadlocks. Li and Zhou add monitors to elementary siphons only while controlling the rest dependent siphons to save cost. After failing a Marking Linear Inequality (MLI) test, they perform a Linear Integer Programming (LIP) test (NP-hard). We proposed a new MLI test earlier to avoid the LIP and extended it to S3PGR2 (systems of simple sequential processes with general resource requirements) for strongly dependent siphons (SDS). The control policy for weakly dependent siphons (WDS) is rather conservative due to some negative terms in the MLI. This paper shows that WDS and SDS have the same controllability (i.e., MLI). As a result, the control for WDS needs no longer be that conservative. We also develop an optimization (by redundancy elimination) of the computation required for LIP test to ensure deadlock prevention of S3PR (Systems of Simple Sequential Processes with Resources). A favorable result for this policy is that any n-dependent (n>2) WDS (similar to SDS) needs no monitor and hence the complexity for synthesizing a controller becomes polynomial.

• Periodical: Applied Mechanics and Materials (Volumes 373-375)
• Pages: 1413-1427
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.373-375.1413
• Online since: August 2013
• Authors: Daniel Y. Chao, Jiun Ting Chen, Ju Sheng Huang
• Keywords: Petri Net, S³PR, Siphons

References

[1] T. K. Kumaran, W. Chang, H. Cho, and A. Wysk (1994). A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems, International Journal of Production Research, 32(10), 2361-2379.

DOI: 10.1080/00207549408957073

[2] Wysk, R.A., Y.N. Shu and J. Sanjay (1994), Resolution of deadlocks in flexible manufacturing systems: avoidance and recovery approaches, Journal of Manuf. Syst., 13(2), 128-136.

DOI: 10.1016/0278-6125(94)90028-0

[3] B. Abdallah and H. A. ElMaraghy (1998). Deadlock prevention and avoidance in FMS: A Petri net based approach, International Journal of Advanced Manufacturing Technology, 14(10), 704-715.

DOI: 10.1007/bf01438223

[4] Lautenbach, K. and H. Ridder (1996). The Linear Algebra of Deadlock Avoidance-A Petri Net Approach, Univ. Koblenz, Res. Rep. Insti. Comput. Sci., Koblenz, Germany.

[5] Chao, D. Y. (2001).

[6] Chao, D. Y. (2006). Computation of Elementary Siphons in Petri Nets for Deadlock Control. Comp. J., (British Computer Society), 49(4), 470-479.

DOI: 10.1093/comjnl/bxl019

[7] Chao, D. Y. (2007). A graphic-algebraic computation of elementary siphons of BS3PR. J. Info. Sci. and Eng., 23(6), 1817-1831.

[8] Ehrenfeucht, A. and G. Rozenberg (1990). Partial (set) 2-structures; part I: basic notions and the representation problem. Acta Informatica, 27, 315-342.

DOI: 10.1007/bf00264611

[9] Ezpeleta, J., J. M. Colom and J. Martinez, (1995). A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Trans. Robot. Automat., 11, 173-184.

DOI: 10.1109/70.370500

[10] Li, Z. W. and M. C. Zhou. (2004). Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems. IEEE Trans. Syst., Man, Cybern. A., 34(1), 38-51.

DOI: 10.1109/tsmca.2003.820576

[11] Iordache, M. V., J. O. Moody and P. J. Antsaklis. (2001). A method for the synthesis liveness enforcing supervisors in Petri nets. In Proc. Amer. Control Conf., 4943-4948.

DOI: 10.1109/acc.2001.945768

[12] Huang, Y. S. (2007). Design of deadlock prevention supervisors for FMS using Petri nets. Int J Adv Manuf Technol., 35(3-4), 349-362.

DOI: 10.1007/s00170-006-0708-y

[13] Li, Z. W. and M. C. Zhou. (2006a). Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Transactions on Industrial Informatics, 2(4), 313-325.

DOI: 10.1109/tii.2006.885185

[14] Li, Z. W. and M. C. Zhou. (2006b). Clarifications on the Definitions of Elementary Siphons in Petri Nets. IEEE Trans. Syst., Man, Cybern., A: Systems and Humans, 36(6), 1227-1229.

DOI: 10.1109/tsmca.2006.878966

[15] Li, Z. W. and M. C. Zhou. (2008a). Control of Elementary and Dependent Siphons in Petri Nets and their Application. IEEE Trans. on Systems, Man, and Cybernetics: Part A, 38(1), 33-148.

DOI: 10.1109/tsmca.2007.909548

[16] Li, Z. W. and M. Zhao (2008b). On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 38(2), 369-384.

DOI: 10.1109/tsmca.2007.914741

[17] Li, Z. W. and M. C. Zhou. (2008c). On Siphon Computation for Deadlock Control in a Class of Petri Nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Human, 38(3), 667-679.

DOI: 10.1109/tsmca.2008.918605

[18] Uzam, M. and M. C. Zhou (2006). An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems. Int J Prod Res 44(10), 1987-(2030).

DOI: 10.1080/00207540500431321

[19] Chao, D. Y. (2010a). Improved controllability test for dependent siphons in S3PR based on elementary siphons. Asian Journal of Control, 12(3), 377 - 391, doi: 10. 1002/asjc. 217.

DOI: 10.1002/asjc.217

[20] Chao, D. Y. (2010b). Conservative Control Policy for Weakly Dependent Siphons in S3PR Based on Elementary Siphons. IET Control Theory and Applications, 4(7), 1298-1302.

DOI: 10.1049/iet-cta.2009.0118

[21] Chao, D. Y. (2010c). Fewer Monitors and More Efficient Controllability for Deadlock Control in S3PGR2 (systems of simple sequential processes with general resource requirements). Comp. J., (British Computer Society), doi: 10. 1093/comjnl/bxq007.

DOI: 10.1093/comjnl/bxq007

[22] Chao, D. Y. (2011). Structure Of Weakly 2-Dependent Siphons. manuscript, 2011(see Appendix I).