Open Problems in Deadlock Control for Flexible Manufacturing Systems by Using Petri Nets

Abstract:

Deadlocks are a rather undesirable situation in a highly automated flexible manufacturing system. Their occurrences often deteriorate the utilization of resources and may lead to catastrophic results in safety-critical systems. This work surveys the open problems in deadlock control for automated manufacturing systems. The focus is deadlock prevention due to its large and continuing stream of efforts. A control strategy is evaluated in terms of computational complexity, behavioral permissiveness, and structural complexity of its deadlock-free supervisor. This study provides readers with a conglomeration of the open problems in this area and facilitates them in finding a suitable topic for their research.

• Periodical: Applied Mechanics and Materials (Volumes 88-89)
• Pages: 134-141
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.88-89.134
• Online since: August 2011
• Authors: Zhi Wu Li, Abdulrahman M. Al-Ahmari
• Keywords: Deadlock Avoidance, Deadlock Prevention, Discrete Event System, Flexible Manufacturing System, Petri Net

References

[1] Barkaoui, K., Pradat-Peyre, J. F.: On liveness and controlled siphons in Petri nets. In Proceedings of the 17th International Conference on Applications and Theory of Petri Nets, LNCS, vol. 1091, Osaka, Japan, New York: Springer. (1996) 57–72.

DOI: 10.1007/3-540-61363-3_4

[2] Chen, Y. F., Li, Z. W., Khalgui, M., Mosbahi, O.: Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. to appear in IEEE Transactions on Automation Science and Engineering. (2010).

DOI: 10.1109/tase.2010.2060332

[3] Chen, Y. F., Li, Z. W.: Design of a maximally permissive liveness-enforcing Petri net supervisor with a compressed supervisory structure for flexible manufacturing systems. to appear in Automatica. (2010).

DOI: 10.1016/j.automatica.2011.01.070

[4] Fanti, M. P., Zhou., M. C.: Deadlock control methods in automated manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 34, no. 1. (2004) 5–22.

DOI: 10.1109/tsmca.2003.820590

[5] He, K. X., Lemmon, L. D.: On the transformation of maximally permissive marking-based liveness enforcing supervisors into monitor supervisors. in Proc. 39th IEEE Conference on Decision and Control, vol. 3, Sydney, NSW, Australia, Dec 12-15. (2002).

DOI: 10.1109/cdc.2000.914206

[6] He, K. X., Lemmon, M. D.: Liveness verification of discrete-event systems modeled by n-safe ordinary Petri Nets. in Proc. 21st International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol. 1825, Springer. (2000).

DOI: 10.1007/3-540-44988-4_14

[7] He, K. X., Lemmon, M. D.: Liveness-enforcing supervision of bounded ordinary Petri nets using partial order methods. IEEE Transactions on Automatic Control, vol. 47, no. 7. (2002) 1042–1055.

DOI: 10.1109/tac.2002.800641

[8] Iordache, M. V., Moody, J. O., Antsaklis, P. J.: Synthesis of deadlock prevention supervisors using Petri nets. IEEE Transactions on Robotics and Automation, vol. 18, no. 1. (2002) 59–68.

DOI: 10.1109/70.988975

[9] Lautenbach, K., Ridder, H.: Liveness in bounded Petri nets which are covered by T-invariants. in Proceedings of the 13th International Conference on Applications and Theory of Petri Nets, LNCS, vol. 815, R. Valette, Ed., Berlin: Springer-Verlag. (1994).

DOI: 10.1007/3-540-58152-9_20

[10] Lautenbach, K., Ridder, H.: The linear algebra of deadlock avoidance-a Petri net approach. No. 25-1996, Technical Report, Institute of Software Technology, University of Koblenz-Landau, Koblenz, Germany. (1996).

[11] Li, Z. W., Zhou, M. C.: Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 34, no. 1. (2004) 38–51.

DOI: 10.1109/tsmca.2003.820576

