考虑合成机制的多星应急任务调度

doi:10.12305/j.issn.1001-506X.2022.04.25

Abstract

Abstract:

Based on the principle of priority scheduling of emergency tasks, it is an urgent problem in the field of multi-satellite emergency task scheduling to minimize the perturbation to the original scheduling sequence on the basis of ensuring the total revenue of observations. Firstly, the relationship between the completion time and the observation revenue of emergency tasks is considered, and a mathematical programming model with time-dependent revenue is established. Besides, a multi-satellite emergency task scheduling algorithm with the merging mechanism based on the genetic algorithm is proposed. In the devised algorithm, task merging operator, task insertion operator and task replacement operator are designed to insert emergency tasks; the fitness function is designed by combining the observation revenue, sequence perturbation and minimum observation time; crossover operator, mutation operator and global repair operator are proposed to iterate and optimize scheduling sequences. Finally, numerical experiments indicate that the designed algorithm can significantly improve the scheduling quality, which is suitable for the multi-satellite emergency task scheduling problem.

Key words: earth observation satellite, emergency task, genetic algorithm, merging mechanism

CLC Number:

Peng JIN, Xiaoxi TANG. Multi-satellite emergency task scheduling with merging mechanism[J]. Systems Engineering and Electronics, 2022, 44(4): 1270-1281.

Figures/Tables 19

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Table 1

Table 2

Fig.14

Table 3

Fig.15

Fig.16

References 34

1	LIU X L , LAPORTE G , CHEN Y W , et al. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time[J]. Computers and Operations Research, 2017, 86 (4): 41- 53.
2	XU R , CHEN H P , LIANG X L , et al. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization[J]. Expert Systems with Applications, 2016, 51, 195- 206. doi: 10.1016/j.eswa.2015.12.039
3	QI J T , GUO J J , WANG M M , et al. A cooperative autonomous scheduling approach for multiple earth observation satellites with intensive missions[J]. IEEE Access, 2021, 9, 61646- 61661. doi: 10.1109/ACCESS.2021.3075059
4	WANG S , LIN Z , CHENG J H , et al. Task scheduling and attitude planning for agile earth observation satellite with intensive tasks[J]. Aerospace Science and Technology, 2019, 90 (4): 23- 33.
5	BARKAOUI M , BERGER J . A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation[J]. Journal of the Operational Research Society, 2020, 71 (9): 1390- 1410. doi: 10.1080/01605682.2019.1609891
6	CHEN X Y , REINELT G , DAI G M , et al. Priority-based and conflict-avoidance heuristics for multi-satellite scheduling[J]. Applied Soft Computing, 2018, 69 (4): 177- 191.
7	邱涤珊, 王建江, 吴朝波, 等. 基于任务合成的对地观测卫星应急调度方法[J]. 系统工程与电子技术, 2013, 35 (7): 1430- 1437.
	QIU D S , WANG J J , WU C B , et al. Emergency scheduling me-thod of earth observation satellites based on task merging[J]. Systems Engineering and Electronics, 2013, 35 (7): 1430- 1437.
