基于任务合成机制的多星调度问题

doi:10.3969/j.issn.1001-506X.2021.01.21

Abstract

Abstract:

In the traditional pattern, the satellite adopts the single task observation mode, in which the imaging accuracy of the task is high. However, the imaging quantity of the task is small and the utilization rate of the resource is extremely low. Therefore, a multi-task merging mechanism (MTMM) based on the single task observation mode is designed, which adopts the way of task merging in the case of ensuring the minimum imaging requirements of users. Firstly, on the basis of the merging task set, a multi-satellite scheduling model is established, and then an algorithm of improved ant colony optimization based on task merging (IACO-TM) is proposed for the model. In the algorithm, an adaptive ant window strategy, a forced disturbance mechanism and a parameters dynamic adjustment strategy of the algorithm are designed, so as to cut the ant search space effectively, avoid the algorithm falling into the local optimum and improve the convergence speed of the algorithm at the same time. Finally, a large number of simulation experiments are provided to verify the effectiveness of MTMM and IACO-TM, comparing with the algorithm of improved ant colony optimization (IACO) and the algorithm of traditional ant colony optimization based on task merging (TACO-TM).

Key words: multi-satellite scheduling, task merging, ant colony algorithm, self-adaption

CLC Number:

Songlian REN, Haiquan SUN, Peng JIN. Multi-satellite scheduling problem based on task merging mechanism[J]. Systems Engineering and Electronics, 2021, 43(1): 171-180.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Fig.6

Table 2

Fig.7

Fig.8

Fig.9

References 32

1	WALTON J . Models for the management of satellite-based sensors[J]. Massachusetts Institute of Technology, 1993, 15 (5): 23- 30.
2	WANG P , GAO P , TAN Y J . A model, a heuristic and a decision support system to solve the earth observing satellites fleet scheduling problem[J]. Computers & Industrial Engineering, 2011, 61 (2): 322- 335.
3	TANGPATTANAKUL P , JOZEFOWIEZ N , LOPEZ P . A multi-objective local search heuristic for scheduling earth observations taken by an agile satellite[J]. European Journal of Opera-tional Research, 2015, 245 (2): 542- 554.
4	CHO D H , KIM J H , CHOI H L , et al. Optimization-Based schedu-ling method for agile earth-observing satellite constellation[J]. Journal of Aerospace Information Systems, 2018, 15 (11): 611- 626.
5	BIANCHESSI N , CORDEAU J F , DESROSIERS J , et al. A heuristic for the multi-satellite, multi-orbit and multi-user mana-gement of earth observation satellites[J]. European Journal of Operational Research, 2007, 177 (2): 750- 762.
6	SONG Y J , HUANG D J , ZHOU Z Y , et al. An emergency task autonomous planning method of agile imaging satellite[J]. EURASIP Journal on Image & Video Processing, 2018, 1 (29): 367- 370.
7	WU G H , LIU J , MA M H , et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
8	LIU X L , BAI B C , CHEN Y W , et al. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics & Computation, 2014, 230, 687- 700.
9	WANG J J , ZHU X M , YANG L Y , et al. Towards dynamic real-time scheduling for multiple earth observation satellites[J]. Journal of Computer & System Sciences, 2015, 81 (1): 110- 124.
10	邱涤珊, 王建江, 吴朝波, 等. 基于任务合成的对地观测卫星应急调度方法[J]. 系统工程与电子技术, 2013, 35 (7): 1430- 1437.
	QIU D S , WANG J J , WU C B , et al. Emergency scheduling method of earth observation satellites based on task merging[J]. Systems Engineering and Electronics, 2013, 35 (7): 1430- 1437.
