Earth observation satellite scheduling for emergency tasks

doi:10.21629/JSEE.2019.05.11

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (5): 931-945.doi: 10.21629/JSEE.2019.05.11

• Systems Engineering • Previous Articles Next Articles

Earth observation satellite scheduling for emergency tasks

Haiquan SUN^1,²(), Wei XIA^1,^2,*(), Xiaoxuan HU^1,²(), Chongyan XU³()

¹ School of Management, Hefei University of Technology, Hefei 230009, China
² Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China
³ Graduate School, Beijing Institute of Remote Sensing Information, Beijing 100192, China

Received:2019-03-15 Online:2019-10-08 Published:2019-10-09
Contact: Wei XIA E-mail:sunhaiquan2015@163.com;xiawei@hfut.edu.cn;xiaoxuanhu@hfut.edu.cn;xuchongy1970@sina.com
About author:SUN Haiquan was born in 1993. He received his B.S. degree from Hefei University of Technology in 2016. He is currently working for his M.S. degree in management science and engineering at Hefei University of Technology. His research interest is satellite intelligent scheduling. E-mail: sunhaiquan2015@163.com|XIA Wei was born in 1983. He received his Ph.D. degree from Hefei University of Technology in 2014. Currently he is working in Hefei University of Technology as a lecturer. His research interests include satellite intelligent scheduling and controlling. E-mail: xiawei@hfut.edu.cn|HU Xiaoxuan was born in 1978. He received his B.S. degree and Ph.D. degree from Hefei University of Technology in 1999 and 2007, respectively. He is a professor at Hefei University of Technology. His research interests include satellite scheduling and UAV planning. E-mail: xiaoxuanhu@hfut.edu.cn|XU Chongyan was born in 1970. She received her B.S. degree from Beijing Institute of Technology in 2003. Now she is working in Beijing Institute of Remote Sensing Information. Her research interest is space remote sensing satellite application. E-mail: xuchongy1970@sina.com
Supported by:
the National Natural Science Foundation of China(71671059);This work was supported by the National Natural Science Foundation of China (71671059)

Abstract

Abstract:

The earth observation satellites (EOSs) scheduling problem for emergency tasks often presents many challenges. For example, the scheduling calculation should be completed in seconds, the scheduled task rate is supposed to be as high as possible, the disturbance measure of the scheme should be as low as possible, which may lead to the loss of important observation opportunities and data transmission delays. Existing scheduling algorithms are not designed for these requirements. Consequently, we propose a rolling horizon strategy (RHS) based on event triggering as well as a heuristic algorithm based on direct insertion, shifting, backtracking, deletion, and reinsertion (ISBDR). In the RHS, the driven scheduling mode based on the emergency task arrival and control station time window events are designed to transform the long-term, large-scale problem into a short-term, small-scale problem, which can improve the schedulability of the original scheduling scheme and emergency response sensiti-vity. In the ISBDR algorithm, the shifting rule with breadth search capability and backtracking rule with depth search capability are established to realize the rapid adjustment of the original plan and improve the overall benefit of the plan and early completion of emergency tasks. Simultaneously, two heuristic factors, namely the emergency task urgency degree and task conflict degree, are constructed to improve the emergency task scheduling guidance and algorithm efficiency. Finally, we conduct extensive experiments by means of simulations to compare the algorithms based on ISBDR and direct insertion, shifting, deletion, and reinsertion (ISDR). The results demonstrate that the proposed algorithm can improve the timeliness of emergency tasks and scheduling performance, and decrease the disturbance measure of the scheme, therefore, it is more suitable for emergency task scheduling.

Key words: emergency task, rolling horizon, shifting rule, backtracking rule

Haiquan SUN, Wei XIA, Xiaoxuan HU, Chongyan XU. Earth observation satellite scheduling for emergency tasks[J]. Journal of Systems Engineering and Electronics, 2019, 30(5): 931-945.

Figures/Tables 22

Fig 1

Fig 2

Fig 3

Fig 4

${ETW_{kj}^b}$ set diagram"

Fig 4

Fig 5

${ST_j^d}$ and ${TW_j^d}$ diagram"

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Fig 12

Table 1

Table 2

Table 3

Fig 13

Table 4

Fig 14

Fig 15

Table 5

Algorithm running value statistics"

