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

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

中图分类号:

靳鹏, 唐晓茜. 考虑合成机制的多星应急任务调度[J]. 系统工程与电子技术, 2022, 44(4): 1270-1281.

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

图/表 19

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

表1

表2

图14

表3

图15

图16

参考文献 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]	骆天溯, 赵灵峰, 冯蕴雯, 薛小锋, 路成. 基于METRIC理论的超大规模卫星星座多级备份策略[J]. 系统工程与电子技术, 2022, 44(7): 2181-2190.
[2]	李波, 周家豪, 刘民岷, 朱品朝. 基于改进NSGA3的焊接缺陷评估特征选择[J]. 系统工程与电子技术, 2022, 44(7): 2211-2218.
[3]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[4]	杨少龙, 黄金, 向先波, 李伟超. 基于置信椭圆的无人艇区域覆盖搜寻规划优化[J]. 系统工程与电子技术, 2022, 44(7): 2263-2269.
[5]	冯蕴雯, 陈俊宇, 路成. 民用飞机多地域航材支援网络模型研究[J]. 系统工程与电子技术, 2022, 44(5): 1553-1561.
[6]	孙剑炜, 王超, 施庆展, 任文博, 尧泽昆, 袁乃昌. 基于遗传算法的相位调制波形智能优化[J]. 系统工程与电子技术, 2022, 44(3): 722-729.
[7]	薛乃阳, 丁丹, 王红敏, 刘步花. 基于改进遗传算法的多类测控资源调度方法[J]. 系统工程与电子技术, 2021, 43(9): 2535-2543.
[8]	陈云翔, 饶益, 蔡忠义, 王泽洲. 基于改进相似性的装备部件剩余寿命预测及经济性储备策略[J]. 系统工程与电子技术, 2021, 43(9): 2688-2696.
[9]	赵禄达, 王斌, 曾威. 进攻战斗电子对抗兵力需求的三层规划模型[J]. 系统工程与电子技术, 2021, 43(6): 1564-1571.
[10]	王力, 刘子奇. WPA-IGA-BP神经网络的模拟电路故障诊断[J]. 系统工程与电子技术, 2021, 43(4): 1133-1143.
[11]	胡春宇, 刘卫东, 于天翔, 周立尧, 冯晨. 基于无人机实时数据多波次任务规划模型分析[J]. 系统工程与电子技术, 2021, 43(3): 747-754.
[12]	闫珍珍, 李波, 杨懋, 闫中江. 基于遗传算法的混叠式非正交多址接入方法[J]. 系统工程与电子技术, 2021, 43(3): 832-838.
[13]	刘庆国, 刘新学, 武健, 李亚雄, 陈豪. 基于改进NSGA-Ⅲ的多SGSW火力分配优化[J]. 系统工程与电子技术, 2020, 42(9): 1995-2002.
[14]	张盛魁, 姚志成, 何岷, 范志良, 杨剑. 基于时频方差聚类的FH信号参数盲估计[J]. 系统工程与电子技术, 2020, 42(8): 1662-1667.
[15]	郭媛, 索志勇, 王婷婷, 廖志强. 弹载SAR系统参数优化设计方法[J]. 系统工程与电子技术, 2020, 42(7): 1478-1483.