11	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.
12	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.
13	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 & Distributed Systems, 2014, 25 (9): 2275- 2285.
14	BATAILLE N , BLUMSTEIN D , BENSANA E , et al. Exact and approximate methods for the daily management of an earth observation satellite[J]. Rairo Operations Research, 2007, 41 (4): 381- 398.
15	HU X X , ZHU W M , AN B , et al. A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem[J]. Computers & Operations Research, 2019, 104 (1): 74- 89.
16	WU G H , WANG H L , PEDRYCZ W , et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Computers & Industrial Engineering, 2017, 113 (1): 576- 588.
17	ZHU W M , HU X X , XIA W , et al. A two-phase genetic annealing method for integrated earth observation satellite schedu-ling problems[J]. Soft Computing, 2019, 23 (1): 181- 196.
18	VASQUEZ M , HAO J K . A "logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J]. Computational Optimization & Applications, 2001, 20 (2): 137- 157.
19	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, 2019, 71 (9): 1390- 1410.
20	DORIGO, M. Optimization, learning and natural algorithms[D]. Italy: Politecnico di Milano, 1992.
21	DORIGO M. LUCA M . The Ant-Q algorithm applied to the nuclear reload problem[J]. Annals of Nuclear Energy, 2002, 29 (12): 1455- 1470.
22	THOMAS S , HOOS H H . MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16 (8): 889- 914.
23	吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J]. 计算机研究与发展, 1999, 36 (10): 1240- 1245.
	WU Q H , ZHANG J H , XU X H . Ant colony algorithm with mutation feature[J]. Computer Research and Development, 1999, 36 (10): 1240- 1245.
24	LUO K P . A hybrid binary artificial bee colony algorithm for the satellite photograph scheduling problem[J]. Engineering Optimization, 2020, 52 (8): 1421- 1440.
25	陈崚, 沈洁, 秦玲, 等. 基于分布均匀度的自适应蚁群算法[J]. 软件学报, 2003, 14 (8): 39- 47.
	CHEN L , SHEN J , QING L , et al. Adaptive ant colony algorithm based on equilibrium of distribution[J]. Journal of Software, 2003, 14 (8): 39- 47.
26	陈崚, 秦玲, 陈宏建, 等. 具有感觉和知觉特征的蚁群算法[J]. 系统仿真学报, 2003, 15 (10): 1418- 1425.
	CHEN L , QING L , CHEN J H , et al. Ant colony algorithm with characteristics of sensation and consciousness[J]. Journal of System Simulation, 2003, 15 (10): 1418- 1425.
27	CORDEAU J F , LAPORTE G . Maximizing the value of an earth observation satellite orbit[J]. Journal of the Operational Research Society, 2005, 56 (8): 962- 968.
28	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.
29	GABREL V , MOULET A , MURAT C , et al. A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts[J]. Annals of Operations Research, 1997, 69 (1): 115- 134.
30	XU R , CHEN H , LIANG X , et al. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization[J]. Expert Systems with Application, 2016, 51 (6): 195- 206.
31	CHEN X Y , REINELT G , DAI G M , et al. A mixed integer linear programming model for multi-satellite scheduling[J]. European Journal of Operational Research, 2019, 275 (2): 694- 707.
32	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 (1): 813- 825.

任务编号	卫星编号	开始时间窗	结束时间窗
afyf	GAOFEN_1_39150	2019/7/24 0:44:43	2019/7/24 0:45:34
mcat	GAOFEN_1_39150	2019/7/24 3:42:09	2019/7/24 3:42:58
xefp	YAOGAN_11_37165	2019/7/24 6:54:14	2019/7/24 6:55:03
⋮	⋮	⋮	⋮
xefp	YAOGAN_11_37165	2019/7/24 17:50:16	2019/7/24 17:51:05
kqsn	YAOGAN_15_38354	2019/7/24 17:50:52	2019/7/24 17:51:42
tmru	YAOGAN_15_38354	2019/7/24 22:22:37	2019/7/24 22:23:29

算例	规模	IACO-TM			IACO			TACO-TM
算例	规模	最佳收益	观测数量	时间/s	最佳收益	观测数量	时间/s	最佳收益	观测数量	时间/s
C1	100	533.67	43	2	555	45	1.67	538	44	3.33
C2		793.33	54	2.67	647.3	41	1.67	773	52	3.33
C3		719	58	3.33	569.67	45	1.33	694.33	53	3
C4	200	1 087.5	90	9	771	61	5.34	973.5	81	8.5
C5		1 050	87	7	766.33	61	5.34	986.5	82	8.5
C6		1 053	88	9	824.67	67	5.67	947.33	79	7
C7	400	1 009.67	83	23	998	80	26.33	892.67	73	22.34
C8		1 420.3	116	38.33	1 048	82	32	1 298.5	107	32
C9		1 354.8	112	30.2	1 009.5	80	28.75	1 188	98	24

