A dual population multi-operator genetic algorithm for flight deck operations scheduling problem

doi:10.23919/JSEE.2021.000028

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 331-346.doi: 10.23919/JSEE.2021.000028

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Previous Articles Next Articles

A dual population multi-operator genetic algorithm for flight deck operations scheduling problem

Rongwei CUI¹(), Wei HAN¹(), Xichao SU^2,*(), Hongyu LIANG³(), Zhengyang LI³()

¹ Aeronautical Foundation College, Naval Aviation University, Yantai 264001, China
² Aeronautical Operations College, Naval Aviation University, Yantai 264001, China
³ Unit 91404 of the PLA, Qinhuangdao 066000, China

Received:2020-11-20 Online:2021-04-29 Published:2021-04-29
Contact: Xichao SU E-mail:cuirongwei126@163.com;Hanwei70cn@163.com;suxich@126.com;yu675878@163.com;lizhengyang1021@163.com
About author:|CUI Rongwei was born in 1996. He received his B.S. degree in mechanical engineering from Naval Aviation University, Yantai, China, in 2019. He is currently working toward his master’s degree in Naval Aviation University. His research interests include flight deck operations scheduling and intelligent computation. E-mail: cuirongwei126@163.com||HAN Wei was born in 1970. He received his B.S. degree in aircraft and engine engineering and M.S. degree in aeronautical and astronautical science and technology from Naval Aviation University, Yantai, China, in 1992 and 1996, respectively, and Ph.D. degree in solid mechanics from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 2003. He is a professor in Naval Aviation University. His research interests include operations scheduling and aircraft dynamics. E-mail: Hanwei70cn@163.com||SU Xichao was born in 1989. He received his B.S. degree in aircraft system and engineering and Ph.D. degree in aeronautical and astronautical science and technology from Naval Aviation University, Yantai, China, in 2012 and 2018, respectively. He is a lecturer in Naval Aviation University. His research interests are flight deck operations scheduling and intelligent computation. E-mail: suxich@126.com||LIANG Hongyu was born in 1995. He received his B.S. degree in mechanical engineering and M.S. degree in aeronautical and astronautical science and technology from Naval Aviation University, Yantai, China, in 2017 and 2019, respectively. He is an assistant engineer in Unit 91404 of the PLA. His research interests are flight deck operations scheduling and intelligent computation. E-mail: yu675878@163.com||LI Zhengyang was born in 1994. He received his B.S. degree in water resources and hydropower engineering from Wuhan University, Wuhan, China, in 2017, and M.S. degree in aviation engineering from Naval Aviation University, Yantai, China, in 2019. He is an assistant engineer in Unit 91404 of the PLA. His research interests are flight deck operations scheduling and intelligent computation. E-mail: lizhengyang1021@163.com
Supported by:
This work was supported by the National Natural Science Foundation of China (61671462);This work was supported by the National Natural Science Foundation of China (61671462)

Abstract

Abstract:

It is of great significance to carry out effective scheduling for the carrier-based aircraft flight deck operations. In this paper, the precedence constraints and resource constraints in flight deck operations are analyzed, then the model of the multi-aircraft integrated scheduling problem with transfer times (MAISPTT) is established. A dual population multi-operator genetic algorithm (DPMOGA) is proposed for solving the problem. In the algorithm, the dual population structure and random-key encoding modified by starting/ending time of operations are adopted, and multiple genetic operators are self-adaptively used to obtain better encodings. In order to conduct the mapping from encodings to feasible schedules, serial and parallel scheduling generation scheme-based decoding operators, each of which adopts different justified mechanisms in two separated populations, are introduced. The superiority of the DPMOGA is verified by simulation experiments.

Key words: genetic algorithm, project scheduling, flight deck operation, transfer times of resources

