Reactive scheduling of multiple EOSs under cloud uncertainties: model and algorithms

doi:10.23919/JSEE.2021.000015

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (1): 163-177.doi: 10.23919/JSEE.2021.000015

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Reactive scheduling of multiple EOSs under cloud uncertainties: model and algorithms

Jianjiang WANG¹(), Xuejun HU^2,*(), Chuan HE³

¹ College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
² Business School, Hunan University, Changsha 410082, China
³ Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China

Received:2020-03-18 Online:2021-02-25 Published:2021-02-25
Contact: Xuejun HU E-mail:jianjiangwang@nudt.edu.cn;xuejun_hu@hnu.edu.cn
About author:|WANG Jianjiang was born in 1986. He received his B.S. and Ph.D. degrees in military operations research from National University of Defense Technology, Changsha, China, in 2009 and 2015, respectively. He is currently a lecturer with National University of Defense Technology, Changsha, China. His research interests are combinational optimization, satellite scheduling, and project scheduling. E-mail: jianjiangwang@nudt.edu.cn||HU Xuejun was born in 1989. She received her B.S. and Ph.D. degrees in management science and engineering from Huazhong University of Science and Technology, Changsha, China, in 2011 and 2016, respectively. She is currently an associate professor in the Business School, Hunan University, Changsha, China. Her research interests are satellite scheduling, project scheduling, and project control. E-mail: xuejun_hu@hnu.edu.cn||HE Chuan was born in 1985. He received his B.S. and M.S. degrees in military operations research from PLA Army Academy of Artillery and Air Defense in 2007 and 2010, respectively. He received his Ph.D. degree in military operations research from National University of Defense Technology, Changsha, China, in 2013. He is currently a research assistant in Beijing Institute of Tracking and Telecommunications Technology. His research interests are satellite application and algorithm design. E-mail: chuanhe@nudt.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (71801218; 71701067; 72071075), the Research Project of National University of Defense Technology (ZK18-03-16), and the Natural Science Foundation of Hunan Province, China (2020JJ4672; 2019JJ50039)

Abstract

Abstract:

Most earth observation satellites (EOSs) are low-orbit satellites equipped with optical sensors that cannot see through clouds. Hence, cloud coverage, high dynamics, and cloud uncertainties are important issues in the scheduling of EOSs. The proactive-reactive scheduling framework has been proven to be effective and efficient for the uncertain scheduling problem and has been extensively employed. Numerous studies have been conducted on methods for the proactive scheduling of EOSs, including expectation, chance-constrained, and robust optimization models and the relevant solution algorithms. This study focuses on the reactive scheduling of EOSs under cloud uncertainties. First, using an example, we describe the reactive scheduling problem in detail, clarifying its significance and key issues. Considering the two key objectives of observation profits and scheduling stability, we construct a multi-objective optimization mathematical model. Then, we obtain the possible disruptions of EOS scheduling during execution under cloud uncertainties, adopting an event-driven policy for the reactive scheduling. For the different disruptions, different reactive scheduling algorithms are designed. Finally, numerous simulation experiments are conducted to verify the feasibility and effectiveness of the proposed reactive scheduling algorithms. The experimental results show that the reactive scheduling algorithms can both improve observation profits and reduce system perturbations.

Key words: earth observation satellite (EOS), uncertainty of clouds, reactive scheduling, multi-objective optimization, event-driven, heuristic

Jianjiang WANG, Xuejun HU, Chuan HE. Reactive scheduling of multiple EOSs under cloud uncertainties: model and algorithms[J]. Journal of Systems Engineering and Electronics, 2021, 32(1): 163-177.

Figures/Tables 14

Fig 1

Table 1

Fig 2

Fig 3

Fig 4

Fig 5

Table 2

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Table 3

Table 4

References 46