Scale	Total scheduled task value		Total scheduled task number		Total scheduled emergency task value		Total scheduled emergency task number		Total scheduled emergency task early completion time/ms}
Scale	ISBDR	ISDR	ISBDR	ISDR	ISBDR	ISDR	ISBDR	ISDR	ISBDR	ISDR
20-400	155.694 767 9	155.306 391 7	411	410	33.519 924 77	33.519 924 77	20	20	963 500	913 837
40-400	187.355 917 2	186.910 33	429	427	65.482 530 32	65.482 530 32	39	39	1 988 093	1 870 252
60-400	216.244 272	215.806 892 7	445	443	95.050 628 22	95.050 628 22	57	57	2 769 542	2 694 203
80-400	246.844 995 1	246.177 952 2	462	460	125.708 562 4	125.708 562 4	75	75	3 836 727	3 606 310
20-600	214.249 678 1	214.242 656 4	593	592	33.519 924 77	33.519 924 77	20	20	927 043	852 168
40-600	245.635 376 1	245.614 460 6	610	608	65.482 530 32	65.482 530 32	39	39	1 963 499	1 674 982
60-600	274.048 733 4	273.996 054 6	624	622	95.050 628 22	95.050 628 22	57	57	2 813 932	2 354 263
80-600	303.039 729 7	302.876 002	641	637	124.041 624 6	124.041 624 6	74	74	3 763 401	3 368 258
20-800	269.702 707 5	269.275 882 1	766	765	33.519 924 77	33.519 924 77	20	20	960 357	835 465
40-800	300.988 291	300.222 456 4	781	780	65.482 530 32	65.482 530 32	39	39	1 925 611	1 800 719
60-800	329.113 319 4	328.448 993 6	796	792	95.050 628 22	95.050 628 22	57	57	2 698 694	2 475 511
80-800	359.537 311 6	358.851 915 4	812	808	125.708 562 4	125.708 562 4	75	75	3 698 408	3 301 407
20-1 000	323.420 770 7	321.856 189 6	935	926	33.519 924 77	33.519 924 77	20	20	945 258	887 000
40-1 000	354.063 524 6	352.471 790 3	950	942	65.482 530 32	65.482 530 32	39	39	1 897 306	1 672 188
60-1 000	382.226 183 8	380.508 810 4	965	955	95.050 628 22	95.050 628 22	57	57	2 566 006	2 314 756
80-1 000	412.148 476 1	410.565 007 6	980	971	125.708 562 4	125.708 562 4	75	75	3 619 846	3 252 925

Table 5

Fig 16

Fig 17

References 30

1	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. Computers&Industrial Engineering, 2017, 113, 576- 588.
2	NIU X, TANG H, WU L, et al. Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events. Mathematical Problems in Engineering, 2015, 2015 (4): 731734.
3	NIU X, TANG H, WU L, et al. Satellite scheduling of large areal tasks for rapid response to natural disaster using a multiobjective genetic algorithm. International Journal of Disaster Risk Reduction, 2018, 28, 813- 825. doi: 10.1016/j.ijdrr.2018.02.013
4	GUO C, XIONG W, LIU C. Research on emergency mission planning of earth observation satellites. Proc. of the IEEE International Conference on Computer Communication and Internet, 2016, 191- 195.
5	WANG M, DAI G, VASILE M. Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites. Mathematical Problems in Engineering, 2014, 2014 (5): 234928.
6	BERTSIMAS D, GRIFFITH J D, GUPTA V, et al. A comparison of Monte Carlo tree search and rolling horizon optimization for large-scale dynamic resource allocation problems. European Journal of Operational Research, 2014, 263 (2): 664- 678.
7	LV Y L, ZHANG J, QIN W. A genetic regulatory networkbased method for dynamic hybrid flow shop scheduling with uncertain processing times. Applied Sciences, 2017, 7 (1) doi: 10.3390/app7010023
8	CHANG D, FANG T, FAN Y. Dynamic rolling strategy for multi-vessel quay crane scheduling. Advanced Engineering Informatics, 2017, 34, 60- 69. doi: 10.1016/j.aei.2017.09.001
9	ZHU X, CHEN H, YANG L T, et al. Energy-aware rollinghorizon scheduling for real-time tasks in virtualized cloud data centers. Proc. of the IEEE International Conference on High Performance Computing and Communications&IEEE International Conference on Embedded and Ubiquitous Computing, 2013: 1119-1126.
10	STOLLETZ R, ZAMORANO E. A rolling planning horizon heuristic for scheduling agents with different qualifications. Transportation Research Part E:Logistics&Transportation Review, 2014, 68, 39- 52.
11	CORDEAU J F, DELL'AMICO M, FALAVIGNA S, et al. A rolling horizon algorithm for auto-carrier transportation. Transportation Research Part B, 2015, 76, 68- 80. doi: 10.1016/j.trb.2015.02.009
12	LUO L, LUO Y, YOU Y, et al. A MIP model for rolling horizon surgery scheduling. Journal of Medical Systems, 2016, 40 (5): 1- 7.
13	HALL N G, MAGAZINE M J. Maximizing the value of a space mission. European Journal of Operational Research, 2007, 78 (2): 224- 241.
14	PEMBERTON A J C, GREENWALD B L G. On the need for dynamic scheduling of imaging satellites. International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences, 2002, 34 (1): 165- 171.
15	HE C, ZHU X, GUO H, et al. Rolling-horizon scheduling for energy constrained distributed real-time embedded systems. Journal of Systems&Software, 2012, 85 (4): 780- 794.
16	QIU D, HE C, LIU J, et al. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy. The Scientific World Journal, 2013. doi: 10.1155/2013/304047
17	WANG J, YANG L T, ZHU X, et al. Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging. IEEE Trans. on Parallel&Distributed Systems, 2014, 25 (9): 2275- 2285.
18	ZHAI X, NIU X, TANG H, et al. Robust satellite scheduling approach for dynamic emergency tasks. Mathematical Problems in Engineering, 2015. doi: 10.1155/2015/482923
19	WANG J, ZHU X, YANG L T, et al. Towards dynamic realtime scheduling for multiple earth observation satellites. Journal of Computer&System Sciences, 2015, 81 (1): 110- 124.
20	WU G H, MA M H, ZHU J H, et al. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks. Journal of Systems Engineering and Electronics, 2012, 23 (5): 723- 733. doi: 10.1109/JSEE.2012.00089
21	WANG J M, LI J F, TAN Y J. Study on heuristic algorithm for dynamic scheduling problem of earth observing satellites. Proc. of the IEEE 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007: 9-14.
22	BIANCHESSI N, CORDEAU J F, DESROSIERS J, et al. A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites. European Journal of Operational Research, 2007, 177 (2): 750- 762.
23	TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P, et al. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite. European Journal of Operational Research, 2015, 245 (2): 542- 554.
24	HAO H, JIANG W, LI Y. Improved algorithms to plan missions for agile earth observation satellites. Journal of Systems Engineering and Electronics, 2014, 25 (5): 811- 821. doi: 10.1109/JSEE.2014.00094
25	LIU X, LAPORTE G, CHEN Y, et al. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers&Operations Research, 2017, 86, 41- 53.
26	ROYCHOWDHURY S, ALLEN T T, ALLEN N B, et al. A genetic algorithm with an earliest due date encoding for scheduling automotive stamping operations. Computers&Industrial Engineering, 2017, 105, 201- 209.
27	CHEN H, LI L M, ZHONG Z N, et al. Approach for earth observation satellite real-time and playback data transmission scheduling. Journal of Systems Engineering and Electronics, 2015, 26 (5): 982- 992. doi: 10.1109/JSEE.2015.00107
28	CHEN H, WU J, SHI W, et al. Coordinate scheduling approach for EDS observation tasks and data transmission jobs. Journal of Systems Engineering and Electronics, 2016, 27 (4): 822- 835. doi: 10.21629/JSEE.2016.04.11
29	SONG B, YAO F, CHEN Y, et al. A hybrid genetic algorithm for satellite image downlink scheduling problem. Discrete Dynamics in Nature&Society, 2018, 2018, 1531452.
30	CHEN H, LI J, PENG S, et al. Approximate path searching method for single-satellite observation and transmission task planning problem. Mathematical Problems in Engineering, 2017. doi: 10.1155/2017/7304506

