A branch and price algorithm for the robust WSOS scheduling problem

doi:10.23919/JSEE.2021.000056

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()

¹ 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

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

Ruiyang LI, Ming HE, Hongyue HE, Zhixue WANG, Cheng YANG. A branch and price algorithm for the robust WSOS scheduling problem[J]. Journal of Systems Engineering and Electronics, 2021, 32(3): 658-667.

Figures/Tables 7

Fig 1

Fig 2

Fig 3

Table 1

Fig 4

Table 2

Table 3

References 35

1	EDWARD C, AMIT S Next-generation smart environments: from system of systems to data ecosystems. IEEE Intelligent Systems, 2018, 33 (3): 69- 76. doi: 10.1109/MIS.2018.033001418
2	ZHAO Q S, DING J Y, LI J C, et al Mission-oriented scheme generation method for weapon system of systems. IEEE Access, 2020, 8, 70981- 70996. doi: 10.1109/ACCESS.2020.2987062
3	WANG H, LAPPAS N H, GOUNARIS C E Multi-mode resource constrained project scheduling with alternative prerequisites: new models and computational studies. Industrial & Engineering Chemistry Research, 2019, 58 (39): 18253- 18266.
4	CHEN P H, WENG H J A two-phase GA model for resource-constrained project scheduling. Automation in Construction, 2009, 18 (4): 485- 498. doi: 10.1016/j.autcon.2008.11.003
5	NAJID N M, ARROUB M An efficient algorithm for the multi-mode resource constrained project scheduling problem with resource flexibility. International Journal of Mathematics in Operational Research, 2010, 2 (6): 748- 761. doi: 10.1504/IJMOR.2010.035497
6	WANG L, FANG C An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem. Computers & Operations Research, 2012, 39 (2): 449- 460.
7	AYODELE M, MCCALL J, REGNIER C O. RK-EDA: a novel random key based estimation of distribution algorithm. Proc. of the International Conference on Parallel Problem Solving from Nature, 2016: 849−858.
8	ADAMU P I, AGARANA M C, OKAGBUE H. Learning heuristic for solving multi-mode resource-constrained project scheduling problems. Proc. of the International Multiconference of Engineers and Computer Scientists, 2018: 14−16.
9	AFSHAR M R, SHAHHOSSEINI V, SEBT M H A genetic algorithm with a new local search method for solving the multimode resource-constrained project scheduling problem. International Journal of Construction Management, 2019, 19 (3): 1- 9.
10	ROSON J H, KULEJEWSKI J E A hybrid approach for solving multi-mode resource-constrained project scheduling problem in construction. Open Engineering, 2019, 9 (1): 7- 13. doi: 10.1515/eng-2019-0006
11	RATAJCZAK R E Experimental evaluation of agent-based approaches to solving multi-mode resource-constrained project scheduling problem. Cybernetics and Systems, 2018, 49 (2): 1- 21.
12	ZSOLT T K, SZALKAI I Multimode resource-constrained project scheduling in flexible projects. Journal of Global Optimization, 2020, 76 (1): 211- 241. doi: 10.1007/s10898-019-00832-8
13	VAHDANI H, SHAMS A Multi-mode capital-constrained project payment scheduling model considering bonus-penalty structure. International Journal of Management Science & Engineering Management, 2020, 15 (1): 17- 25.
14	SPRECHER A, DREXL A Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. European Journal of Operational Research, 1998, 107 (2): 431- 450. doi: 10.1016/S0377-2217(97)00348-2
15	KYRIAKIDIS T S, KOPANOS G M, GEORGIADIS M C MILP formulations for single- and multi-mode resource-constrained project scheduling problems. Computers & Chemical Engineering, 2012, 36 (1): 369- 385.
16	JOSE C, MARIO V Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. European Journal of Operational Research, 2011, 213 (1): 73- 82. doi: 10.1016/j.ejor.2011.03.019
17	SCHNELL A, HARTL R F On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations. OR Spectrum, 2016, 38 (2): 283- 303. doi: 10.1007/s00291-015-0419-6
18	BOFILL M, COLL J, SUY J, et al Solving the multi-mode resource-constrained project scheduling problem with SMT. Proc.of the IEEE International Conference on Tools with Artificial Intelligence, 2017, 239- 246.
19	ALTINTAS C, AZIZOGLU M A branch and bound algorithm for a multi-mode project scheduling problem with a single non-renewable resource. International Journal of Information Technology, 2020, 11 (2): 55- 70.
20	LI R Y, WANG Z X, YU M G, et al Multi-objective portfolio optimization of system of systems based on robust capabilities. Systems Engineering and Electronics, 2019, 41 (5): 103- 111.
21	LEUS R, HERROELEN W The complexity of machine scheduling for stability with a single disrupted job. Operations Research Letters, 2005, 33 (2): 151- 156. doi: 10.1016/j.orl.2004.04.008
22	KAVEH A, KHANZADI M, ALIPOUR M Fuzzy resource constraint project scheduling problem using CBO and CSS algorithms. International Journal of Civil Engineering, 2016, 14 (5): 325- 337. doi: 10.1007/s40999-016-0031-4
23	BIRJANDI A, MOUSAVI S M Fuzzy resource-constrained project scheduling with multiple routes: a heuristic solution. Automation in Construction, 2019, 100 (4): 84- 102.
24	ANGELA C, YUN C L, JOSE D P An entropy-based upper bound methodology for robust predictive multi-mode RCPSP schedules. Entropy, 2014, 16 (9): 5032- 5067. doi: 10.3390/e16095032
25	SHAN W X, PENG Z X, LIU J M, et al An exact algorithm for inland container transportation network design. Transportation Research Part B: Methodological, 2020, 135, 41- 82. doi: 10.1016/j.trb.2020.02.011
26	DRAUDVILIENE L, MESKUOTIENE A, RAISUTIS R, et al The capability assessment of the spectrum decomposition technique for measurements of the group velocity of lamb waves. Journal of Nondestructive Evaluation, 2018, 37 (2): 29- 42. doi: 10.1007/s10921-018-0484-2
27	LIAO W Z, FU Y X. Min-max regret criterion-based robust model for the permutation flow-shop scheduling problem. Engineering Optimization, 2020, 52(4): 687−700.
28	LI R Y, HE M, HE H Y, et al Heuristic column generation for designing an express circular packaging distribution network. Operational Research, 2020, 1, 1- 24. doi: 10.1007/s12351-020-00570-w
29	NANNICINI G, SARTOR G, TRAVERSI E, et al An exact algorithm for robust influence maximization. Mathematical Programming, 2020, 183 (1): 419- 453.
30	REIHANEH M, GHONIEM A A branch-cut-and-price algorithm for the generalized vehicle routing problem. Journal of the Operational Research Society, 2018, 69 (2): 307- 318. doi: 10.1057/s41274-017-0231-6
31	MUNARI P, MORENO A, JONATHAN D, et al The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transportation Science, 2019, 53 (4): 1043- 1066. doi: 10.1287/trsc.2018.0886
32	WEI Q, WU Y Dynamic programming algorithms for two- machine hybrid flow-shop scheduling with a given job sequence and deadline. IEEE Access, 2020, 8, 89964- 89975. doi: 10.1109/ACCESS.2020.2993857
33	WANG Q, LIU C C, ZHENG L A column-generation-based algorithm for a resource-constrained project scheduling problem with a fractional shared resource. Engineering Optimization, 2020, 52(5), 798- 816. doi: 10.1080/0305215X.2019.1610946
34	MYSZKOWSKI P B, MAREK E S, OLECH U P, et al Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem. Soft Computing, 2015, 19 (12): 3599- 3619. doi: 10.1007/s00500-014-1455-x
35	EYNDE R, VANHOUCKE M Resource-constrained multi-project scheduling: benchmark datasets and decoupled scheduling. Journal of Scheduling, 2020, 23, 301- 325. doi: 10.1007/s10951-020-00651-w