1	BIANCHESSI N, CORDEAU J F, DESROSIERS J, et al A heuristic for the multisatellite, multi-orbit and multi-user management of earth observation satellites. European Journal of Operational Research, 2007, 177 (2): 750- 762. doi: 10.1016/j.ejor.2005.12.026
2	WANG J J, DEMEULEMEESTER E, QIU D S A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds. Computers & Operations Research, 2016, 74, 1- 13.
3	HABET D, VASQUEZ M, VIMONT Y Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite. Computational Optimization and Applications, 2010, 47 (2): 307- 333. doi: 10.1007/s10589-008-9220-7
4	GABREL V Strengthened 0-1 linear formulation for the daily satellite mission planning. Journal of Combinatorial Optimization, 2006, 11 (3): 341- 346. doi: 10.1007/s10878-006-7912-4
5	MARINELLI F, SALVATORE N, ROSSI F, et al A Lagrange heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 2011, 38 (11): 1572- 1583.
6	KUCUK M, YILDIZ S T. A constraint programming approach for agile earth observation satellite scheduling problem. Proc. of the 9th International Conference on Recent Advances in Space Technologies, 2019: 613–617.
7	QAMAR A, SALAH E E, BADRAN K M, et al Mission planning and scheduling for earth observation space system. International Journal of System of Systems Engineering, 2020, 10 (1): 24- 38. doi: 10.1504/IJSSE.2020.105422
8	WOLFE J, STEPHEN S E Three scheduling algorithms applied to the earth observing systems domain. Management Science, 2000, 46 (1): 148- 168. doi: 10.1287/mnsc.46.1.148.15134
9	BARKAOUI M, BERGER J A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation. Journal of the Operational Research Society, 2020, 71 (9): 1390- 1410. doi: 10.1080/01605682.2019.1609891
10	SARKHEYLI A, VAGHEI B G, BAGHERI A. New tabu search heuristic in scheduling earth observation satellites. Proc. of the 2nd International Conference on Software Technology and Engineering, 2010. DOI: 10.1109/ICSTE.2010.5608821.
11	ZUFFEREY N, AMSTUTZ P, GIACCARI P Graph colouring approaches for a satellite range scheduling problem. Journal of Scheduling, 2008, 11 (4): 263- 277. doi: 10.1007/s10951-008-0066-8
12	CHU X G, CHEN Y N, TAN Y J An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 2017, 60 (9): 2077- 2090. doi: 10.1016/j.asr.2017.07.026
13	GABREL V, VANDERPOOTEN D Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. European Journal of Operational Research, 2002, 139 (3): 533- 542. doi: 10.1016/S0377-2217(01)00188-6
14	PENG G, SONG G. XING L, et al An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 2020, 120, 104946.
15	HU X H, ZHU W M, AN B, et al A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem. Computers & Operations Research, 2019, 104, 74- 89.
16	ZHU W M, HU X X, XIA W, et al A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests. Computers & Industrial Engineering, 2019, 130, 97- 107.
17	ZHAO Y B, DU B, LI S Agile satellite mission planning via task clustering and double-layer tabu algorithm. Computer Modeling in Engineering & Sciences, 2020, 122 (1): 235- 257.
18	SALMAN A A, AHMAD I, OMRAN M G A metaheuristic algorithm to solve satellite broadcast scheduling problem. Information Sciences, 2015, 322, 72- 91. doi: 10.1016/j.ins.2015.06.016
19	LI Z L, LI X J A multi-objective binary-encoding differential evolution algorithm for proactive scheduling of agile earth observation satellites. Advances in Space Research, 2019, 63 (10): 3258- 3269. doi: 10.1016/j.asr.2019.01.043
20	WU K, ZHANG D X, CHEN Z H, et al Multi-type multi-objective imaging scheduling method based on improved NSGA-Ⅲ for satellite formation system. Advances in Space Research, 2019, 63 (8): 2551- 2565. doi: 10.1016/j.asr.2019.01.006
21	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. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
22	ZHANG Z J, HU F N, ZHANG N Ant colony algorithm for satellite control resource scheduling problem. Applied Intelligence, 2018, 48 (10): 1- 11.
23	TANGPATTANAKUL P, JOZEFOWIEZ N, LOPEZ P 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. doi: 10.1016/j.ejor.2015.03.011
24	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. Computers & Operations Research, 2017, 86, 41- 53.
25	HE L, LIU X L, LAPORTE G, et al An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100, 12- 25.
26	PENG G S, DEWIL R, VERBEECK C, et al Agile earth observation satellite scheduling: an orienteering problem with time-dependent profits and travel times. Computers & Operations Research, 2019, 111, 84- 98.
27	GLOBUS A, CRAWFORD J, LOHN J, et al A comparison of techniques for scheduling fleets of earth-observing. Journal of the Operational Research Society, 2003, 56 (8): 962- 968.
28	ZHU W, HU X, XIA W, et al A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing, 2019, 23 (1): 181- 196. doi: 10.1007/s00500-017-2889-8
29	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.
30	WANG J, ZHU X, QIU D, et al Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging. IEEE Trans. on Parallel and Distributed Systems, 2014, 25 (9): 2275- 2285. doi: 10.1109/TPDS.2013.156
31	WANG J J, ZHU X M, YANG L T, et al Towards dynamic real-time scheduling for multiple earth observation satellites. Journal of Computer and System Sciences, 2015, 81 (1): 110- 124. doi: 10.1016/j.jcss.2014.06.016
32	XIE P, WANG H, CHEN Y N, et al A heuristic algorithm based on temporal conflict network for agile Earth observing satellite scheduling problem. IEEE Access, 2019, 7, 61024- 61033. doi: 10.1109/ACCESS.2019.2902669
33	HE Y M, CHEN Y W, LU J M, et al Scheduling multiple agile earth observation satellites with an edge computing framework and a constructive heuristic algorithm. Journal of Systems Architecture, 2019, 95, 55- 66. doi: 10.1016/j.sysarc.2019.03.005
34	KARAPETYAN D, MINIC S M, MALLADI K T, et al Satellite downlink scheduling problem: a case study. Omega, 2015, 53, 115- 123. doi: 10.1016/j.omega.2015.01.001
35	SUN H Q, XIA W, HU X X, et al Earth observation satellite scheduling for emergency tasks. Journal of Systems Engineering and Electronics, 2019, 30 (5): 931- 945. doi: 10.21629/JSEE.2019.05.11
36	BEAUMET G, VERFAILLIE G, CHARMEAU M C Feasibility of autonomous decision making on board an agile earth-observing satellite. Computation Intelligence, 2011, 27 (1): 123- 139. doi: 10.1111/j.1467-8640.2010.00375.x
37	LIN W C, LIAO D Y, LIU C Y, et al Daily imaging scheduling of an Earth observation satellite. IEEE Trans. on Systems Man and Cybernetics Part A—Systems and Humans, 2005, 35 (2): 213- 223. doi: 10.1109/TSMCA.2005.843380
38	LEMAITRE M, VERFAILLIE G, JOUHAUD F, et al. How to manage the new generation of agile earth observation satellites. Proc. of the International Symposium on Artificial Intelligence, Robotics and Automation in Space, 2000. DOI: 10.1002/ppsc.201300352.
39	LIAO D Y, TANG Y Imaging order scheduling of an earth observation satellite. IEEE Trans. on Systems Man and Cybernetics Part C—Applications and Reviews, 2007, 37 (5): 794- 802. doi: 10.1109/TSMCC.2007.900668
40	VALICKA C G, GARCIA D, STAID A, et al Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty. European Journal of Operational Research, 2019, 275 (2): 431- 445. doi: 10.1016/j.ejor.2018.11.043
41	WANG J J, DEMEULEMEESTER E, HU X J, et al Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds. IEEE Systems Journal, 2019, 13 (3): 3556- 3567. doi: 10.1109/JSYST.2018.2874223
42	WANG J J, DEMEULEMEESTER E, HU X J, et al Expectation and SAA models and algorithms for scheduling of multiple Earth observation satellites under the impact of clouds. IEEE Systems Journal, 2020, 14 (4): 5451- 5462. doi: 10.1109/JSYST.2019.2961236
43	SAMIMI A, NIKZAD M Complete active-reactive power resource scheduling of smart distribution system with high penetration of distributed energy resources. Journal of Modern Power Systems & Clean Energy, 2017, 5 (6): 863- 875.
44	HU X J, WANG J J, LENG K J The interaction between critical chain sequencing, buffer sizing, and reactive actions in a CC/BM framework. Asia Pacific Journal of Operational Research, 2019, 36 (3): 1950010. doi: 10.1142/S0217595919500106
45	PAPROCKA I, KEMPA W M. Searching for a method of basic schedules generation which influences over the performance of predictive and reactive schedules. Proc. of the 37th International Conference on Information Systems Architecture and Technology, 2017: 233–242.
46	VIERIA G E, HERRMANN J W, LIN E Rescheduling manufacturing systems: a framework of strategies, policies and methods. Journal of Scheduling, 2003, 6 (1): 39- 62. doi: 10.1023/A:1022235519958