Sat_id	Sat_name	Sat_sensor_name	Sensor_msg/(°)	Apogee/km	Perigee/km
0	FENGYUN_1D_27431	FY1D_Sensor1	35	872	851
1	FENGYUN_3A_32958	FY3A_Sensor1	25	827	826
2	GAOFEN_1_39150	GF1_Sensor1	25	652	628
3	GAOFEN_2_40118	GF2_Sensor1	35	633	621
4	YAOGAN_12_37875	YG12_Sensor1	30	491	488
5	YAOGAN_13_37941	YG13_Sensor1	25	514	511
6	YAOGAN_14_38257	YG14_Sensor1	25	479	471
7	YAOGAN_15_38354	YG15_Sensor1	25	1 206	1 196
8	YAOGAN_16A_39011	YG16A_Sensor1	25	1 162	1 018
9	YAOGAN_17A_39239	YG17A_Sensor1	35	1 184	997
10	YAOGAN_18_39363	YG18_Sensor1	25	514	510
11	YAOGAN_19_39410	YG19_Sensor1	30	1 207	1 201
12	YAOGAN_20A_40109	YG20A_Sensor1	25	1 122	1 059
13	YAOGAN_21_40143	YG21_Sensor1	25	498	482
14	YAOGAN_22_40275	YG22_Sensor1	25	1 207	1 198
15	YAOGAN_23_40305	YG23_Sensor1	30	513	511
16	YAOGAN_24_40310	YG24_Sensor1	25	651	628
17	YAOGAN_25A_40338	YG25A_Sensor1	30	1 105	1 076
18	YAOGAN_26_40362	YG26_Sensor1	30	491	484
19	YAOGAN_27_40878	YG27_Sensor1	25	1 207	1 193

Con_id	Con_name	Con_lon	Con_lat	Con_alt
0	KUNMING	102.59	24.97	0
1	HAERBIN	126.848	45.67	0
2	CHENGDU	104.04	31.26	0
3	GUANGZHOU	113.401	23.08	0
4	HANGZHOU	120.103	30.35	0
5	LASA	91.121	29.65	0

Gro_id	Gro_name	Gro_lon	Gro_lat	Gro_alt
0	BEIJING	116.595	39.04	0
1	CHANGSHA	113.037	28.25	0
2	TAIYUAN	112.585	37.82	0
3	WULUMUQI	87.395	43.86	0

Earth observation satellite scheduling for emergency tasks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 22

References 30

Related Articles 1

Recommended Articles

Metrics

Comments

Initial scheduling scheme		Emergency task scale	Algorithm
Satellite scale	General task scale	Emergency task scale	Algorithm
20	400	20, 40, 60, 80	ISBDR, ISDR
	600
	800
	1 000