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
Zhou He, Ziyue Ma, Zhiwu Li and Alessandro Giua, "Parametric Transformation of Timed Weighted Marked Graphs: Applications in Optimal Resource Allocation," IEEE/CAA J. Autom. Sinica, vol. 8, no. 1, pp. 179-188, Jan. 2021. doi: 10.1109/JAS.2020.1003477
Citation: Zhou He, Ziyue Ma, Zhiwu Li and Alessandro Giua, "Parametric Transformation of Timed Weighted Marked Graphs: Applications in Optimal Resource Allocation," IEEE/CAA J. Autom. Sinica, vol. 8, no. 1, pp. 179-188, Jan. 2021. doi: 10.1109/JAS.2020.1003477

Parametric Transformation of Timed Weighted Marked Graphs: Applications in Optimal Resource Allocation

doi: 10.1109/JAS.2020.1003477
Funds:  This work was supported by the National Natural Science Foundation of China (61803246, 61703321), the China Postdoctoral Science Foundation (2019M663608), Shaanxi Provincial Natural Science Foundation (2019JQ-022 and 2020JQ-733), the Fundamental Research Funds for the Central Universities (JB190407), and the Shaanxi Key Laboratory of Complex System Control and Intelligent Information Processing, Xi’an University of Technology (SKL2020CP03)
More Information
  • Timed weighted marked graphs are a subclass of timed Petri nets that have wide applications in the control and performance analysis of flexible manufacturing systems. Due to the existence of multiplicities (i.e., weights) on edges, the performance analysis and resource optimization of such graphs represent a challenging problem. In this paper, we develop an approach to transform a timed weighted marked graph whose initial marking is not given, into an equivalent parametric timed marked graph where the edges have unitary weights. In order to explore an optimal resource allocation policy for a system, an analytical method is developed for the resource optimization of timed weighted marked graphs by studying an equivalent net. Finally, we apply the proposed method to a flexible manufacturing system and compare the results with a previous heuristic approach. Simulation analysis shows that the developed approach is superior to the heuristic approach.


  • loading
  • 1 Although several techniques that may help to speed up the approaches in [30], [31] are developed, these procedures are still subject to high computational complexity.
    2 The solutions developed in [30] and [31] for the cycle time optimization have high computational cost since they require one to solve a mixed integer linear programming for each possible equivalent TMG system.
  • [1]
    M. Ibrahim and S. Reveliotis, “Throughput maximization of complex resource allocation systems through timed-continuous-Petri-net modeling,” Discrete Event Dyn. Syst., vol. 29, no. 3, pp. 393–409, 2019. doi: 10.1007/s10626-019-00289-7
    N. Ran, H. Y. Su, and S. G. Wang, “An improved approach to test diagnosability of bounded Petri nets,” IEEE/CAA Journal of Automatica Sinica, vol. 4, no. 2, pp. 297–303, 2017. doi: 10.1109/JAS.2017.7510406
    L. Li, F. Basile, and Z. W. Li, “An approach to improve permissiveness of supervisors for GMECs in time Petri net systems,” IEEE Trans. Autom. Control, vol. 65, no. 1, pp. 237–251, 2019.
    D. Wang, X. Wang, and Z. W. Li, “Nonblocking supervisory control of state-tree Sstructures with conditional-preemption matrices,” IEEE Trans. on Ind. Inf., vol. 16, no. 6, pp. 3744–3756, 2020. doi: 10.1109/TII.2019.2939628
    N. Ran, J. Hao, Z. Dong, Z. He, Z. Liu, Y. Ruan, and S. G. Wang, “Kcodiagnosability verification of labeled Petri nets,” IEEE Access, vol. 7, pp. 185055–185062, 2019. doi: 10.1109/ACCESS.2019.2959904
    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 Journal of Automatica Sinica, vol. 6, no. 4, pp. 969–980, 2019. doi: 10.1109/JAS.2019.1911576
    J. C. Wang and D. M. Li, “Resource oriented workflow nets and workflow resource requirement analysis,” Int. J. Software Engineer. Knowledge Engineer, vol. 23, no. 5, pp. 667–693, 2013.
    F. Basile, M. P. Cabasino, and C. Seatzu, “State estimation and fault diagnosis of labeled time Petri net systems with unobservable transitions,” IEEE Trans. Autom. Control, vol. 4, no. 60, pp. 997–1009, 2015.
    R. Li and S. Reveliotis, “Performance optimization for a class of generalized stochastic Petri nets,” Discrete Event Dyn. Syst., vol. 25, no. 3, pp. 387–417, 2015. doi: 10.1007/s10626-014-0189-3
    D. Lefebvre, “Approximated timed reachability graphs for the robust control of discrete event systems,” Discrete Event Dyn. Syst., vol. 29, no. 1, pp. 31–56, 2019. doi: 10.1007/s10626-019-00275-z
    L. Pan, B. Yang, J. Q. Jiang, and M. C. Zhou, “A time Petri net with relaxed mixed semantics for schedulability analysis of flexible manufacturing systems,” IEEE Access, vol. 8, pp. 46480–46492, 2020. doi: 10.1109/ACCESS.2020.2978101
    V. M. Goncalves, C. A. Maia, and L. Hardouin, “On the steady-state control of timed event graphs with firing date constraints,” IEEE Trans. Autom. Control, vol. 61, no. 8, pp. 2187–2202, 2016. doi: 10.1109/TAC.2015.2481798
    P. Declerck, “Compromise approach for predictive control of timed event graphs with specifications defined by P-time event graphs,” Discrete Event Dyn. Syst., vol. 26, no. 4, pp. 611–632, 2016. doi: 10.1007/s10626-016-0227-4
    J. Campos, G. Chiola, J. M. Colom, and M. Silva, “Properties and performance bounds for timed marked graphs,” IEEE Trans. Fundam. Theory Appl., vol. 39, no. 5, pp. 386–401, 1992.
    J. V. Millo and R. De Simone, “Periodic scheduling of marked graphs using balanced binary words,” Theor. Comput. Sci., vol. 458, pp. 113–130, 2012. doi: 10.1016/j.tcs.2012.08.012
    B. Cottenceau, L. Hardouin, J. L. Boimond, and J. L. Ferrier, “Model reference control for timed event graphs in dioids,” Automatica, vol. 37, no. 9, pp. 1451–1458, 2001. doi: 10.1016/S0005-1098(01)00073-5
    B. Cottenceau, L. Hardouin, and J. L. Boimond, “Modeling and control of weight-balanced timed event graphs in dioids,” IEEE Trans. Autom. Control, vol. 59, no. 5, pp. 1219–1231, 2014. doi: 10.1109/TAC.2013.2294822
    J. M. Proth, N. Sauer, and X. Xie, “Optimization of the number of transportation devices in a flexible manufacturing system using event graphs,” IEEE Trans. Ind. Electron., vol. 44, no. 3, pp. 298–306, 1997. doi: 10.1109/41.585827
    Z. He, M. Liu, N. Ran, and Z. W. Li, “Firing rate optimization of deterministic timed event graphs by server performance improvement,” IEEE Access, vol. 6, pp. 70866–70873, 2018. doi: 10.1109/ACCESS.2018.2880460
    A. Giua, A. Piccaluga, and C. Seatzu, “Firing rate optimization of cyclic timed event graph,” Automatica, vol. 38, no. 1, pp. 91–103, 2002. doi: 10.1016/S0005-1098(01)00189-3
    M. Liu, Z. He, N. Q. Wu, A. Al-Ahmari, and Z. W. Li, “Resource configuration analysis for a class of Petri nets based on strongly connected characteristic resource subnets,” IEEE Access, vol. 5, pp. 26376–26386, 2017. doi: 10.1109/ACCESS.2017.2768069
    Z. W. Li and M. C. Zhou, “On siphon computation for deadlock control in a class of Petri nets,” IEEE Trans. Syst.,Man,Cybern. A,Syst.,Humans, vol. 38, no. 3, pp. 667–679, 2008. doi: 10.1109/TSMCA.2008.918605
    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. C,Appl. Rev., vol. 42, no. 4, pp. 437–462, 2012. doi: 10.1109/TSMCC.2011.2160626
    B. Cottenceau, L. Hardouin, and J. Trunk, “Weight-balanced timed event graphs to model periodic phenomena in manufacturing systems,” IEEE Trans. Autom. Sci. Eng., vol. 14, no. 4, pp. 1731–1742, 2017. doi: 10.1109/TASE.2017.2729894
    E. Teruel, P. Chrzastowski-Wachtel, J.M. Colom, and M. Silva, “On weighted T-Systems,” Appl. Theory Petri Nets, vol. 616, pp. 348–367, 1992.
    A. Munier, “Régime asymptotique optimal d’un graphe d’événements temporisé généralisé: Application à un problème d’assemblage,” RAIPOAPⅡ, vol. 27, pp. 487–513, 1992.
    M. Nakamura and M. Silva, “Cycle time computation in deterministically timed weighted marked graphs,” in Proc. 7th IEEE Int. Conf. Emerg. Tech. Factory Autom., vol. 2, pp. 1037–1046, 1999.
    N. Sauer, “Marking optimization of weighted marked graphs,” Discrete Event Dyn. Syst., vol. 13, no. 3, pp. 245–262, 2003. doi: 10.1023/A:1024055724914
    Z. He, Z. W. Li, and A. Giua, “Optimization of deterministic timed weighted marked graphs,” IEEE Trans. Autom. Sci. Eng., vol. 14, no. 2, pp. 1084–1095, 2017. doi: 10.1109/TASE.2015.2490538
    Z. He, Z. W. Li, and A. Giua, “Cycle time optimization of deterministic timed weighted marked graphs by transformation,” IEEE Trans. Control Syst. Technol., vol. 25, no. 4, pp. 1318–1330, 2017. doi: 10.1109/TCST.2016.2613967
    Z. He, Z. W. Li, and A. Giua, “Performance optimization for timed weighted marked graphs under infinite server semantics,” IEEE Trans. Autom. Control, vol. 63, no. 8, pp. 2573–2580, 2018. doi: 10.1109/TAC.2017.2766202
    J. H. van Schuppen, M. Silva, and C. Seatzu, “Control of discrete-event systems-automata and Petri net perspectives,” Lect. Notes Control Infor. Sci., Springer, vol. 433, pp. 319–340, 2012.
    M. P. Cabasino, A. Giua, and C. Seatzu, “Identification of Petri nets from knowledge of their language,” Discrete Event Dyn. Syst., vol. 17, no. 4, pp. 447–474, 2007. doi: 10.1007/s10626-007-0025-0
    A. Bemporad and M. Morari, “Control of systems integrating logic, dynamics, and constraints,” Automatica, vol. 35, no. 3, pp. 407–427, 1999. doi: 10.1016/S0005-1098(98)00178-2
    F. Basile, P. Chiacchio, and J. Coppola, “Identification of time Petri net models,” IEEE Trans. Syst.,Man,Cybern. A,Syst., vol. 47, no. 9, pp. 2586–2600, 2017. doi: 10.1109/TSMC.2016.2523929
    M. Tawarmalani and N. V. Sahinidis, “Global optimization of mixedinteger nonlinear programs: A theoretical and computational study,” Math. Program., vol. 99, no. 3, pp. 563–591, 2004. doi: 10.1007/s10107-003-0467-6
    Lindo Systems Inc., Lingo User’s Guide, 2011. [Online]. Available: http://www.lindo.com, Accessed on: Mar. 2017.
    F. Sessego, A. Giua, and C. Seatzu. “HYPENS: a Matlab tool for timed discrete, continuous and hybrid Petri nets,” in Proc. Int. Conf. Appl. Theor. Petri Nets, pp. 419–428, 2008.
    Z. He, Z. Y. Ma, and W. Tang. “Performance safety enforcement in strongly connected timed event graphs,” Automatica, under review, 2020.


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

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

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

    Figures(6)  / Tables(1)

    Article Metrics

    Article views (973) PDF downloads(56) Cited by()


    • A transformation method is developed for Timed Weighted Marked Graphs (TWMGs)
    • An analytical approach is proposed for the marking optimization problem of TWMGs
    • The proposed method is also applicable for solving cycle time optimization problem


    DownLoad:  Full-Size Img  PowerPoint