×

Supervisor reconfiguration for deadlock prevention by resources reallocation. (English) Zbl 1266.91042

Summary: Analysis and control of deadlocks play an important role in the design and operation of automated flexible manufacturing systems (FMSs). In FMS, deadlocks are highly undesirable situations, which always cause unnecessary cost. The design problem of an optimal supervisor is in general NP-hard. A computationally efficient method often ends up with a suboptimal one. This paper develops a deadlock prevention policy based on resources reallocation and supervisor reconfiguration. First, given a plant model, we reallocate the marking of each resource place to be one, obtaining a net model whose reachable states are much less than that of the original one. In this case, we find a controlled system for it by using the theory of regions. Next, the markings of the resource places in the controlled system are restored to their original ones. Without changing the structure of the obtained controlled system, we compute the markings of the monitors gradually, which can be realized by two algorithms proposed in this paper. Finally, we decide a marking for each monitor such that it makes the controlled system live with nearly optimal permissive behavior. Two FMS examples are used to illustrate the application of the proposed method and show its superior efficiency.

MSC:

91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] T. Murata, “Petri nets: properties, analysis and application,” Proceedings of the IEEE, vol. 77, no. 4, pp. 541-580, 1989.
[2] J. Ezpeleta, J. M. Colom, and J. Martinez, “A Petri net based deadlock prevention policy for flexible manufacturing systems,” IEEE Transactions on Robotics and Automation, vol. 11, no. 2, pp. 173-184, 1995.
[3] Z. W. Li and M. C. Zhou, “Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets,” IEEE Transactions on Industrial Informatics, vol. 2, no. 4, pp. 313-325, 2006.
[4] Z. W. Li, N. Q. Wu, and M. C. Zhou, “Deadlock control of automated manufacturing systems based on Petri nets-a literature review,” IEEE Transactions on Systems, Man, and Cybernetics C, vol. 42, no. 4, pp. 437-462, 2012.
[5] S. G. Wang, C. Y. Wang, and Y. P. Yu, “Comments on ‘siphon-based deadlock prevention policy for flexible manufacturing systems’,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 41, no. 2, pp. 338-340, 2011.
[6] S. G. Wang, C. Y. Wang, and M. C. Zhou, “Controllability conditions of resultant siphons in a class of Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 42, no. 5, pp. 1206-1215, 2012.
[7] B. Hruz and M. C. Zhou, Modeling and Control of Discrete Event Dynamic Systems, Springer, London, UK, 2007.
[8] M. D. Jeng and X. L. Xie, “Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons,” in Deadlock Resolution in Computer-Integrated Systems, M. C. Zhou and M. P. Fanti, Eds., pp. 233-281, Marcel-Dekker, New York, NY, USA, 2005.
[9] T. K. Kumaran, W. Chang, H. Cho, and A. Wysk, “A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems,” International Journal of Production Research, vol. 32, no. 10, pp. 2361-2379, 1994. · Zbl 0902.90082
[10] M. Silva and J. M. Colom, “On the computation of structural synchronic invariants in P/T nets,” in Advances in Petri Nets 1988, Springer, New York, NY, USA, 1988. · Zbl 0668.68070
[11] S. G. Wang, C. Y. Wang, M. C. Zhou, and Z. W. Li, “A method to compute strict minimal siphons in a class of Petri nets based on loop resource subsets,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 42, no. 1, pp. 226-237, 2012.
[12] Y. F. Chen and Z. W. Li, “On structural minimality of optimal supervisors for flexible manufacturing systems,” Automatica, vol. 48, no. 10, pp. 2647-2656, 2012. · Zbl 1271.93102
[13] Y. F. Chen and Z. W Li, Optimal Supervisory Control of Automated Manufacturing Systems, CRC Press, Taylor & Francis Group, New York, NY, USA, 2013.
[14] Z. W. Li and M. C. Zhou, Deadlock Resolution in Automated Manufacturing Systems: A Novel Petri Net Approach, Springer, London, UK, 2009.
[15] M. Uzam, “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, pp. 192-208, 2002.
[16] M. Uzam and M. C. Zhou, “An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems,” International Journal of Production Research, vol. 44, no. 10, pp. 1987-2030, 2006.
[17] P. K. Mishra, “Lower and upper bounds of shortest paths in reachability graphs,” International Journal of Mathematics and Mathematical Sciences, no. 57, pp. 3023-3036, 2004. · Zbl 1101.68730
[18] M. Uzam and M. C. Zhou, “An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 37, no. 3, pp. 362-371, 2007.
[19] A. Ghaffari, N. Rezg, and X. Xie, “Design of a live and maximally permissive Petri net controller using the theory of regions,” IEEE Transactions on Robotics and Automation, vol. 19, no. 1, pp. 137-142, 2003.
[20] Y. F. Chen, Z. W. Li, M. Khalgui, and O. Mosbahi, “Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 2, pp. 374-393, 2011.
[21] B. Barzegar, H. Motameni, and H. Bozorgi, “Solving flexible job-shop scheduling problem using gravitational search algorithm and colored Petri net,” Journal of Applied Mathematics, vol. 2012, Article ID 651310, 20 pages, 2012. · Zbl 1251.90114
[22] J. Ezpeleta, F. Garcła-Valls, and J. M. Colom, “A class of well structured Petri nets for flexible manufacturing systems,” in Proceedings of the 19th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, J. Desel and M. Silva, Eds., vol. 1420 of Lecture Notes in Computer Science, pp. 64-83, 1998.
[23] Y. S. Huang, M. D. Jeng, X. L. Xie, and S. L. Chung, “A deadlock prevention policy for flexible manufacturing systems using siphons,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA ’01), pp. 541-546, May 2001.
[24] Y. S. Huang, M. D. Jeng, X. L. Xie, and D. H. Chung, “Siphon-based deadlock prevention policy for flexible manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 36, no. 6, pp. 1248-1256, 2006.
[25] Z. W. Li and M. C. Zhou, “Elementary siphons of petri nets and their application to deadlock prevention in flexible manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 34, no. 1, pp. 38-51, 2004.
[26] F. Tricas, F. Garcła-Valls, J. M. Colom, and J. Ezpeleta, “An iterative method for deadlock prevention in FMSs,” in Proceedings of the 5th Workshop on Discrete Event Systems, R. Boel and G. Stremersch, Eds., pp. 139-148, 2000. · Zbl 1050.68108
[27] A. R. Wang, Z. W. Li, J. Y. Jia, and M. C. Zhou, “An effective algorithm to find elementary siphons in a class of Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 39, no. 4, pp. 912-923, 2009.
[28] K. Y. Xing, M. C. Zhou, F. Wang, H. X. Liu, and F. Tian, “Resource-transition circuits and siphons for deadlock control of automated manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 41, no. 1, pp. 74-84, 2011.
[29] L. Piroddi, R. Cordone, and I. Fumagalli, “Selective siphon control for deadlock prevention in Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 38, no. 6, pp. 1337-1348, 2008.
[30] L. Piroddi, R. Cordone, and I. Fumagalli, “Combined siphon and marking generation for deadlock prevention in Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 39, no. 3, pp. 650-661, 2009.
[31] Z. W. Li, G. Y. Liu, H. M. Hanisch, and M. C. Zhou, “Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 42, no. 1, pp. 178-191, 2012.
[32] F. Chu and X. L. Xie, “Deadlock analysis of Petri nets using siphons and mathematical programming,” IEEE Transactions on Robotics and Automation, vol. 13, no. 6, pp. 793-804, 1997.
[33] K. Barkaoui and J. F. Pradat-Peyre, “On liveness and controlled siphons in Petri nets,” in Proceedings of the 17th International Conference on Applications and Theory of Petri Nets, vol. 1091 of Lecture Notes in Computer Science, pp. 57-72, 1996.
[34] H. S. Hu, M. C. Zhou, and Z. W. Li, “Supervisor design to enforce production ratio and absence of deadlock in automated manufacturing systems,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 41, no. 2, pp. 201-212, 2010.
[35] D. Liu, Z. W. Li, and M. C. Zhou, “Liveness of an extended S3PR,” Automatica, vol. 46, no. 6, pp. 1008-1018, 2010. · Zbl 1192.93076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.