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

Zhou He; Ziyue Ma; Zhiwu Li; Alessandro Giua

doi:10.1109/JAS.2020.1003477

Volume 8 Issue 1

Jan. 2021

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2021 > 8(1): 179-188

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

Citation:

PDF( 1079 KB)

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

Author Bio:
Zhou He (S’16–M’18) received the B. S. degree in mechanical engineering from the Shaanxi University of Science and Technology, Xi’an, China in 2012, the Ph. D. degree in mechatronic engineering from Xidian University, Xi’an, China in 2017, and the Ph. D. degree in automatique from Aix-Marseille University, Marseille, France in 2017. He is currently an Associate Professor with the College of Mechanical and Electrical Engineering, Shaanxi University of Science and Technology, Xi’an, China. His research interests include Petri nets, fault diagnosis, and the control and optimization of timed discrete event systems

Ziyue Ma (S’15–M’17) received the B. S. and the M. S. degrees from Peking University, China in 2007 and 2011, respectively. In 2017 he got the Ph. D. diploma in cotutorship between the School of Electro-Mechanical Engineering of Xidian University, China (mechatronic engineering), and the Department of Electrical and Electronic Engineering of University of Cagliari, Italy (electronics and computer engineering). He joined Xidian University in 2011, where he is currently an Associate Professor in the School of Electro-Mechanical Engineering. His current research interests include control theory in discrete event systems, automata and Petri nets, diagnosis and diagnosability analysis, optimization, and security in cyber-physical systems. He is a member of Technical Committee Member of IEEE Control System Society (IEEE-CSS) on Discrete Event Systems. He is serving/has served as the Associate Editor of the IEEE Conference on Automation Science and Engineering (CASE’17–CASE’20), European Control Conference (ECC’19), and IEEE International Conference on Systems, Man, and Cybernetics (SMC’19). He is/was the Track Committee Member of the International Conference on Emerging Technologies and Factory Automation (ETFA’17–ETFA’20). He received the Outstanding Reviewer Award from the IEEE Transactions on Automatic Control

Zhiwu Li (M’06–SM’07–F’16) received the B. S., M. S. and Ph. D. degrees in mechanical engineering, automatic control, and manufacturing engineering, respectively, all from Xidian University, Xi’an, China, in 1989, 1992, and 1995, respectively. He joined Xidian University in 1992 and now he is also with the Institute of Systems Engineering, Macau University of Science and Technology, Macau, China. Over the past decade, he was a Visiting Professor at the University of Toronto, Technion (Israel Institute of Technology), Israel, Martin-Luther University of Halle–Wittenburg, Germany, Conservatoire National des Arts et Métiers (CNAM), France, Meliksah Saud University, Turkey. His current research interests include Petri net theory and application, supervisory control of discrete event systems, workflow modeling and analysis, system reconfiguration, game theory, and data and process mining. He is a member of Discrete Event Systems Technical Committee of the IEEE Systems, Man, and Cybernetics Society, and a member of IFAC Technical Committee on Discrete Event and Hybrid Systems from 2011 to 2014. He serves as a frequent reviewer for 40+ international journals including Automatica and a number of the IEEE Transactions as well as many international conferences. He is listed in Marquis Who’s Who in the world, 27th Edition, 2010. He is a recipient of an Alexander von Humboldt Research Grant, Alexander von Humboldt Foundation, Germany, and Research in Paris, France. He is the Founding Chair of Xi’an Chapter of IEEE Systems, Man, and Cybernetics Society

Alessandro Giua (M’92–SM’08–F’17) received a laurea degree from the University of Cagliari, Italy in 1988, and the Master and Ph. D. degrees in computer and systems engineering from Rensselaer Polytechnic Institute Troy, NY, USA in 1990 and 1992. He is a Professor of Automatic Control at the Department of Electrical and Electronic Engineering (DIEE) of the University of Cagliari, Italy. He has also held faculty or visiting positions in several institutions worldwide, including Aix-Marseille University, France and Xidian University, Xi’an, China. His research interests include discrete event systems, hybrid systems, networked control systems, Petri nets and failure diagnosis. He serves the Institute of Electrical and Electronic Engineers (IEEE) as Vice President for Conference Activities of the Control Systems Society (CSS) and the International Federation of Automatic Control (IFAC) as a member of the Publications Committee. He is currently Editor in Chief of the IFAC journal Nonlinear Analysis: Hybrid Systems, a Senior Editor of the IEEE Transaction on Automatic Control, and a department editor of the journal Discrete Event Dynamic Systems. He is a Fellow of the IEEE and a Fellow of the IFAC for contributions to Discrete Event and Hybrid Systems. He is a recipient of the People’s Republic of China Friendship Award and of the Shaanxi government Sanqin Friendship Award
Corresponding author: Z. W. Li is with the School of Electro-Mechanical Engineering, Xidian University, Xi’an 710071, and also with Institute of Systems Engineering, Macau University of Science and Technology, Taipa 999078, Macau, China (e-mail: zhwli@xidian.edu.cn)
¹ 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.
² 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.
Received Date: 2020-02-28
Revised Date: 2020-05-05
Accepted Date: 2020-06-10

Available Online: 2020-07-02

Abstract

Abstract

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.
- Discrete event system,
- resource allocation,
- timed Petri net,
- weighted marked graph

FullText(HTML)

¹ 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.
² 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.

References(39)

References

[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
[2]	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
[3]	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.
[4]	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
[5]	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
[6]	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
[7]	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.
[8]	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.
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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.
[15]	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
[16]	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
[17]	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
[18]	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
[19]	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
[20]	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
[21]	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
[22]	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
[23]	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
[24]	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
[25]	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.
[26]	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.
[27]	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.
[28]	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
[29]	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
[30]	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
[31]	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
[32]	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.
[33]	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
[34]	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
[35]	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
[36]	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
[37]	Lindo Systems Inc., Lingo User’s Guide, 2011. [Online]. Available: http://www.lindo.com, Accessed on: Mar. 2017.
[38]	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.
[39]	Z. He, Z. Y. Ma, and W. Tang. “Performance safety enforcement in strongly connected timed event graphs,” Automatica, under review, 2020.

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(6) / Tables(1)

Get Citation

PDF

XML

Article Metrics

Article views (1035) PDF downloads(61)

Highlights

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

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

doi: 10.1109/JAS.2020.1003477

Abstract

References

Proportional views

Catalog

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

Article Metrics

Highlights

Export File

Citation

Format

Content