8	WANG J J , HU X J , HE C . Reactive scheduling of multiple EOSs under cloud uncertainties: model and algorithms[J]. Journal of Systems Engineering and Electronics, 2021, 32 (1): 163- 177. doi: 10.23919/JSEE.2021.000015
9	WANG J , DEMEULEMEESTER E , HU X , et al. Expectation and SAA models and algorithms for scheduling of multiple earth observation satellites under the impact of clouds[J]. IEEE Systems Journal, 2020, 14 (4): 5451- 5462. doi: 10.1109/JSYST.2019.2961236
10	WANG X W , SONG G P , LEUS R , et al. Robust Earth observation satellite scheduling with uncertainty of cloud coverage[J]. IEEE Trans.on Aerospace and Electronic Systems, 2020, 56 (3): 2450- 2461. doi: 10.1109/TAES.2019.2947978
11	CHEN X Y , GERHAR D R , DAI G M , et al. A mixed integer li-near programming model for multi-satellite scheduling[J]. European Journal of Operational Research, 2018, 275 (2): 694- 707.
12	E Z B , SHI R H , GAN L , et al. Multi-satellites imaging scheduling using individual reconfiguration based integer coding genetic algorithm[J]. Acta Astronautica, 2021, 178, 645- 657. doi: 10.1016/j.actaastro.2020.08.041
13	LI L X, MA W Z, LIU X L, et al. Research on TSGA algorithm satellite data transmission scheduling[C]//Proc. of the International Conference on Management Science & Engineering, 2014: 56-61.
14	WU G H , MA M H , ZHU J H , et al. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks[J]. Journal of Systems Engineering and Electronics, 2012, 23 (5): 723- 733. doi: 10.1109/JSEE.2012.00089
15	贺川, 朱晓敏, 邱涤珊. 面向应急成像观测任务的多星协同调度方法[J]. 系统工程与电子技术, 2012, 34 (4): 726- 731. doi: 10.3969/j.issn.1001-506X.2012.04.16
	HE C , ZHU X M , QIU D S . Cooperative scheduling method of multi-satellites for imaging reconnaissance in emergency condition[J]. Systems Engineering and Electronics, 2012, 34 (4): 726- 731. doi: 10.3969/j.issn.1001-506X.2012.04.16
16	WANG J M, LI J F, TAN Y J. Study on heuristic algorithm for dynamic scheduling problem of earth observing satellites[C]//Proc. of the 8th ACIS International Conference on the Software Engineering Artificial Intelligence Networking and Parallel Distributed Computing, 2007: 9-14.
17	郭超, 熊伟, 刘呈祥. 基于优先级与时间裕度的卫星应急观测任务规划[J]. 电讯技术, 2016, 56 (7): 744- 749. doi: 10.3969/j.issn.1001-893x.2016.07.005
	GUO C , XIONG W , LIU C X . Mission planning of satellite emergency observations based on priority and time margin degree[J]. Telecommunication Engineering, 2016, 56 (7): 744- 749. doi: 10.3969/j.issn.1001-893x.2016.07.005
18	NIU X N , TANG H , WU L X , et al. Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events[J]. Mathematical Problems in Engineering, 2015, 2015, 731734.
19	GUO C, XIONG W, LIU C X. Research on emergency mission planning of earth observation satellites[C]//Proc. of the IEEE 1st International Conference on Computer Communication and the Internet, 2016.
20	NIU X N , TANG H , WU L X . Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm[J]. International Journal of Disaster Risk Reduction, 2018, 28, 813- 825. doi: 10.1016/j.ijdrr.2018.02.013
21	WANG M C , DAI G M , VASILE M , et al. Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites[J]. Mathematical Problems in Engineering, 2014, 2014 (5): 234928.
22	SUN H Q , XIA W , HU X X , et al. Earth observation satellite scheduling for emergency tasks[J]. Journal of Systems Engineering and Electronics, 2019, 30 (5): 931- 945. doi: 10.21629/JSEE.2019.05.11
23	ZHAO Y B , DU B , LI S . Agile satellite mission planning via task clustering and double-layer tabu algorithm[J]. Computer Modeling in Engineering & Sciences, 2020, 122 (1): 235- 257.
24	白保存, 贺仁杰, 李菊芳, 等. 卫星单轨任务合成观测问题及其动态规划算法[J]. 系统工程与电子技术, 2009, 31 (7): 1738- 1742. doi: 10.3321/j.issn:1001-506X.2009.07.046
	BAI B C , HE R J , LI J F , et al. Satellite orbit task merging problem and its dynamic programming algorithm[J]. Systems Engineering and Electronics, 2009, 31 (7): 1738- 1742. doi: 10.3321/j.issn:1001-506X.2009.07.046