Rongwei CUI, Wei HAN, Xichao SU, Hongyu LIANG, Zhengyang LI. A dual population multi-operator genetic algorithm for flight deck operations scheduling problem[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 331-346.

Figures/Tables 14

Fig.1

Fig.2

Fig.3

Table 1

Related notations in decoding operators"

Notation	Definition
C_g	The set of scheduled operations at stage g
${D_g}$	The set of eligible operations at stage g
${t_g}$	The earliest feasible scheduling time of stage g
${A_g}$	The set of operations active in period t_g of stage g
${t'_g}$	The earliest precedence-resource-feasible scheduling time of stage g
${\text{π}} Lp_{kl}^t$	0, if personnel l with trade $k\left( {k \in Kp} \right)$ is not performing or transferring in period t; 1, otherwise
${\text{π}} Le_{kl}^t$	i, if support equipment l of the type $k\left( {k \in Ke} \right)$ is supporting aircraft i $\left( {i = 1,2, \cdots ,n} \right)$ in period t; $ - 1$ if this support equipment is transferring; 0, otherwise
${\text{π}} Ls_{ik}^t$	1, if work station space of the type $k\left( {k \in Ks} \right)$ in aircraft i in period t is occupied; 0, otherwise
${\text{π}} Lw_k^t$	The remaining number of aircraft that supply resource of the type $k\left( {k \in Kw} \right)$ can support in period t
$E{S_{ij}}$	The earliest precedence-feasible starting time of operation O_ij
SP_ij	The earliest personnel-feasible starting time of operation O_ij
$S\!\!{P_{ijk}}$	The earliest personnel-feasible starting time of operation O_ij for personnel with trade k $\left( {k \in Kp} \right)$
$S\!\!{P_{ijkl}}$	The earliest personnel-feasible starting time of operation O_ij for personnel l with trade $k\left( {k \in Kp} \right)$
SE_ij	The earliest equipment-feasible starting time of operation O_ij
$S\!\!{E_{ijk}}$	The earliest equipment-feasible starting time of operation O_ij for support equipment of the type $k\left( {k \in Ke} \right)$
$S\!\!{E_{ijkl}}$	The earliest equipment-feasible starting time of operation O_ij for support equipment l of the type $k\left( {k \in Ke} \right)$
SS_ij	The earliest space-feasible starting time of operation O_ij
SW_ij	The earliest supply resource-feasible starting time of operation O_ij
ERS_ij	The earliest precedence-resource-feasible starting time of operation O_ij
$lp_k^t$	The set of personnel with trade $k\left( {k \in Kp} \right)$ that can perform operation to be scheduled at period t
$le_k^t$	The set of support equipment of the type $k\left( {k \in Ke} \right)$ that can perform operation to be scheduled at period t
$Le_k^{{p_i}}$	The set of support equipment of the type $k\left( {k \in Ke} \right)$ that can reach the service parking spot ${p_i}$ , $Le_k^{{p_i}} = \left\{ {l\|\lambda _{kl}^{{p_i}} = 1,l \in L{e_k}} \right\}$
$RP_k^t$	The set of personnel with trade $k\left( {k \in Kp} \right)$ that are not performing or transferring at period t
$RE_k^t$	The set of support equipment of the type $k\left( {k \in Ke} \right)$ that are not performing or transferring at period t
$A{P_{kl}}$	The set of scheduled operations of the personnel l with trade $k\left( {k \in Kp} \right)$
$A{E_{kl}}$	The set of scheduled operations of the support equipment l of the type $k\left( {k \in Ke} \right)$
$T{T_{kl}}$	The accumulated transfer distance of the personnel l with trade $k\left( {k \in Kp} \right)$
$T{R_{kl}}$	The total performing time remaining in the cover area of the support equipment l of the type $k\left( {k \in Ke} \right)$

Table 1

Fig.4

Table 2

Fig.5

Table 3

Table 4

Table 5

Table 6

Fig.6

Table 7

References 32

1	LIU J, HAN W, LI J, et al Integration design of sortie scheduling for carrier aircraft based on hybrid flexible flowshop. IEEE Systems Journal, 2020, 14 (1): 1503- 1511. doi: 10.1109/JSYST.2019.2922261
2	LIU J, HAN W, WANG X W, et al Research on cooperative trajectory planning and tracking problem for multiple carrier aircraft on the deck. IEEE Systems Journal, 2020, 14 (2): 3027- 3038. doi: 10.1109/JSYST.2019.2932783
3	WANG X W, LIU J, SU X C, et al A review on carrier aircraft dispatch path planning and control on deck. Chinese Journal of Aeronautics, 2020, 33 (12): 3039- 3057. doi: 10.1016/j.cja.2020.06.020
4	SHI W W, HAN W, SI W C Optimization of direct flight line maintenance process for multi-carrier planes. Computer Engineering and Design, 2013, 34 (12): 4214- 4219.
5	YU L F, ZHU C, SHI J M, et al An extended flexible job shop scheduling model for flight deck scheduling with priority, parallel operations, and sequence flexibility. Scientific Programming, 2017, 2017, 2463252.
6	CUI R W, HAN W, SU X C, et al A multi-objective hyper heuristic framework for integrated optimization of carrier-based aircraft flight deck operations scheduling and resource configuration. Aerospace Science and Technology, 2020, 107, 106346. doi: 10.1016/j.ast.2020.106346
7	JIANG T T, SU X C, HAN W. Optimization of support scheduling on deck of carrier aircraft based on improved differential evolution algorithm. Proc. of the 3rd International Conference on Control Science and Systems Engineering, 2017. DOI: 10.1109/CCSSE.2017.8087910.
8	SU X C, HAN W, XIAO W, et al Pit-stop support scheduling on deck of carrier plane based on memetic algorithm. Systems Engineering and Electronics, 2016, 38 (10): 2303- 2309.
9	YUAN P L, HAN W, SU X C, et al. A dynamic scheduling method for carrier aircraft support operation under uncertain conditions based on rolling horizon strategy. Applied Sciences, 2018. DOI: 10.3390/app8091546.
10	SU X C, HAN W, WU Y, et al. A proactive robust scheduling method for aircraft carrier flight deck operations with stochastic durations. Complexity, 2018. DOI: 10.1155/2018/6932985.
11	SU X C, HAN W, WU Y, et al A robust scheduling optimization method for flight deck operations of aircraft carrier with ternary interval durations. IEEE Access, 2018, 6, 69918- 69936. doi: 10.1109/ACCESS.2018.2879503
12	ELSAYED S, SARKER R, RAY T, et al Consolidated optimization algorithm for resource-constrained project scheduling problems. Information Sciences, 2017, 418, 346- 362.
13	JIA Q, SEO Y An improved particle swarm optimization for the resource-constrained project scheduling problem. International Journal of Advanced Manufacturing Technology, 2013, 67 (9−12): 2627- 2638. doi: 10.1007/s00170-012-4679-x
14	WANG L, FANG C A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem. Expert Systems with Applications, 2012, 39 (3): 2451- 2460. doi: 10.1016/j.eswa.2011.08.095
15	CHALESHTARTI A S, SHADROKH S, KHAKIFIROOZ M, et al A hybrid genetic and Lagrangian relaxation algorithm for resource-constrained project scheduling under nonrenewable resources. Applied Soft Computing, 2020, 94, 106482. doi: 10.1016/j.asoc.2020.106482
16	PEREZ E, POSADA M, LORENZANA A Taking advantage of solving the resource constrained multi-project scheduling problems using multi-modal genetic algorithms. Soft Computing, 2015, 20 (5): 1- 18. doi: 10.1007/s00500-015-1610-z
17	KADRI R L, BOCTOR F F An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: the single mode case. European Journal of Operational Research, 2017, 265 (2): 454- 462.
18	DEBELS D, VANHOUCKE M A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Research, 2007, 55 (3): 457- 469. doi: 10.1287/opre.1060.0358
19	ZHANG X J, MA S, CHEN S L Healthcare service configuration based on project scheduling. Advanced Engineering Informatics, 2020, 43, 101039. doi: 10.1016/j.aei.2020.101039
20	HAN W, SU X C, CHEN J F Integrated maintenance support scheduling method of multi-carrier aircraft. Systems Engineering and Electronics, 2015, 37 (4): 809- 816.
21	HARTMANN S, KOLISCH R Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 2000, 127 (2): 394- 407. doi: 10.1016/S0377-2217(99)00485-3
22	KOLISCH R, HARTMANN S. Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. http:// hdl.handle.net/10419/147576.
23	DEBELS D, REYCK B D, LEUS R, et al A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research, 2006, 169 (2): 638- 653. doi: 10.1016/j.ejor.2004.08.020
24	WANG J Q, CHENG Z W, ZHANG P L, et al Research on improvement of real-coded genetic algorithm for solving constrained optimization problems. Control and Decision, 2019, 34 (5): 44- 53.
25	COELHO J, VANHOUCKE M Going to the core of hard resource-constrained project scheduling instances. Computers & Operations Research, 2020, 121, 104976.
26	KOLISCH R Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. European Journal of Operational Research, 1996, 90 (2): 320- 333. doi: 10.1016/0377-2217(95)00357-6
27	RADY RAZ N, AKBARZADEH-T M R, AKBARZADEH A Experiment-based affect heuristic using fuzzy rules and Taguchi statistical method for tuning complex systems. Expert Systems with Applications, 2021, 172, 114638. doi: 10.1016/j.eswa.2021.114638
28	HOSEINPOUR-LONBAR M, ALAVI M Z, PALASSI M Selection of asphalt mix with optimal fracture properties at intermediate temperature using Taguchi method for design of experiment. Construction and Building Materials, 2020, 262, 120601. doi: 10.1016/j.conbuildmat.2020.120601
29	KRUGER D, SCHOLL A A heuristic solution framework for the resource constrained (multi-) project scheduling problem with sequence-dependent transfer times. European Journal of Operational Research, 2009, 197 (2): 492- 508. doi: 10.1016/j.ejor.2008.07.036
30	GUO W, VANHOUCKE M, COELHO J, et al Automatic detection of the best performing priority rule for the resource-constrained project scheduling problem. Expert Systems with Applications, 2020, 167, 114116.
31	CHAKRABORTTY R K, RAHMAN H F, RYAN M J Efficient priority rules for project scheduling under dynamic environments: a heuristic approach. Computers & Industrial Engineering, 2020, 140, 106287.
32	CHEN H, DING G, ZHANG J, et al Research on priority rules for the stochastic resource constrained multi-project scheduling problem with new project arrival. Computers & Industrial Engineering, 2019, 137, 106060.

Crossover operator		Mutation operator
Crossover 1	O(NP)	Mutation 1	O(NP)
Crossover 2	O((\|J\|?2)×NP)	Mutation 2	O(NP)
Crossover 3	O(\|J\|×NP)	Mutation 3	O(Na×NP)
Crossover 4	O(\|J\|×NP)	Mutation 4	O(\|J_i\|×NP)

Mission case	Service parking spot number
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	Aircraft type; released time/min
Mission 1	A;0	B;0	C;0	C;0	D;0	D;0	D;0	D;0	—	—	—	—	—	—	—	—
Mission 2	A;0	B;0	A;0	C;0	C;0	C;0	C;0	D;0	D;8	D;7	D;12	E;11	—	—	—	—
Mission 3	A;0	B;0	A;0	C;0	C;0	C;0	C;0	C;0	C;8	D;7	D;12	D;11	D;16	D;15	D;20	E;19

Parameter	Level
Parameter	1	2	3	4	5
NP	30	60	90	120	150
$ {\sigma }_{d}^{2} $	0.01	0.05	0.09	0.13	0.17
${P_{m0}}$	0.005	0.05	0.1	0.2	0.3

Level	NP	$\sigma _d^2$	${P_{m0}}$
1	0.0128	0.01158	0.01247
2	0.0092	0.01061	0.01205
3	0.01427	0.01384	0.01176
4	0.0119	0.01016	0.00972
5	0.01129	0.01328	0.01347
Delta	0.00507	0.00368	0.00374
Rank	1	3	2

Mission case	PS	Performance measurement	Algorithm					Priority rule
Mission case	PS	Performance measurement	DPMOGA	EGA	IPSO	HEDA	MMGA	minLFT	minSLK
Mission 1	1.8	Avg.	75.7	76.215	76.615	76.345	79.115	93.8	87.3
		Best.	75.2	75.7	75.3	75.9	77.4
		Var.	0.0758	0.0824	2.2529	0.25	0.5761
	3.2	Avg.	57.565	58.565	58.79	58.805	59.195	65	63.5
		Best.	56.8	58	58	58.5	58.6
		Var.	0.055	0.0971	0.3052	0.0373	0.0637
Mission 2	1.8	Avg.	74.695	75.825	76.6	78.53	79.445	95.6	87.7
		Best.	74.0	75.2	74.6	77.3	77.8
		Var.	0.1689	0.1472	2.5274	0.398	0.4847
	3.2	Avg.	57.41	58.3867	59.335	59.085	59.2	63.1	68.8
		Best.	57.1	57.4	58.2	58.6	58.7
		Var.	0.0378	0.1998	0.434	0.054	0.0674
Mission 3	1.8	Avg.	74.35	77.72	78.155	80.36	80.83	87.6	83.4
		Best.	74	76.1	75.5	79	79.3
		Var.	0.0553	0.5164	2.5626	0.3099	0.8843
	3.2	Avg.	61.805	62.435	63.58	62.815	62.45	66.1	67.4
		Best.	61.6	62	62	61.9	61.7
		Var.	0.0268	0.1645	2.0312	0.1413	0.0521

A dual population multi-operator genetic algorithm for flight deck operations scheduling problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 14

References 32

Related Articles 15

Recommended Articles

Metrics

Comments

p-value	Mission 1		Mission 2		Mission 3
p-value	PS=1.8	PS=3.2	PS=1.8	PS=3.2	PS=1.8	PS=3.2
p	$3.23 \times {10^{ - 5}}$	$5.59 \times {10^{ - 8}}$	$1.12 \times {10^{ - 7}}$	$3.45 \times {10^{ - 7}}$	$6.17 \times {10^{ - 8}}$	$7.62 \times {10^{ - 7}}$

[1]	Jianwei SUN, Chao WANG, Qingzhan SHI, Wenbo REN, Zekun YAO, Naichang YUAN. Intelligent optimization methods of phase-modulation waveform [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 916-923.
[2]	Yu LI, Honglan WU, Youchao SUN. Improved adaptive genetic algorithm based RFID positioning [J]. Journal of Systems Engineering and Electronics, 2022, 33(2): 305-311.
[3]	Yongbin YU, Chenyu YANG, Quanxin DENG, Tashi NYIMA, Shouyi LIANG, Chen ZHOU. Memristive network-based genetic algorithm and its application to image edge detection [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1062-1070.
[4]	Peng YANG, Haoyu XIE, Jing QIU. System level test selection based on combinatorial dependency matrix [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 984-994.
[5]	Cuiyu WANG, Yang LI, Xinyu LI. Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 261-271.
[6]	Yongjin LIU, Xihong CHEN, Yu ZHAO. Joint synchronization estimation based on genetic algorithm for OFDM/OQAM systems [J]. Journal of Systems Engineering and Electronics, 2020, 31(4): 657-665.
[7]	Xiaoyun LEI, Zhian ZHANG, Zhonghua DU. Analysis of an improved trajectory correction scheme based on mass blocks [J]. Journal of Systems Engineering and Electronics, 2019, 30(1): 180-190.
[8]	Ruoyu ZHANG, Honglin ZHAO, Jiayan ZHANG, Shaobo JIA. Hybrid orthogonal and non-orthogonal pilot distribution based channel estimation in massive MIMO system [J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 881-898.
[9]	Amir ZAHEDI, Bijan ABBASI ARAND. GA-based approach to phase compensation of large phased array antennas [J]. Journal of Systems Engineering and Electronics, 2018, 29(4): 723-730.
[10]	Hongqiang LIU, Lei YU, Haiyan YANG, Zhongliang ZHOU. Self-adapting radiation control method for RFS in tracking [J]. Journal of Systems Engineering and Electronics, 2018, 29(2): 244-255.
[11]	Hao Chen, Jiangjiang Wu, Wenyuan Shi, Jun Li, and Zhinong Zhong. Coordinate scheduling approach for EDS observation tasks and data transmission jobs [J]. Systems Engineering and Electronics, 2016, 27(4): 822-.
[12]	Jianzhong Zhao, Jianqiu Deng, Wen Ye, and Xiaofeng Lü. Combined forecast method of HMM and LS-SVM about electronic equipment state based on MAGA [J]. Systems Engineering and Electronics, 2016, 27(3): 730-738.
[13]	Xueying Wang, Jun Li, Tiebing Wang, Wei An, and Weidong Sheng. Satellite constellation design with genetic algorithms based on system performance [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 379-385.
[14]	Huaiyuan Li, Hongfu Zuo, Kun Liang, Juan Xu, Jing Cai, and Junqiang Liu. Optimizing combination of aircraft maintenance tasks by adaptive genetic algorithm based on cluster search [J]. Systems Engineering and Electronics, 2016, 27(1): 140-.
[15]	Yan Zhang, Shafei Wang, and Jicheng Li. Improved particle filtering techniques based on generalized interactive genetic algorithm [J]. Systems Engineering and Electronics, 2016, 27(1): 242-.