Deadlock and liveness characterization for a class of generalized Petri nets. (English) Zbl 1436.90041
Summary: Petri nets (PNs) are widely adopted for modeling flexible manufacturing systems (FMSs) since they are an effective tool for analyzing the latter’s dynamic behavior and synthesizing a supervisory controller to make a system deadlock-free. As an important subclass of PNs, the weighted system of simple sequential processes with resources (\(\mathrm{WS}^3\mathrm{PR}\)) can be used to model many FMSs well. Based on the initial marking and structural properties of a \(\mathrm{WS}^3\mathrm{PR}\) without using marking enumeration and state equations, this paper presents a method to check its liveness. We first define two classes of transitions for a resource subnet of \(\mathrm{WS}^3\mathrm{PR}\), based on which, the relationship between markings and strongly connected resource subnets (SCRSs) is analyzed. Next, functions used to check the liveness of a given \(\mathrm{WS}^3\mathrm{PR}\) are developed, which take the full advantage of SCRS trees and \(\mathrm{WS}^3\mathrm{PR}\) structure. It is shown that, by the proposed method, the computational complexity for a subclass of \(\mathrm{WS}^3\mathrm{PR}\) named \(k\)-sharing bounded \(\mathrm{WS}^3\mathrm{PR}\) is polynomial. Sufficient conditions to check liveness of a \(\mathrm{WS}^3\mathrm{PR}\) are finally established. Two examples are used to illustrate the results.
MSC:
| 90B30 | Production models |
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
References:
| [1] | Ahmad, F.; Huang, H. J.; Wang, X. L., Analysis of the Petri net model of parallel manufacturing processes with shared resources, Inf. Sci., 181(23), 5249-5266 (2011) |
| [2] | Bai, L. P.; Wu, N.; Li, Z.; Zhou, M., Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology, IEEE Trans. Syst., Man, Cybern.: A., Syst., 46(10), 1456-1467 (2016) |
| [3] | Barkaoui, K.; Pradat-Peyre, J. F., On liveness and controlled siphons in Petri nets, Proceeding International Conference on Application and Theory Petri Nets. Proceeding International Conference on Application and Theory Petri Nets, LNCS, 1091, 57-72 (1996) · Zbl 1418.68131 |
| [4] | Burnwal, S.; Deb, S., Scheduling optimization of flexible manufacturing system using cuckoo search-based approach, Int. J. Adv. Manuf. Technol., 64(5), 951-959 (2013) |
| [5] | Chan, F. T.S.; Swarnkar, R., Ant colony optimization approach to a fuzzy goal programming model for a machine tool selection and operation allocation problem in an FMS, Rob. Comput.-Integr. Manuf., 22(4), 353-362 (2006) |
| [6] | Chao, D. Y., Max′-controlled siphons for liveness of \(S^3 PGR^2\), IET Control Theory Appl., 1(4), 933-936 (2007) |
| [7] | Chen, H. F.; Wu, N. Q.; Zhou, M. C., A novel method for deadlock prevention of AMS by using resource-oriented Petri nets, Inf. Sci., 363(1), 178-189 (2016) · Zbl 1427.68187 |
| [8] | Chen, Y. F.; Li, Z. W.; Al-Ahmari, A.; Wu, N. Q.; Qu, T., Deadlock recovery for flexible manufacturing systems modeled with Petri nets, Inf. Sci., 381(1), 290-303 (2017) · Zbl 1429.90019 |
| [9] | Chen, Y. F.; Li, Z. W.; Barkaoui, K., New Petri net structure and its application to optimal supervisory control: Interval inhibitor arcs, IEEE Trans. Syst., Man, Cybern., A, Syst., Humans, 44(10), 1384-1400 (2014) |
| [10] | Chen, Y. F.; Li, Z. W.; Barkaoui, K.; Wu, N. Q.; Zhou, M. C., Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs, IEEE Trans. Syst., Man, Cybern., A, Syst., Humans, 47(2), 364-379 (2017) |
| [11] | Chen, Y. F.; Li, Z. W.; Zhou, M. C., Maximally permissive liveness-enforcing supervisor with lowest implementation cost for flexible manufacturing systems, Inf. Sci., 256(1), 74-90 (2014) · Zbl 1321.90046 |
| [12] | Colom, J. M., The resource allocation problem in flexible manufacturing systems, Proc. Int. Conf. Appl. Theory Petri Nets. Proc. Int. Conf. Appl. Theory Petri Nets, LNCS, 2679, 23-35 (2003) · Zbl 1274.90133 |
| [13] | Ezpeleta, J.; Colom, J. M.; Martinez, J., A Petri net based deadlock prevention policy for flexible manufacturing systems, IEEE Trans. Robot. Autom., 11(2), 173-184 (1995) |
| [14] | Grichi, H.; Mosbahi, O.; Khalgui, M.; Li, Z. W., New power-oriented methodology for dynamic resizing and mobility of reconfigurable wireless sensor networks, IEEE Trans. Syst., Man, Cybern., 1-11 (2017) |
| [15] | Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8(4), 538-548 (1983) · Zbl 0524.90067 |
| [16] | Lewis, F. L.; Gurel, A.; Bogdan, S.; Doganalp, A.; Pastravanu, O. C., Analysis of deadlock and circular waits using a matrix model for flexible manufacturing systems, Automatica, 34(9), 1083-1100 (1998) · Zbl 0966.90028 |
| [17] | Li, Z. W.; Liu, G. Y.; Hanisch, M-H.; Zhou, M. C., Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems, IEEE Trans. Syst., Man, Cybern., A, Syst., Humans, 42(1), 178-191 (2012) |
| [18] | Li, Z. W.; Wu, N. Q.; Zhou, M. C., Deadlock control of automated manufacturing systems based on Petri nets-A literature review, IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., 42(4), 437-462 (2012) |
| [19] | Li, Z. W.; Zhao, M., On controllability of dependent siphons for deadlock prevention in generalized Petri nets, IEEE Trans. Syst., Man, Cybern. A, Syst., Humans, 38(2), 369-384 (2008) |
| [20] | Li, Z. W.; Zhou, M. C., Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems, IEEE Trans. Syst., Man, Cybern., A, Syst., Humans, 34(1), 38-51 (2004) |
| [21] | Li, Z. W.; Zhou, M. C., Control of elementary and dependent siphons in Petri nets and their application, IEEE Trans. Syst., Man, Cybern. A, Syst., Humans, 38(1), 133-148 (2007) |
| [22] | Liu, D.; Li, Z. W.; Zhou, M. C., Liveness of an extented \(S^3\) PR, Automatica, 46(6), 1008-1018 (2010) · Zbl 1192.93076 |
| [23] | Liu, G. J.; Jiang, C. J.; Zhou, M. C.; Ohta, A., The liveness of \(WS^3\) PR: Complexity and decision, IEICE Trans. Fundam., E96-A(8), 1783-1793 (2013) |
| [24] | Liu, H. C.; You, J. X.; Li, Z. W.; Tian, G. D., Fuzzy Petri nets for knowledge representation and reasoning: A literature review, Eng. Appl. Artif. Intell., 60, 45-56 (2017) |
| [25] | Ma, Z. Y.; Li, Z. W.; Giua, A., Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints, IEEE Trans. Autom. Control, 60(2015), 1775-1785 (2015) · Zbl 1360.93431 |
| [26] | Ma, Z. Y.; Li, Z. W.; Giua, A., Characterization of admissible marking sets in Petri nets with conflicts and synchronizations, IEEE Trans. Autom. Control, 62(3), 1329-1341 (2017) · Zbl 1366.93356 |
| [27] | Ma, Z. Y.; Tong, Y.; Li, Z. W.; Giua, A., Basis marking representation of Petri net reachability spaces and its application to the reachability problem, IEEE Trans. Autom. Control, 62(3), 1078-1093 (2017) · Zbl 1366.93357 |
| [28] | Mogale, D. G.; Dolgui, A.; Kandhway, R.; Kumar, S. K.; Tiwari, M. K., A multi-period inventory transportation model for tactical planning of food grain supply chain, Comput. Indus. Eng., 110, 379-394 (2017) |
| [29] | Mogale, D. G.; Kumar, S. K., Two stage indian food grain supply chain network transportation-allocation model, IFAC-PapersOnLine, 49(12), 1767-1772 (2016) |
| [30] | Park, J.; Reveliotis, S. A., Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings, IEEE Trans. Autom. Control, 46(10), 1572-1583 (2001) · Zbl 1045.93034 |
| [31] | Reveliotis, S., On the siphon-based characterization of liveness in sequential resource allocation systems, Proc. Int. Conf. Appl. Theory Petri Nets. Proc. Int. Conf. Appl. Theory Petri Nets, LNCS, 2679, 241-255 (2003) · Zbl 1274.90138 |
| [32] | Tarjan, R. E., Depth first search and linear graph algorithms, SIAM J. Comput., 1(2), 146-160 (1972) · Zbl 0251.05107 |
| [33] | Tian, G. D.; Zhang, H. H.; Feng, Y. X.; Jia, H. F.; Zhang, C. Y.; Jiang, Z. G.; Li, Z. W.; Li, P. G., Operation patterns analysis of automotive components remanufacturing industry development in China, Journal of Cleaner Production (2017) |
| [34] | Tian, G. D.; Zhang, H. H.; Zhou, M. C.; Li, Z. W., AHP, gray correlation, and TOPSIS combined approach to green performance evaluation of design alternatives, IEEE Trans. Syst., Man, Cybern.: A, Syst., PP(99), 1-13 (2016) |
| [35] | Tong, Y.; Li, Z. W.; Giua, A., On the equivalence of observation structures for Petri net generators, IEEE Trans. Autom. Control, 61(9), 2448-2462 (2016) · Zbl 1359.93289 |
| [36] | Tong, Y.; Li, Z. W.; Seatzu, C.; Giua, A., Verification of state-based opacity using Petri nets, IEEE Trans. Autom. Control, 62(6), 2823-2837 (2017) · Zbl 1369.68265 |
| [37] | Tuncel, G.; Bayhan, G. M., Applications of Petri nets in production scheduling: A review, Int. J. Adv. Manuf. Technol., 34(7), 762-773 (2006) |
| [38] | Uzam, M.; Li, Z. W.; Gelen, G., A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems, J. Intell. Manuf., 27(5), 1111-1129 (2016) |
| [39] | Wang, S. G.; Liu, M., Comments on “Liveness of an extended \(S^3\) PR”[Automatica 46(2010) 1008-1018], Automatica, 5(8), 2199-2200 (2014) · Zbl 1297.93114 |
| [40] | Wang, X.; Khemaissia, I.; Khalgui, M.; Li, Z. W.; Mosbahi, O.; Zhou, M. C., Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks, IEEE Trans. Autom. Sci. Eng., 12(1), 258-271 (2015) |
| [41] | Wang, X.; Li, Z. W.; Wonham, W. M., Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control, IEEE Trans. Ind. Inf., 12(1), 101-111 (2016) |
| [42] | Wu, N. Q.; Bai, L. P.; Zhou, M. C., An efficient scheduling method for crude oil operations in refinery with crude oil type mixing requirements, IEEE Trans. Syst., Man, Cybern.: A., Syst., 46(3), 413-426 (2016) |
| [43] | Wu, N. Q.; Zhou, M.; Bai, L.; Li, Z. W., Short-term scheduling of crude oil operations in refinery with high-fusion-point oil and two transportation pipelines, Enterp. Inf. Syst., 10(6), 581-610 (2016) |
| [44] | Wu, N. Q.; Zhou, M. C.; Li, Z. W., Short-term scheduling of crude-oil operations: Petri net-based control-theoretic approach, IEEE Rob. Autom. Mag., 22(2), 64-76 (2015) |
| [45] | Yang, F. J.; Wu, N. Q.; Qiao, Y.; Zhou, M. C.; Li, Z. W., Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints, IEEE Trans. Syst., Man, Cybern.: A., Syst., 47(3), 502-516 (2017) |
| [46] | Ye, J. H.; Li, Z. W.; Giua, A., Decentralized supervision of Petri nets with a coordinator, IEEE Trans. Syst., Man, Cybern. A, Syst., Humans., 45(6), 955-966 (2015) |
| [47] | Yildirim, M. B.; Cakar, T.; Doguc, U.; Meza, J. C., Machine number, priority rule, and due date determination in flexible manufacturing systems using artificial neural networks, Comput. Indus. Eng., 50(1), 185-194 (2006) |
| [48] | Zhang, J. F.; Khalgui, M.; Li, Z. W.; Frey, G.; Mosbahi, O.; Salah, H. B., Reconfigurable coordination of distributed discrete event control systems, IEEE Trans. Control Syst. Technol., 23(1), 323-330 (2015) |
| [49] | Zhou, M. C.; Venkatesh, K., Modeling, Simulation and Control of Flexible Manufacturing Systems: A Petri Net Approach (1998), Singapore: World Scientific |
| [50] | Wu, N. Q.; Zhou, M. C., Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation, IEEE Trans. Autom. Sci. Eng., 9, 1, 203-209 (2012) |
| [51] | Wu, N. Q.; Zhou, M. C., Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets, IEEE Trans. Autom. Sci. Eng., 9, 2, 446-454 (2012) |
| [52] | Wu, N. Q.; Chu, F.; Chu, C. B.; Zhou, M. C., Petri net modeling and cycle time analysis of dual-arm cluster tools with wafer revisiting, IEEE Trans. Syst., Man, Cybern: Syst., 43, 1, 196-207 (2013) |
| [53] | Zhang, S. W.; Wu, N. Q.; Li, Z. W.; Qu, T.; Li, C. D., Petri net-based approach to short-term scheduling of crude oil operations with less tank requirement, Inf. Sci., 417, 247-261 (2017) · Zbl 1435.90077 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
