An extraction algorithm for a set of elementary siphons based on mixed-integer programming

Abstract

Elementary siphons are useful in the development of a deadlock prevention policy for a discrete event system modeled with Petri nets. This paper proposes an algorithm to iteratively extract a set of elementary siphons in a class of Petri nets, called system of simple sequential processes with resources (S3PR). At each iteration, by a mixed-integer programming (MIP) method, the proposed algorithm finds a maximal unmarked siphon, classifies the places in it, extracts an elementary siphon from the classified places, and adds a new constraint in order to extract the next elementary siphon. This algorithm iteratively executes until no new unmarked siphons can be found. It finally obtains a unique set of elementary siphons and avoids a complete siphon enumeration. A theoretical analysis and examples are given to demonstrate its efficiency and practical potentials.

Keywords

Petri net / flexible manufacturing system / deadlock prevention / mixed integer programming / elementary siphon

References

[1] Chao D.Y.. Computation of elementary siphons for deadlock control. The Computer Journal, 1999, 49(4): 470-479.

[2] Chu F., Xie X.L.. Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE Transactions on Robotics and Automation, Part A, 1997, 13(6): 793-804.

[3] Ezpeleta J., Colom J.M., Martinez J.. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation, 1995, 11(2): 173-184.

[4] Hsieh F.S., Chang S.C.. Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems. IEEE Transactions on Robotics and Automation, 1994, 10(2): 196-209.

[5] Huang Y.S., Jeng M.D., Xie X.L., Chun S.L.. Deadlock prevention policy based on Petri nets and siphons. International Journal of Production Research, 2001, 39(2): 283-305.

[6] Huang Y.S., Jeng M.D., Xie X.L., Chun D.H.. Siphon-based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2006, 36(6): 1248-1256.

[7] Li S.Y., Li Z.W., Hu H.S.. Siphon extraction for deadlock control in flexible manufacturing systems by using Petri nets. International Journal of Computer Integrated Manufacturing, 2011, 24(8): 710-725.

[8] Li Z.W., Zhou M.C.. Elementary siphons of Petrinets and their application to deadlock prevention in flexible manufacturing systems. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2004, 34(1): 38-51.

[9] Li, Z.W., Hu, H.S. & Zhou, M.C. (2004b). An algorithm for anoptimal set of elementary siphons in Petri nets for deadlock control. In: Proceedings of 2004 IEEE International Conference on Systems, Man and Cybernetics, Hague, Netherlands, October 10–13, 2004

[10] Li Z.W., Zhou M.C.. Clarifications on thedefinitions of elementary siphons of Petri nets. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2006, 36(6): 1227-1229.

[11] Li Z.W., Liu D.. A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net. International Journal of Production Research, 2007, 45(9): 2161-2165.

[12] Li Z.W., Zhou M.C.. On siphon computation for deadlock control in a class of Petri nets. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2008, 38(3): 667-679.

[13] Li Z.W., Zhou M.C.. Deadlock Resolution in Automated Manufacturing Systems, 2009, London: Springer, Inc.

[14] Lindo System, Inc. (2011). Premier optimization modeling tools. Availabe via DIALOG. http://www.lindo.com

[15] Murata, T. (1989). Petri nets: properties, analysis, and applications. In: Proceedings of the IEEE, USA, August 20–22, 1989

[16] Park J., Reveliotis S.A.. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automation Control, 2001, 46(10): 1572-1583.

[17] Peterson J.L.. Petri Net Theory and the Modeling of Systems, 1981, New Jersey: Prentice Hall, Inc.

[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, 2008, 38(6): 1337-1348.

[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, 2009, 39(3): 650-661.

[20] Starke P.H.. INA: Intergrated Net Analyzer, 1992, Germany: Handbuch

[21] Tricas F., Ezpeleta J.. Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2006, 36(3): 532-539.

[22] Uzam M., Zhou M.C.. An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Systems, Man and Cybernetics, Part A, 2007, 37(3): 362-371.

[23] Wu N.Q., Zhou M.C.. Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles. IEEE Transactions on Systems, Man and Cybernetics, Part B, 2005, 35(6): 1193-1202.