Task number	Profit	Orbit number
		1		2		3
		Time window	Probability	Time window	Probability	Time window	Probability
1	9	[10,16]	0.96	[20,24]	0.88	[30,34]	0.64
2	6	—	—	[22,26]	0.92	[24,18]	0.84
3	3	[24,30]	0.72	—	—	[18,22]	0.78

Satellite	Slewing velocity	Startup time	Shutdown time	Stability time	Memory/time	Energy/time	Energy/(°)
CBERS-2	2	5	8	3	2	1.5	1.5
IKONOS-2	2.5	8	5	6	4	2.5	4
SPOT-5	3	10	10	9	3	3.5	1

Performance	Number of orbits	Number of tasks	Proactive-reactive scheduling			Proactive scheduling
Performance	Number of orbits	Number of tasks	Min	Ave	Max	Min	Ave	Max
Profit	21	200	377.6	455.612	517.1	314.3	405.348	485.2
		300	323.5	398.354	460.7	272.6	360.194	435.6
		400	363.0	444.708	512.6	298.5	397.551	485.5
	42	200	679.5	762.801	828.9	540.7	650.689	751.4
		300	752.1	871.550	948.8	623.0	742.234	850.1
		400	748.8	840.233	914.8	572.4	705.377	826.6
Perturbation	21	200	18.0	50.182	89.4	29.6	70.267	116.0
		300	10.6	39.285	72.7	18.0	52.642	92.4
		400	12.8	42.686	79.0	20.8	57.980	100.0
	42	200	38.7	77.059	120.7	68.8	127.369	188.0
		300	40.6	78.457	125.0	76.5	129.736	188.5
		400	27.8	63.480	105.0	56.0	110.822	171.2