25	LONG X Y , WU S F , WU X F , et al. A GA-SA hybrid planning algorithm combined with improved clustering for LEO observation satellite missions[J]. Algorithms, 2019, 12 (11): a12110231.
26	LIU X L , BAI B C , CHEN Y W , et al. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics and Computation, 2014, 230, 687- 700. doi: 10.1016/j.amc.2013.12.109
27	WU G H , WANG H L , WITOLD P , et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Computers & Industrial Engineering, 2017, 113, 576- 588.
28	QIU D S , WU G H , LIU J , et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers and Operations Research, 2013, 40 (7): 1884- 1894. doi: 10.1016/j.cor.2013.02.009
29	LONG J, CHEN S L, LI C, et al. A task clustering method for multi agile satellite based on clique partition[C]//Proc. of the International Conference on Intelligent Computation Technology & Automation, 2018: 332-336.
30	LONG X Y, WU S F, CUI B J, et al. Analysis of satellite observation task clustering based on the improved clique partition algorithm[C]//Proc. of the IEEE Congress on Evolutionary Computation, 2019: 1314-1321.
31	白保存, 慈元卓, 陈英武. 基于动态任务合成的多星观测调度方法[J]. 系统仿真学报, 2009, 21 (9): 2646- 2649.
	BAI B C , CI Y Z , CHEN Y W . Dynamic task merging in multi-satellites observing scheduling[J]. Journal of System Simulation, 2009, 21 (9): 2646- 2649.
32	WANG J J , ZHU X M , QIU D S , et al. Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging[J]. IEEE Trans.on Parallel and Distributed Systems, 2014, 25 (9): 2275- 2285. doi: 10.1109/TPDS.2013.156
33	NIU X N , TANG H , WU L X , et al. Imaging-duration embedded dynamic scheduling of Earth observation satellites for emergent events[J]. Mathematical Problems in Engineering, 2015, 2015 (4): 731734.
34	WANG J J , ZHU X M , YANG L T , et al. Towards dynamic real-time scheduling for multiple earth observation satellites[J]. Journal of Computer and System Sciences, 2015, 81 (1): 110- 124. doi: 10.1016/j.jcss.2014.06.016

卫星编号	卫星名称	单轨最大存储限制	传感器旋转速率/(°/s)	单次最长开机时间/s	传感器稳定时间/s	传感器视场角/(°)
1	FENGYUN_1D_27431	200	5	50	3	12
2	FENGYUN_3A_32958	210	3	60	4	10
3	GAOFEN_1_39150	190	4	55	2	14

序号	常规任务规模	应急任务规模	GA-ETS			IDI			收益差值相对值/%
序号	常规任务规模	应急任务规模	收益	扰动	运行时间/s	收益	扰动	运行时间/s	收益差值相对值/%
1	100	20	54.53	28.4	7.000	48.44	28.4	0.457	12.57
2		40	78.68	30.0	13.390	69.00	29.1	0.454	14.03
3		60	92.49	30.8	25.530	80.92	28.9	0.464	14.30
4	200	20	68.53	47.5	16.460	62.07	45.1	3.153	10.41
5		40	94.38	47.1	22.000	85.52	46.7	3.473	10.36
6		60	107.22	49.0	34.880	97.72	46.1	3.584	9.72
7	400	20	89.00	77.2	57.170	81.24	72.1	19.559	9.55
8		40	112.65	76.1	65.500	104.72	70.6	20.246	7.57
9		60	125.49	75.3	82.190	117.00	71.9	17.747	7.26

序号	常规任务规模	应急任务规模	GA-TM-ETS					GA-ETS
序号	常规任务规模	应急任务规模	收益	扰动	常规任务完成数量	应急任务完成数量	运行时间/s	收益	扰动	常规任务完成数量	应急任务完成数量	运行时间/s
1	100	20	98.19	29.9	99	19	6.615	54.53	28.4	71	13	7.000
2		40	146.93	30.1	99	39	13.205	78.68	30.0	68	24	13.390
3		60	210.61	31.9	98	59	24.660	92.49	30.8	67	31	25.530
4	200	20	149.25	50.0	194	19	16.135	68.53	47.5	104	13	16.460
5		40	209.48	50.0	194	39	22.842	94.38	47.1	101	24	22.000
6		60	269.56	50.8	193	59	36.427	107.22	49.0	98	32	34.880
7	400	20	240.59	71.3	383	19	58.242	89.00	77.2	155	14	57.170
8		40	309.44	71.0	382	39	66.945	112.64	76.1	145	24	65.500
9		60	364.41	70.9	380	58	85.052	125.49	75.3	139	31	82.190