[1]	Xinkang SONG, Shanghong ZHAO, Xiang WANG, Shaowei HAO. Collaborative construction and embedding strategy of aviation information network service function chain [J]. Systems Engineering and Electronics, 2022, 44(11): 3556-3563.
[2]	Mingjie SUN, Lin ZHOU, Yunlong YU, Jinling GU. Ant colony optimization based polymorphism-aware routing algorithm for AdHoc UAV network [J]. Systems Engineering and Electronics, 2021, 43(9): 2562-2572.
[3]	Lili LI, Xiaoyong ZHANG, Wei YUE. Broadcasting strategy based on greedy and ant colony algorithm in mobile ad hoc networks [J]. Systems Engineering and Electronics, 2020, 42(4): 926-932.
[4]	Qingdong HUANG, Runzhi YUAN, Minpeng GUO, Binyu SHI, Yiyuan CAO. Advanced low delay Q-routing algorithm based on full echoes [J]. Systems Engineering and Electronics, 2020, 42(4): 940-947.
[5]	Jingyu YAO, Peng JIN, Waiming ZHU, Xiaoxuan HU. Multi-satellite scheduling problem for regional targets with uneven income [J]. Systems Engineering and Electronics, 2020, 42(3): 638-645.
[6]	HE Lei, LIU Xiao-lu, CHEN Ying-wu, XING Li-ning. Cloud modeling and processing method for agile observing satellite mission planning [J]. Systems Engineering and Electronics, 2016, 38(4): 852-858.
[7]	XIAO Qin-kun, Wang Yi, LUO Yi-chuang. 3D path planning of ant colony algorithm using partial differential elevation modeling [J]. Systems Engineering and Electronics, 2015, 37(7): 1550-1561.
[8]	CHANG Tian-qing, CHEN Jun-wei, HAO Na, MA Dian-zhe. Terminating control of ant colony algorithm for armored unit dynamic weapon-target assignment [J]. Systems Engineering and Electronics, 2015, 37(2): 343-347.
[9]	LI Hong-liang， SONG Gui-bao， CAO Yan-jie. Cooperative path planning of multiple anti-ship missiles to multiple targets [J]. Systems Engineering and Electronics, 2013, 35(10): 2102-2109.
[10]	LI Ji-ying， DANG Jian-wu. Ant colony algorithm and application based on quantum space [J]. Systems Engineering and Electronics, 2013, 35(10): 2229-2232.
[11]	GUO Hao， WU Guohua， QIU Dishan. Intensive task clustering method for agile imaging satellites [J]. Journal of Systems Engineering and Electronics, 2012, 34(5): 931-935.
[12]	WU Hong, WANG Wei-ping, YANG Feng. Discretization method of continuous variables in Bayesian network parameter learning [J]. Journal of Systems Engineering and Electronics, 2012, 34(10): 2157-2162.
[13]	. Hybrid strategy with ant colony and simulated annealing algorithm and its improvement in target assignment [J]. Journal of Systems Engineering and Electronics, 2011, 33(5): 1182-.
[14]	YANG Jing, XU Mai, ZHAO Wei, XU Bao-guo. Energy efficient data gathering algorithm for wireless sensor networks [J]. Journal of Systems Engineering and Electronics, 2011, 33(3): 650-653.
[15]	WANG Lin, YU Lei, KOU Ying-xin, GAO Cheng-jin. Multi-sensor resource management method driven by task requirement [J]. Journal of Systems Engineering and Electronics, 2010, 32(9): 1925-1930.

Multi-satellite scheduling problem based on task merging mechanism

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 32

Related Articles 15

Recommended Articles

Metrics

Comments