A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 8 Issue 1
Jan.  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
Shouguang Wang, Wenli Duo, Xin Guo, Xiaoning Jiang, Dan You, Kamel Barkaoui and MengChu Zhou, "Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming," IEEE/CAA J. Autom. Sinica, vol. 8, no. 1, pp. 219-226, Jan. 2021. doi: 10.1109/JAS.2020.1003210
Citation: Shouguang Wang, Wenli Duo, Xin Guo, Xiaoning Jiang, Dan You, Kamel Barkaoui and MengChu Zhou, "Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming," IEEE/CAA J. Autom. Sinica, vol. 8, no. 1, pp. 219-226, Jan. 2021. doi: 10.1109/JAS.2020.1003210

Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming

doi: 10.1109/JAS.2020.1003210
Funds:  This work was supported in part by Zhejiang Provincial Key Research and Development Program (2018C01084), Zhejiang Natural Science Foundation (LQ20F020009), and Zhejiang Gongshang University, Zhejiang Provincial Key Laboratory of New Network Standards and Technologies (2013E10012)
More Information
  • Deadlock resolution strategies based on siphon control are widely investigated. Their computational efficiency largely depends on siphon computation. Mixed-integer programming (MIP) can be utilized for the computation of an emptiable siphon in a Petri net (PN). Based on it, deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity. Due to this reason, various MIP methods are proposed for various subclasses of PNs. This work proposes an innovative MIP method to compute an emptiable minimal siphon (EMS) for a subclass of PNs named S4PR. In particular, many particular structural characteristics of EMS in S4PR are formalized as constraints, which greatly reduces the solution space. Experimental results show that the proposed MIP method has higher computational efficiency. Furthermore, the proposed method allows one to determine the liveness of an ordinary S4PR.

     

  • loading
  • [1]
    J. N. Zhou, J. C. Wang, and J. Wang, “A simulation engine for stochastic timed petri nets and application to emergency healthcare systems,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 969–980, Jul. 2019. doi: 10.1109/JAS.2019.1911576
    [2]
    M. M. Wang, G. J. Liu, P. H. Zhao, C. G. Yan, and C. J. Jiang, “Behavior consistency computation for workflow nets with unknown correspondence,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 281–291, Jan. 2018. doi: 10.1109/JAS.2017.7510775
    [3]
    D. M. Xiang, G. J. Liu, C. G. Yan, and C. J. Jiang, “Detecting data-flow errors based on Petri nets with data operations,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 251–260, Jan. 2018. doi: 10.1109/JAS.2017.7510766
    [4]
    A. Giua and C. Seatzu, “Modeling and supervisory control of railway networks using Petri nets,” IEEE Trans. Autom. Sci. Eng., vol. 5, no. 3, pp. 431–445, Jul. 2008. doi: 10.1109/TASE.2008.916925
    [5]
    Z. W. Li, N. Q. Wu, and M. C. Zhou, “Deadlock control of automated manufacturing systems based on petri nets—a literature review,” IEEE Trans. Syst. Man Cybern. Part C Appl. Rev., vol. 42, no. 4, pp. 437–462, Jul. 2012. doi: 10.1109/TSMCC.2011.2160626
    [6]
    F. J. Yang, N. Q. Wu, Y. Qiao, and R. Su, “Polynomial approach to optimal one-wafer cyclic scheduling of treelike hybrid multi-cluster tools via petri nets,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 270–280, Jan. 2018. doi: 10.1109/JAS.2017.7510772
    [7]
    G. Y. Liu and K. Barkaoui, “A survey of siphons in Petri nets,” Inf. Sci., vol. 363, pp. 198–220, Oct. 2016. doi: 10.1016/j.ins.2015.08.037
    [8]
    K. Barkaoui and I. B. Abdallah, “A deadlock prevention method for a class of FMS,” in Proc. IEEE Int. Conf. on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, Vancouver, Canada, 1995, pp. 4119–4124.
    [9]
    J. C. Luo, Z. Q. Liu, M. C. Zhou, K. Y. Xing, X. N. Wang, X. L. Li, and H. X. Liu, “Robust deadlock control of automated manufacturing systems with multiple unreliable resources,” Inf. Sci., vol. 479, pp. 401–415, Apr. 2019. doi: 10.1016/j.ins.2018.11.051
    [10]
    Y. S. Huang, M. Jeng, X. L. Xie, and S. Chung, “A deadlock prevention policy for flexible manufacturing systems using siphons,” in Proc. IEEE Int. Conf. on Robotics and Automation, Seoul, South Korea, 2001, pp. 541–546.
    [11]
    Y. S. Huang, M. Jeng, X. Xie, and D. H. Chung, “Siphon-based deadlock prevention policy for flexible manufacturing systems,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 36, no. 6, pp. 1248–1256, Nov. 2006. doi: 10.1109/TSMCA.2006.878953
    [12]
    H. W. Liao, S. Lafortune, S. Reveliotis, Y. Wang, and S. Mahlke, “Optimal liveness-enforcing control for a class of petri nets arising in multithreaded software,” IEEE Trans. Autom. Control, vol. 58, no. 5, pp. 1123–1138, May 2013. doi: 10.1109/TAC.2012.2230814
    [13]
    Z. W. Li and M. C. Zhou, “Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 34, no. 1, pp. 38–51, Jan. 2004. doi: 10.1109/TSMCA.2003.820576
    [14]
    L. Piroddi, R. Cordone, and I. Fumagalli, “Combined siphon and marking generation for deadlock prevention in petri nets,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 39, no. 3, pp. 650–661, May 2009. doi: 10.1109/TSMCA.2009.2013189
    [15]
    X. Guo, S. G. Wang, D. You, Z. F. Li, and X. N. Jiang, “A Siphon-based deadlock prevention strategy for S3PR,” IEEE Access, vol. 7, pp. 86863–86873, Jun. 2019. doi: 10.1109/ACCESS.2019.2920677
    [16]
    K. Y. Xing, M. C. Zhou, H. X. Liu, and F. Tian, “Optimal petri-net-based polynomial-complexity deadlock-avoidance policies for automated manufacturing systems,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 39, no. 1, pp. 188–199, Jan. 2009. doi: 10.1109/TSMCA.2008.2007947
    [17]
    S. G. Wang, C. Y. Wang, and M. C. Zhou, “Controllability conditions of resultant siphons in a class of petri nets,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 42, no. 5, pp. 1206–1215, Sep. 2012. doi: 10.1109/TSMCA.2011.2170419
    [18]
    D. You, S. Wang, and M. Zhou, “Synthesis of monitor-based liveness-enforcing supervisors for S3PR with ξ-resources,” IEEE Trans. Syst. Man Cybern. Syst., vol. 45, no. 6, pp. 967–975, Jun. 2015. doi: 10.1109/TSMC.2014.2376476
    [19]
    H. S. Hu, Y. Liu, and L. Yuan, “Supervisor simplification in FMSs: Comparative studies and new results using petri nets,” IEEE Trans. Control Syst. Technol., vol. 24, no. 1, pp. 81–95, Jan. 2016. doi: 10.1109/TCST.2015.2420619
    [20]
    Y. Yang and H. S. Hu, “A distributed control approach to automated manufacturing systems with complex routes and operations using petri nets,” IEEE Trans. Syst. Man Cybern. Syst., to be published.
    [21]
    C. F. Zhong, W. L. He, Z. W. Li, N. Q. Wu, and T. Qu, “Deadlock analysis and control using Petri net decomposition techniques,” Inf. Sci., vol. 482, pp. 440–456, May 2019. doi: 10.1016/j.ins.2019.01.029
    [22]
    H. X. Liu, K. Y. Xing, W. M. Wu, M. C. Zhou, and H. L. Zou, “Deadlock prevention for flexible manufacturing systems via controllable siphon basis of petri nets,” IEEE Trans. Syst. Man Cybern. Syst., vol. 45, no. 3, pp. 519–529, Mar. 2015. doi: 10.1109/TSMC.2014.2347267
    [23]
    H. X. Liu, K. Y. Xing, M. C. Zhou, L. B. Han, and F. Wang, “Transition cover-based design of petri net controllers for automated manufacturing systems,” IEEE Trans. Syst. Man Cybern. Syst., vol. 44, no. 2, pp. 196–208, Feb. 2014. doi: 10.1109/TSMC.2013.2238923
    [24]
    G. Y. Liu, L. C. Zhang, L. Chang, A. Al-Ahmari, and N. Q. Wu, “Robust deadlock control for automated manufacturing systems based on elementary siphon theory,” Inf. Sci., vol. 510, pp. 165–182, Feb. 2020. doi: 10.1016/j.ins.2019.09.018
    [25]
    R. Cordone, L. Ferrarini, and L. Piroddi, “Enumeration algorithms for minimal siphons in Petri nets based on place constraints,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 35, no. 6, pp. 844–854, Nov. 2005. doi: 10.1109/TSMCA.2005.853504
    [26]
    S. G. Wang, D. You, C. Seatzu, and A. Giua, “Complete enumeration of minimal siphons in ordinary Petri nets based on problem partitioning,” in Proc. 54th IEEE Conf. on Decision and Control, Osaka, Japan, 2015, pp. 356–361.
    [27]
    I. B. Abdallah and H. A. ElMaraghy, “Deadlock prevention and avoidance in FMS: A petri net based approach,” Int. J. Adv. Manuf. Technol., vol. 14, no. 10, pp. 704–715, Oct. 1998. doi: 10.1007/BF01438223
    [28]
    K. Barkaoui and B. Lemaire, “An effective characterization of minimal deadlocks and traps in Petri nets based on graph theory,” Proc. 10th Int. Conf. on Application and Theory of Petri Nets, France, 1989.
    [29]
    E. R. Boer and T. Murata, “Generating basis siphons and traps of Petri nets using the sign incidence matrix,” IEEE Trans. Circ Syst. I Fundam. Theory Appl., vol. 41, no. 4, pp. 266–271, Apr. 1994. doi: 10.1109/81.285680
    [30]
    F. Tricas, J. M. Colom, and J. J. Merelo, “Computing minimal siphons in Petri net models of resource allocation systems: An evolutionary approach,” in Proc. Int. Workshop on Petri Nets and Software Engineering, Tunis, Tunisia, 2014, pp. 307–322.
    [31]
    F. Tricas, J. M. Colom, and J. J. Merelo, “Using the incidence matrix in an evolutionary algorithm for computing minimal siphons in Petri net models,” in Proc. 18th Int. Conf. on System Theory, Control and Computing, Sinaia, Romania, 2014, pp. 645–651.
    [32]
    Y. F. Chen and G. Y. Liu, “Computation of minimal siphons in Petri nets by using binary decision diagrams,” ACM Trans. Embed. Comput. Syst., vol. 12, no. 1, pp. 1–15, Jan. 2013.
    [33]
    P. H. Starke, INA: Integrated Net Analyzer, 1992. [Online]. Available: http://www2.informatik.hu-berlin.de/~starke/ina.html.
    [34]
    E. E. Cano, C. A. Rovetto, and J. M. Colom, “An algorithm to compute the minimal siphons in S4PR nets,” Discrete Event Dyn. Syst., vol. 22, no. 4, pp. 403–428, Feb. 2012. doi: 10.1007/s10626-012-0132-4
    [35]
    F. Tricas and J. Ezpeleta, “Computing minimal siphons in Petri net models of resource allocation systems: A parallel solution,” IEEE Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 36, no. 3, pp. 532–539, May 2006. doi: 10.1109/TSMCA.2005.855751
    [36]
    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 Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 42, no. 1, pp. 226–237, Jan. 2012. doi: 10.1109/TSMCA.2011.2159590
    [37]
    K. 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 Trans. Syst. Man Cybern. Part A Syst. Hum., vol. 41, no. 1, pp. 74–84, Jan. 2011. doi: 10.1109/TSMCA.2010.2048898
    [38]
    D. You, S. G. Wang, and M. C. Zhou, “Computation of strict minimal siphons in a class of Petri nets based on problem decomposition,” Inf. Sci., vol. 409-410, pp. 87–100, Oct. 2017. doi: 10.1016/j.ins.2017.05.011
    [39]
    D. You, S. G. Wang, W. Z. Dai, W. H. Wu, and Y. S. Jia, “An approach for enumerating minimal siphons in a subclass of petri nets,” IEEE Access, vol. 6, pp. 4255–4265, Feb. 2018. doi: 10.1109/ACCESS.2017.2763783
    [40]
    F. Chu and X. L. Xie, “Deadlock analysis of Petri nets using siphons and mathematical programming,” IEEE Trans. Robot. Autom., vol. 13, no. 6, pp. 793–804, Dec. 1997. doi: 10.1109/70.650158
    [41]
    Y. S. Huang, M. Jeng, X. L. Xie, and S. Chung, “Deadlock prevention policy based on Petri nets and siphons,” Int. J. Prod. Res., vol. 39, no. 2, pp. 283–305, 2001. doi: 10.1080/00207540010002405
    [42]
    Z. W. Li and D. Liu, “A correct minimal siphons extraction algorithm from a maximal unmarked siphon of a Petri net,” Int. J. Prod. Res., vol. 45, no. 9, pp. 2161–2165, May 2007. doi: 10.1080/00207540500464942
    [43]
    C. F. Zhong and Z. W. Li, “A deadlock prevention approach for flexible manufacturing systems without complete siphon enumeration of their Petri net models,” Eng. Comput., vol. 25, no. 3, pp. 269–278, Sep. 2009. doi: 10.1007/s00366-008-0122-1
    [44]
    F. Tricas, F. García-Vallés, J. M. Colom, and J. Ezpeleta, “An iterative method for deadlock prevention in FMS,” in Discrete Event Systems: Analysis and Control, R. Boel and G. Stremersch, Eds. Boston, USA: Springer, 2000, pp. 139–148.
    [45]
    J. Park and S. A. Reveliotis, “Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings,” IEEE Trans. Autom. Control, vol. 46, no. 10, pp. 1572–1583, Oct. 2001. doi: 10.1109/9.956052
    [46]
    G. Liu and Z. Li, “General mixed integer programming-based liveness test for system of sequential systems with shared resources nets,” IET Control Theory Appl., vol. 4, no. 12, pp. 2867–2878, Dec. 2010. doi: 10.1049/iet-cta.2009.0557
    [47]
    M. D. Gan, S. G. Wang, Z. J. Ding, M. C. Zhou, and W. H. Wu, “An improved mixed-integer programming method to compute emptiable minimal siphons in S3PR nets,” IEEE Trans. Control Syst. Technol., vol. 26, no. 6, pp. 2135–2140, Nov. 2018. doi: 10.1109/TCST.2017.2754982
    [48]
    F. Tricas, “Analysis, prevention and avoidance of deadlocks in sequential resource allocation systems,” Ph.D. dissertation, Universidad de Zaragoza, Zaragoza, Spain, 2003.
    [49]
    F. Tricas, J. M. Colom, and J. Ezpeleta, “A solution to the problem of deadlocks in concurrent systems using Petri nets and integer linear programming,” in Proc. 11th European Simulation Symp., Erlangen, Germany, 1999.
    [50]
    S. G. Wang, D. You, and M. C. Zhou, “A necessary and sufficient condition for a resource subset to generate a strict minimal siphon in S4PR,” IEEE Trans. Autom. Control, vol. 62, no. 8, pp. 4173–4179, Aug. 2017. doi: 10.1109/TAC.2017.2677859
    [51]
    M. D. Gan, “The data for testing our method. [Online]. Available: https://pan.baidu.com/s/1aRmWssqshjmIO6Z01ssb7g, April 20, 2020.
    [52]
    J. Li, M. Zhou, and X. Dai, “Reduction and refinement by algebraic operations for Petri net transformation,” IEEE Trans. Systems, Man, and CyberneticsPart A: Systems and Humans, vol. 42, no. 5, pp. 1244–1255, Sept. 2012.
    [53]
    J. Li, X. Meng, M. Zhou, and X. Dai, “A two-stage approach to path planning and collision avoidance of multibridge machining systems,” IEEE Trans. Systems, Man, and Cybernetics: Systems, vol. 47, no. 7, pp. 1039–1049, July 2017.
    [54]
    G. Y. Liu, P. Li, Z. W. Li, and N. Q. Wu, “Robust deadlock control for automated manufacturing systems with unreliable resources based on Petri net reachability graphs,” IEEE Trans. Syst., Man, Cybern., Syst., vol. 49, no.7, pp. 1371–1385, 2019.
    [55]
    D. You, S. G. Wang, and C. Seatzu, “Verification of fault-predictability in labeled Petri nets using predictor graphs,” IEEE Trans. Autom. Control., vol. 64, no. 10, pp. 4353–4360, Oct. 2019.
    [56]
    C. Pan, M. Zhou, Y. Qiao, and N. Q. Wu, “Scheduling cluster tools in semiconductor manufacturing: recent advances and challenges,” IEEE Trans. Autom. Science and Engineering, vol. 15, no. 2, pp. 896–899, April. 2018.
    [57]
    J. Wang, H. Hu, C. Pan, Y. Zhou, Yuan, and L. Li, “Scheduling dual-arm cluster tools with multiple wafer types and residency time constraints,” IEEE/CAA J. Autom. Sinica. vol. 7, no. 3, pp. 776–789, May 2020.
    [58]
    J. Wang, C. Pan, H. Hu, L. Li, and Y. Zhou, “A cyclic scheduling approach to single-arm cluster tools with multiple wafer types and residency time constraints,” IEEE Trans. Autom. Science and Engineering, vol. 16, no. 3, pp.1373–1386, May 2019.
    [59]
    N. Wu and M. Zhou, “Deadlock resolution in automated manufacturing systems with robots,” IEEE Trans. Autom. Science and Engineering, vol. 4, no. 3, pp. 474–480, July. 2007.
    [60]
    Y. Xia, X. Luo, J. Li, and Q. Zhu, “A petri-net-based approach to reliability determination of ontology-based service compositions,” IEEE Trans. Systems, Man, and Cybernetics: Systems, vol. 43, no. 5, pp. 1240–1247, 2013.
    [61]
    W. Q. Xiong, C. R. Pan, Y. Qiao, N. Q. Wu, M. X. Chen, and P. H. Hsieh, “Reducing wafer delay time by robot idle time regulation for single-arm cluster tools,” IEEE Trans. Autom. Science and Engineering, DOI: 10.1109/TASE.2020.3014078, 2020.
    [62]
    F. Yang, N. Wu, Y. Qiao, M. Zhou, and Z. Li, “Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints,” IEEE Trans. Systems, Man, and Cybernetics: Systems, vol. 47, no.3, pp. 502–516, Mar. 2017.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(2)  / Tables(1)

    Article Metrics

    Article views (912) PDF downloads(59) Cited by()

    Highlights

    • Deadlock control strategies
    • Discrete event systems
    • Mixed integer programming

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return