[1]	Lu ZHUANG, Zhong LU, Haijing SONG, Jia ZHOU. An optimization method for development assurance level assignment of airborne system [J]. Systems Engineering and Electronics, 2022, 44(8): 2688-2698.
[2]	Tiansu LUO, Lingfeng ZHAO, Yunwen FENG, Xiaofeng XUE, Cheng LU. Super large-scale satellite constellation multi-level backup strategy based on METRIC theory [J]. Systems Engineering and Electronics, 2022, 44(7): 2181-2190.
[3]	Bo LI, Jiahao ZHOU, Minmin LIU, Pinchao ZHU. Feature selection for welding defect assessment based on improved NSGA3 [J]. Systems Engineering and Electronics, 2022, 44(7): 2211-2218.
[4]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[5]	Shaolong YANG, Jin HUANG, Xianbo XIANG, Weichao LI. Optimization of USV area coverage path planning based on confidence ellipsoid [J]. Systems Engineering and Electronics, 2022, 44(7): 2263-2269.
[6]	Yunwen FENG, Junyu CHEN, Cheng LU. Research on civil aircraft spare parts multi-region support network model [J]. Systems Engineering and Electronics, 2022, 44(5): 1553-1561.
[7]	Jianwei SUN, Chao WANG, Qingzhan SHI, Wenbo REN, Zekun YAO, Naichang YUAN. Intelligent optimization of phase-modulation waveform based on genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(3): 722-729.
[8]	Naiyang XUE, Dan DING, Hongmin WANG, Buhua LIU. Multi-type TT&C resource scheduling method based on improved genetic algorithm [J]. Systems Engineering and Electronics, 2021, 43(9): 2535-2543.
[9]	Luda ZHAO, Bin WANG, Wei ZENG. Three-level programming model of electronic countermeasures force requirements in offensive combat [J]. Systems Engineering and Electronics, 2021, 43(6): 1564-1571.
[10]	Li WANG, Ziqi LIU. Fault diagnosis of analog circuit for WPA-IGA-BP neural network [J]. Systems Engineering and Electronics, 2021, 43(4): 1133-1143.
[11]	Chunyu HU, Weidong LIU, Tianxiang YU, Liyao ZHOU, Chen FENG. Analysis of multi wave task planning model based on UAV real-time data [J]. Systems Engineering and Electronics, 2021, 43(3): 747-754.
[12]	Zhenzhen YAN, Bo LI, Mao YANG, Zhongjiang YAN. Hybrid non-orthogonal multiple access method based on genetic algorithm [J]. Systems Engineering and Electronics, 2021, 43(3): 832-838.
[13]	Qingguo LIU, Xinxue LIU, Jian WU, Yaxiong LI, Hao CHEN. Optimization of fire distribution for multiple SGSW based on improved NSGA-Ⅲ [J]. Systems Engineering and Electronics, 2020, 42(9): 1995-2002.
[14]	Shengkui ZHANG, Zhicheng YAO, Min HE, Zhiliang FAN, Jian YANG. FH signal parameter blind estimation based on time-frequency variance clustering [J]. Systems Engineering and Electronics, 2020, 42(8): 1662-1667.
[15]	Yuan GUO, Zhiyong SUO, Tingting WANG, Zhiqiang LIAO. Parameter optimization design method of missile-borne SAR system [J]. Systems Engineering and Electronics, 2020, 42(7): 1478-1483.

Multi-satellite emergency task scheduling with merging mechanism

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 34

Related Articles 15

Recommended Articles

Metrics

Comments