Activity (requirement)	Participation System (capability)	Duration/h
1(2)	Sys3(1), Sys4(1)	0?4
2(3)	Sys6(2), Sys7(2)	0?2
3(4)	Sys1(2), Sys2(2)	8?11
4(2)	Sys5(2)	2?3
5(4)	Sys2(2), Sys6(2)	4?6
6(2)	Sys3(1), Sys7(2)	3?6
7(3)	Sys5(2), Sys8(1)	6?8
8(3)	Sys4(1), Sys6(2)	6?10
9(3)	Sys9(3)	11?13
10(3)	Sys5(2), Sys8(1)	10?14

Instance	CPLEX			Branch-and-price						GAP/%
Instance	ACT	OPT	Node	col. in MP	ACT in MP	ACT	LB	OPT	Node	GAP/%
100-10-48-15	1751	792	9701	961	145	1134	792	792	14	0.00
100-20-46-15	1954	600	14984	1443	180	1395	600	600	38	0.00
100-5-20-9-D3	1648	1200	12505	727	135	749	1200	1200	25	0.00
200-10-50-9	2561	1560	19400	1626	202	1683	1560	1560	112	0.00
200-10-85-15	2948	1464	22441	3548	242	1 990	1464	1464	154	0.00
200-20-97-9	3474	888	27832	5137	212	2451	888	888	189	0.00
200-40-133-15	3600	720	31576	7126	295	2846	648	648	265	?10.00
200-40-45-9	3600	696	37072	9552	362	3399	624	624	378	?10.34
200-40-90-9	3600	696	39098	11660	450	3600	576	600	466	?13.79
200-40-91-15	3600	672	41687	14235	481	3600	552	576	555	?14.29

[1]	Naikang YU, Bin QIAN, Rong HU, Yuwang CHEN, Ling WANG. Solving open vehicle problem with time window by hybrid column generation algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 997-1009.
[2]	Fan YUE, Shiji SONG, Peng JIA, Guangping WU, Han ZHAO. Robust single machine scheduling problem with uncertain job due dates for industrial mass production [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 350-358.
[3]	Jianfei Ding, Guangya Si, Guoqiang Yang, Yang Liu, and Xiao Liu. Visualization analysis of the capability of weapon system of systems for multi-dimensional indicators [J]. Systems Engineering and Electronics, 2017, 28(2): 292-300.
[4]	Ke Wang, and Fajie Wei. Robust data envelopment analysis based MCDM with the consideration of uncertain data [J]. Journal of Systems Engineering and Electronics, 2010, 21(6): 981-989.

A branch and price algorithm for the robust WSOS scheduling problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 7

References 35

Related Articles 4

Recommended Articles

Metrics

Comments

Group	Instance	Activity	System	Relation	Capability
G1	100-10-48-15	100	10	48	15
	100-20-46-15	100	20	46	15
	100-5-20-9-D3	100	5	20	9
G2	200-10-50-9	200	10	50	9
	200-10-85-15	200	10	85	15
	200-20-97-9	200	20	97	9
	200-40-133-15	200	40	133	15
	200-40-45-9	200	40	45	9
	200-40-90-9	200	40	90	9
	200-40-91-15	200	40	91	15