Performance	Number of orbits	Number of tasks	Proactive-reactive scheduling			Proactive scheduling
Performance	Number of orbits	Number of tasks	Min	Ave	Max	Min	Ave	Max
Profit	21	200	533.5	606.181	667.5	482.8	569.111	644.6
		300	774.5	873.819	955.9	701.8	814.472	912.1
		400	959.6	1 078.932	1170.3	873.1	998.408	1107.2
	42	200	684.0	750.485	801.1	595.1	683.998	759.9
		300	1 000.0	1308.346	1375.5	1000.0	1223.268	1319.1
		400	1 000.0	1583.450	1662.8	1000.0	1456.914	1576.8
Perturbation	21	200	27.6	65.874	110.6	38.4	85.930	138.4
		300	50.0	101.452	160.3	74.8	134.396	203.2
		400	69.8	125.030	190.6	102.4	168.062	243.2
	42	200	23.0	57.938	97.7	46.0	94.130	147.6
		300	51.4	94.974	149.9	80.5	142.220	208.5
		400	78.0	131.198	194.0	130.4	205.098	283.2

[1]	Jiaxin HU, Leping YANG, Huan HUANG, Yanwei ZHU. Optimal reconfiguration of constellation using adaptive innovation driven multiobjective evolutionary algorithm [J]. Journal of Systems Engineering and Electronics, 2021, 32(6): 1527-1538.
[2]	Zining WANG, Min LIN, Xiaogang TANG, Kefeng GUO, Shuo HUANG, Ming CHENG. Multi-objective robust secure beamforming for cognitive satellite and UAV networks [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 789-798.
[3]	Zikai ZHANG, Qiuhua TANG, Zixiang LI, Dayong HAN. An efficient migrating birds optimization algorithm with idle time reduction for Type-I multi-manned assembly line balancing problem [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 286-296.
[4]	Shiyun LI, Sheng ZHONG, Zhi PEI, Wenchao YI, Yong CHEN, Cheng WANG, Wenzhu ZHANG. Multi-objective reconfigurable production line scheduling for smart home appliances [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 297-317.
[5]	Jian WU, Fang LU, Jiawei ZHANG, Jiawei ZHANG, Lining XING. Design of task priority model and algorithm for imaging observation problem [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 321-334.
[6]	Zhen XU, Enze ZHANG, Qingwei CHEN. Rotary unmanned aerial vehicles path planning in rough terrain based on multi-objective particle swarm optimization [J]. Journal of Systems Engineering and Electronics, 2020, 31(1): 130-141.
[7]	Hongwei LI, Jianyong LIU, Liang CHEN, Jingbo BAI, Yangyang SUN, Kai LU. Chaos-enhanced moth-flame optimization algorithm for global optimization [J]. Journal of Systems Engineering and Electronics, 2019, 30(6): 1144-1159.
[8]	Yan'gang LIANG, Zheng QIN. A decision support system for satellite layout integrating multi-objective optimization and multi-attribute decision making [J]. Journal of Systems Engineering and Electronics, 2019, 30(3): 535-544.
[9]	Jiale GAO, Qinghua XING, Chengli FAN, Zhibing LIANG. Double adaptive selection strategy for MOEA/D [J]. Journal of Systems Engineering and Electronics, 2019, 30(1): 132-143.
[10]	Jiting Li, Sheng Zhang, Xiaolu Liu, and Renjie He. Multi-objective evolutionary optimization for geostationary orbit satellite mission planning [J]. Systems Engineering and Electronics, 2017, 28(5): 934-945.
[11]	Ying Zhang, Rennong Yang, Jialiang Zuo, and Xiaoning Jing. Enhancing MOEA/D with uniform population initialization, weight vector design and adjustment using uniform design [J]. Journal of Systems Engineering and Electronics, 2015, 26(5): 1010-1022.
[12]	Haipeng Ren* and Yang Zhao. Immune particle swarm optimization of linear frequency modulation in acoustic communication [J]. Systems Engineering and Electronics, 2015, 26(3): 450-456.
[13]	Aijun Zhu, Chuanpei Xu, Zhi Li, JunWu, and Zhenbing Liu. Hybridizing grey wolf optimization with differential evolution for global optimization and test scheduling for 3D stacked SoC [J]. Journal of Systems Engineering and Electronics, 2015, 26(2): 317-328.
[14]	Lixia Han, Shujuan Jiang, and Shaojiang Lan. Novel electromagnetism-like mechanism method for multiobjective optimization problems [J]. Journal of Systems Engineering and Electronics, 2015, 26(1): 182-.
[15]	Xiaoxue Zhang, Shu Tang, Aimin Luo, and Xueshan Luo. System deployment optimization in architecture design [J]. Journal of Systems Engineering and Electronics, 2014, 25(2): 237-248.

Reactive scheduling of multiple EOSs under cloud uncertainties: model and algorithms

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 14

References 46

Related Articles 15

Recommended Articles

Metrics

Comments