Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (3): 658-667.doi: 10.23919/JSEE.2021.000056

• SYSTEMS ENGINEERING • Previous Articles     Next Articles

A branch and price algorithm for the robust WSOS scheduling problem

Ruiyang LI(), Ming HE*(), Hongyue HE(), Zhixue WANG(), Cheng YANG()   

  1. 1 Institute of Command and Control Engineering, Army Engineering University of PLA, Nanjing 210007, China
  • Received:2020-03-17 Online:2021-06-18 Published:2021-07-26
  • Contact: Ming HE E-mail:15601591998@163.com;heming@126.com;hehy2008@sina.com;wzxcx@163.com;978008436@qq.com
  • About author:|LI Ruiyang was born in 1992. He is a Ph.D. student in Institute of Command and Control Engineering, Army Engineering University of PLA. After graduating from college in 2014, He was admitted to the PLA University of Science and Technology, his profession was system analysis and integration. In the master’s period, his major research interests were operational optimization, operational effectiveness assessment and artificial intelligence algorithm. Then he continued to pursue a doctorate in software engineering. His major research interests are requirement engineering and model and method of system of systems planning and management. E-mail: 15601591998@163.com||HE Ming was born in 1978. He is a professor in Institute of Command and Control Engineering, Army Engineering University of PLA. He received his B.Sc., M.Sc. and Ph.D. degrees from PLA Science and Technology University in 2000, 2003 and 2007, respectively. His main research interests focus on emergency command, big data analytics, multi-agent control and situation awareness. E-mail: heming@126.com||HE Hongyue was born in 1985. He received his M.S. degree in 2007 and Ph.D. degree in 2014 from PLA University of Science and Technology. Now, he is a lecturer of Army Engineering University of PLA. His research interests are system of systems engineering, focusing on specification. E-mail: hehy2008@sina.com||WANG Zhixue was born in 1961. He is a professor in Institute of Command and Control Engineering, Army Engineering University of PLA. He received his M.S. degree from National University of Defense and Technology, and was a visiting researcher in Faculty of Information Technology, University of Brighton, England. His research interests are software engineering, requirements engineering, theory and technology of command automation, currently focusing on domain specific modeling and formal verification. E-mail: wzxcx@163.com||YANG Cheng was born in 1990. He is a master student in Institute of Command and Control Engineering, Army Engineering University of PLA. His major is computer technology. His main research interests are machine learning and the internet of things. E-mail: 978008436@qq.com
  • Supported by:
    This work was supported by the National Key R&D Program of China (2018YFC0806900), the China Postdoctoral Science Foundation Funded Project (2018M633757), the Primary Research & Development Plan of Jiangsu Province (BE2017616; BE20187540; BE2019762; BE2020729), and the Jiangsu Province Postdoctoral Science Foundation Funded Project (2019K185)

Abstract:

To analyze and optimize the weapon system of systems (WSOS) scheduling process, a new method based on robust capabilities for WSOS scheduling optimization is proposed. First, we present an activity network to represent the military mission. The member systems need to be reasonably assigned to perform different activities in the mission. Then we express the problem as a set partitioning formulation with novel columns (activity flows). A heuristic branch-and-price algorithm is designed based on the model of the WSOS scheduling problem (WSOSSP). The algorithm uses the shortest resource-constrained path planning to generate robust activity flows that meet the capability requirements. Finally, we discuss this method in several test cases. The results show that the solution can reduce the makespan of the mission remarkably.

Key words: weapon system of systems (WSOS), robust optimization, scheduling decision, branch-and-price, column generation