[12] Li, Z. W., Zhou, M. C.: Deadlock Resolution in Automated Manufacturing Systems: A Novel Petri Net Approach, Springer. (2009).

[13] Liu, D., Li, Z. W., Zhou, M. C.: Liveness of an extended S3PR. Automatica, vol. 46. (2010) 1008-1018.

DOI: 10.1016/j.automatica.2010.03.011

[14] McMillan, K.: Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. in Lecture Notes in Computer Science, vol. 663, B. V. Bochmann and D. K. Probst, Eds. (1992) 164–177.

DOI: 10.1007/3-540-56496-9_14

[15] McMillan, K.: Symbolic Model Checking, Norwell, Massachusetts: Kluwer. (1993).

[16] Murata, T.: Petri nets: Properties, analysis, and applications. In: Proceedings of the IEEE, vol. 77, no. 4. (1989) 541–580.

[17] Park, J., Reveliotis, S. A., Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automatic Control, vol. 46, no. 10. (2001) 1572–1583.

DOI: 10.1109/9.956052

[18] Piroddi, L., Cordone, R., Fumagalli, I.: Selective siphon control for deadlock prevention in Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 38, no. 6. (2008) 1337–1348.

DOI: 10.1109/tsmca.2008.2003535

[19] Piroddi, L., Cordone, R., Fumagalli, I.: Combined siphon and marking generation for deadlock prevention in Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 39, no. 3. (2009) 650–661.

DOI: 10.1109/tsmca.2009.2013189

[20] Qin, M., Li, Z. W., Khalgui, M., Mosbahi, O.: On applicability of deadlock prevention policies with uncontrollable and unobservable transitions. International Journal of Innovative Computing, Information, and Control, vol. 7, no. 7. (2011).

[21] Ramadge, P. J., Wonham, W. M.: The control of discrete event systems. In: Proceedings of the IEEE, vol. 77, no. 1. (1989) 81–89.

[22] Reveliotis, S. A., Lawley, M. A., Ferreira, P. M.: Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems. IEEE Transactions on Automatic Control, vol. 42, no. 10. (1997) 1344–1357.

DOI: 10.1109/9.633824

[23] Sreenivas, R. S.: On Commoner's liveness theorem and supervisory policies that enforce liveness in free-choice Petri nets. Systems Control Letters, vol. 31, no. 1. (1997) 41–48.

DOI: 10.1016/s0167-6911(97)00019-4

[24] Sreenivas, R. S.: On the existence of supervisory control policies that enforce liveness in discrete-event dynamic systems modeled by controlled Petri nets. IEEE Transactions on Automatic Control, vol. 42, no. 7. (1997) 928–945.

DOI: 10.1109/9.599972

[25] Sreenivas, R. S.: On supervisory policies that enforce liveness in completely controlled Petri nets with directed cut-places and cut-transitions. IEEE Transactions on Automatic Control, vol. 44, no. 6. (1999) 1221–1225.

DOI: 10.1109/9.769378

[26] Uzam, M.: An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. International Journal of Advanced Manufacturing Technology, vol. 19, no. 3. (2002) 192–208.

DOI: 10.1007/s001700200014

[27] Wang, A. R., Li, Z. W., Jia, J. Y., Zhou, M. C.: An effective algorithm to find elementary siphons in a class of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 39, no. 4. (2009) 912–923.

DOI: 10.1109/tsmca.2009.2019880

[28] Wu, N. Q., Zhou, M. C.: System Modeling and Control with Resource-Oriented Petri Nets, NY: CRC Press. (2009).

[29] Xing, K. Y., Zhou, M. C., Liu, H. X., Tian, F.: Optimal Petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems. IEEE Tranactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, vol. 39, no. 1. (2009).

DOI: 10.1109/tsmca.2008.2007947

[30] Zhong, C. F., Li, Z. W., On self-liveness of a class of Petri net models for flexible manufacturing systems. IET Control Theory and Applications, vol. 4, no. 3. (2010) 403–410.

DOI: 10.1049/iet-cta.2008.0193