Please wait a minute...
Frontiers of Engineering Management

ISSN 2095-7513

ISSN 2096-0255(Online)

CN 10-1205/N

Postal Subscription Code 80-905

Front. Eng    2023, Vol. 10 Issue (4) : 695-709    https://doi.org/10.1007/s42524-023-0263-3
Systems Engineering Theory and Application
General modeling and optimization technique for real-world earth observation satellite scheduling
Feng YAO1, Yonghao DU1(), Lei LI1, Lining XING2, Yingguo CHEN1
1. College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
2. School of Electronic Engineering, Xidian University, Xi’an 710075, China
 Download: PDF(5774 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Over the last two decades, many modeling and optimization techniques have been developed for earth observation satellite (EOS) scheduling problems, but few of them show good generality to be engineered in real-world applications. This study proposes a general modeling and optimization technique for common and real-world EOS scheduling cases; it includes a decoupled framework, a general modeling method, and an easy-to-use algorithm library. In this technique, a framework that decouples the modeling, constraints, and optimization of EOS scheduling problems is built. With this framework, the EOS scheduling problems are appropriately modeled in a general manner, where the executable opportunity, another format of the well-known visible time window per EOS operation, is viewed as a selectable resource to be optimized. On this basis, 10 types of optimization algorithms, such as Tabu search and genetic algorithm, and a parallel competitive memetic algorithm, are developed. For simplified EOS scheduling problems, the proposed technique shows better performance in applicability and effectiveness than the state-of-the-art algorithms. In addition, a complicatedly constrained real-world benchmark exampled by a four-EOS Chinese commercial constellation is provided, and the technique is qualified and outperforms the in-use scheduling system by more than 50%.

Keywords earth observation satellite      scheduling      general technique      optimization algorithm      commercial constellation      real-world      benchmark     
Corresponding Author(s): Yonghao DU   
Just Accepted Date: 04 July 2023   Online First Date: 09 August 2023    Issue Date: 07 December 2023
 Cite this article:   
Feng YAO,Yonghao DU,Lei LI, et al. General modeling and optimization technique for real-world earth observation satellite scheduling[J]. Front. Eng, 2023, 10(4): 695-709.
 URL:  
https://academic.hep.com.cn/fem/EN/10.1007/s42524-023-0263-3
https://academic.hep.com.cn/fem/EN/Y2023/V10/I4/695
Fig.1  Role of the general modeling and optimization technique in a brief EOS management flow.
Fig.2  Framework of the general modeling and optimization technique for EOS scheduling problems.
Fig.3  Generally described EOS operations per task in EOS scheduling problems.
Fig.4  Examples of EOS working modes with different combinations of imaging and downlink operations. (a) Timeline view of an EOS. (b) Timeline view of a tracking station.
Fig.5  Relationship among real-world problem data in EOS scheduling problems.
Fig.6  Discretization from a ten-second VTW into the five-second EOs.
Fig.7  Model encoding example for real-world EOS scheduling problems. (a) Instanced decision variable presentation. (b) Numerical decision variable presentation by a decision matrix.
Catalog Sub-catalog Explanation
Preprocessable constraints Visibility The VTWs caused by EOS-task locations
The VTWs caused by EOS-task frequential matches
The VTWs caused by the abilities of EOSs, tracking stations, and their payloads
The VTWs caused by task requirements
The VTWs caused by other factors (sun, clouds, and latitudes)
Non-preprocessable constraints Logicality An imaging or downlink operation can be executed once at most
An imaging and downlink operation must be paired per task
A downlink operation under certain EOS working modes must be executed within the VTW
Sequence Some imaging and downlink operations must be executed in ordered sequences
Transition Transition time is required between the executed operations per EOS
Transition time is required between the executed operations per tracking station
Transition time is required between the imaging and downlink operations per task
Memory The stored data in the EOS memory cannot exceed the limit
The stored data must be downloaded prior to memory-erasing
EOS protection Working frequency and time limits for EOS cameras per orbit and/or day
Working frequency and time limits for EOS antennas per orbit and/or day
Maneuver frequency and time limits for EOSs per orbit and/or day
Continuous maneuver frequency and time limits for EOSs per orbit
Tab.1  Elementary constraint catalog of EOS scheduling problems
Fig.8  Procedure of the model that judges the satellite scheduling solution as feasible or not and evaluates its objective value.
Fig.9  Operators to reproduce neighboring solutions. (a) Move operator. (b) Crossover operator.
Fig.10  Flow chart of the PC-MA.
Case EOS operations State-of-the-art Task number
Case 1 Imaging ALNS (Liu et al., 2017) 50–400
Case 2 Imaging BDP-ILS (Peng et al., 2019) 100–600
Case 3 Downlink Conflict-resolution heuristic (Luo et al., 2017) 297–322
Case 4 Imaging, downlink, and memory-erasing Seldom studied 56–1267
Tab.2  Four EOS scheduling cases to be studied
Subcase Rule AGA TLA PC-MA ALNS
50 270.0 270.0 270.0 270.0 269.0
100 443.0 506.2 556.5 568.8 543.0
150 575.0 661.5 767.0 781.9 716.0
200 584.0 711.2 813.6 853.0 705.0
250 753.0 843.3 951.1 1017.9 813.0
300 809.0 855.8 986.3 1061.3 749.0
350 752.0 858.1 967.4 1066.3 841.0
400 793.0 875.7 1001.4 1133.7 739.0
Outperform 1/8 1/8 1/8 8/8 0/8
Tab.3  Experimental results of Case 1
Subcase Rule AGA TLA PC-MA BDP-ILS
100 291.0 420.7 489.5 494.0 491.1
200 396.0 621.2 725.7 741.4 747.6
300 409.0 671.1 811.1 833.8 854.9
400 475.0 904.1 1009.1 1060.7 1053.2
500 497.0 1012.9 1081.8 1149.9 1153.7
600 589.0 921.4 1128.2 1195.6 1260.1
Outperform 0/6 0/6 0/6 2/6 4/6
Tab.4  Experimental results of Case 2
Subcase Rule AGA TLA PC-MA Conflict-resolution
Day 1 269.0 309.5 313.2 314.9 316.0
Day 2 262.0 292.6 296.1 298.6 299.0
Day 3 264.0 300.2 306.1 308.0 309.0
Day 4 265.0 306.6 312.9 315.2 316.0
Day 5 255.0 295.8 300.0 303.0 303.0
Day 6 239.0 287.7 291.0 294.0 294.0
Day 7 257.0 290.0 293.0 293.0 293.0
Outperform 0/7 0/7 1/7 3/7 7/7
Tab.5  Experimental results of Case 3
EOS Date Rule AGA TLA PC-MA
1 Apr. 12 110.0 112.3 113.0 113.0
1 Apr. 12, 13 185.0 189.2 189.8 190.0
2 Apr. 12 143.0 146.3 148.0 148.0
3 Apr. 12 55.0 55.0 55.0 55.0
4 Apr. 12 129.0 134.4 136.8 137.0
1, 2, 3, 4 Apr. 13 331.0 337.4 344.6 344.9
1, 2, 3, 4 Apr. 14 262.0 271.3 272.0 272.0
1, 2, 3, 4 Apr. 13, 14 593.0 603.0 614.2 616.7
1, 2, 3, 4 Apr. 16 515.0 533.8 560.4 571.6
1, 2, 3, 4 Apr. 17 598.0 634.5 667.3 681.0
1, 2, 3, 4 Apr. 16, 17 1113.0 1159.7 1231.5 1246.9
Outperform 1/11 1/11 4/11 11/11
Tab.6  Experimental results of Case 4 (only with VTWs and transition time constraints)
EOS Date Rule AGA TLA PC-MA
1 Apr. 12 35.0 69.0 77.9 79.4
1 Apr. 12, 13 67.0 95.6 99.8 108.4
2 Apr. 12 29.0 72.7 84.0 86.6
3 Apr. 12 30.0 47.8 51.3 53.3
4 Apr. 12 29.0 73.6 81.1 85.5
1, 2, 3, 4 Apr. 13 113.0 219.2 253.9 260.4
1, 2, 3, 4 Apr. 14 96.0 193.4 232.1 241.0
1, 2, 3, 4 Apr. 13, 14 182.0 405.0 446.2 491.8
1, 2, 3, 4 Apr. 16 234.0 251.7 283.6 296.2
1, 2, 3, 4 Apr. 17 239.0 275.9 308.5 331.0
1, 2, 3, 4 Apr. 16, 17 357.0 455.6 534.0 544.3
Outperform 0/11 0/11 0/11 11/11
Tab.7  Experimental results of Case 4 (with all constraints)
Fig.11  Mean parallel-algorithm grades per 20% optimization process in the PC-MA. (a) Subcase 400 in Case 1. (b) Subcase 600 in Case 2. (c) Subcase Day 1 in Case 3. (d) Subcase Apr. 16, 17 with all the constraints in Case 4.
Other satellite scheduling problem Satellite operation contained per task
Satellite range scheduling Downlink
Relay satellite scheduling Downlink and memory-erasing
Time synchronization scheduling of navigation satellites Downlink
Inter-link scheduling of navigation satellites Inter-link (divided in timeslots)
Tab.8  Ideas of modeling other satellite scheduling problems using the proposed technique
1 Air Force Office of Scientific Research (2003). Exploiting elementary landscapes for search (AFSCN scheduling problems)
2 X G Chu, Y N Chen, Y J Tan, (2017). An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 60( 9): 2077–2090
https://doi.org/10.1016/j.asr.2017.07.026
3 J F Cordeau, G Laporte, (2005). Maximizing the value of an earth observation satellite orbit. Journal of the Operational Research Society, 56( 8): 962–968
https://doi.org/10.1057/palgrave.jors.2601926
4 Y H Du, L Wang, L N Xing, J G Yan, M S Cai, (2021). Data-driven heuristic assisted memetic algorithm for efficient inter-satellite link scheduling in the BeiDou navigation satellite system. IEEE/CAA Journal of Automatica Sinica, 8( 11): 1800–1816
https://doi.org/10.1109/JAS.2021.1004174
5 Y H Du, T Wang, B Xin, L Wang, Y G Chen, L N Xing, (2020). A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Transactions on Evolutionary Computation, 24( 4): 679–693
https://doi.org/10.1109/TEVC.2019.2934148
6 Y H Du, L N Xing, Y G Chen, (2022). Satellite scheduling engine: The intelligent solver for future multi-satellite management. Frontiers of Engineering Management, 9( 4): 683–688
https://doi.org/10.1007/s42524-022-0222-4
7 L He, X L Liu, G Laporte, Y W Chen, Y G Chen, (2018). An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 100: 12–25
https://doi.org/10.1016/j.cor.2018.06.020
8 Y M He, L N Xing, Y W Chen, W Pedrycz, L Wang, G Wu, (2022). A generic Markov decision process model and reinforcement learning method for scheduling agile earth observation satellites. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52( 3): 1463–1474
https://doi.org/10.1109/TSMC.2020.3020732
9 J Jang, J Choi, H J Bae, I C Choi, (2013). Image collection planning for Korea Multi-Purpose SATellite-2. European Journal of Operational Research, 230( 1): 190–199
https://doi.org/10.1016/j.ejor.2013.04.009
10 M LemaîtreG VerfaillieF (2000) Jouhaud. How to manage the new generation of agile earth observation satellites. In: Proceedings of the 6th International SpaceOps Symposium. Toulouse: AIAA, 1–8
11 X L Liu, G Laporte, Y W Chen, R J He, (2017). An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 86: 41–53
https://doi.org/10.1016/j.cor.2017.04.006
12 K P Luo, H H Wang, Y J Li, Q Li, (2017). High-performance technique for satellite range scheduling. Computers & Operations Research, 85: 12–21
https://doi.org/10.1016/j.cor.2017.03.012
13 S H Mok, S Jo, H Bang, H Leeghim, (2019). Heuristic-based mission planning for an agile earth observation satellite. International Journal of Aeronautical and Space Sciences, 20( 3): 781–791
https://doi.org/10.1007/s42405-018-0105-4
14 P Moscato (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Con-Current Computation Program 158-79. Pasadena, CA: California Institute of Technology
15 S Nag, A S Li, J H Merrick, (2018). Scheduling algorithms for rapid imaging using agile Cubesat constellations. Advances in Space Research, 61( 3): 891–913
https://doi.org/10.1016/j.asr.2017.11.010
16 G S Peng, R Dewil, C Verbeeck, A Gunawan, L N Xing, P Vansteenwegen, (2019). Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times. Computers & Operations Research, 111: 84–98
https://doi.org/10.1016/j.cor.2019.05.030
17 G S Peng, G P Song, L N Xing, A Gunawan, P Vansteenwegen, (2020). An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 120: 104946
https://doi.org/10.1016/j.cor.2020.104946
18 C G Valicka, D Garcia, A Staid, J P Watson, G Hackebeil, S Rathinam, L Ntaimo, (2019). Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty. European Journal of Operational Research, 275( 2): 431–445
https://doi.org/10.1016/j.ejor.2018.11.043
19 J J Wang, E Demeulemeester, X J Hu, G H Wu, (2020). Expectation and SAA models and algorithms for scheduling of multiple earth observation satellites under the impact of clouds. IEEE Systems Journal, 14( 4): 5451–5462
https://doi.org/10.1109/JSYST.2019.2961236
20 G Wu, J Liu, M Ma, D S Qiu, (2013). A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 40( 7): 1884–1894
https://doi.org/10.1016/j.cor.2013.02.009
21 Y Y Xiao, S Y Zhang, P Yang, M You, J Y Huang, (2019). A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties. Reliability Engineering & System Safety, 188: 263–275
https://doi.org/10.1016/j.ress.2019.03.016
22 C F Yang, (2021). Innovation and development of BeiDou Navigation Satellite System (BDS) project management mode. Frontiers of Engineering Management, 8( 2): 312–320
https://doi.org/10.1007/s42524-021-0155-3
23 W M Zhu, X X Hu, W Xia, P Jin, (2019). A two-phase genetic annealing method for integrated earth observation satellite scheduling problems. Soft Computing, 23( 1): 181–196
https://doi.org/10.1007/s00500-017-2889-8
[1] Lebing WANG, Jian Gang JIN, Lijun SUN, Der-Horng LEE. Urban rail transit disruption management: Research progress and future directions[J]. Front. Eng, 2024, 11(1): 79-91.
[2] Yuting WANG, Yuyan HAN, Dunwei GONG, Huan LI. A review of intelligent optimization for group scheduling problems in cellular manufacturing[J]. Front. Eng, 2023, 10(3): 406-426.
[3] Zoltán A. VATTAI, Levente MÁLYUSZ. Negative weights in network time model[J]. Front. Eng, 2022, 9(2): 268-280.
[4] Loghman PIRI, Vahidreza GHEZAVATI, Ashkan HAFEZALKOTOB. Developing a new model for simultaneous scheduling of two grand projects based on game theory and solving the model with Benders decomposition[J]. Front. Eng, 2022, 9(1): 117-134.
[5] Atilla DAMCI, Gul POLAT, Firat Dogu AKIN, Harun TURKOGLU. Use of float consumption rate in resource leveling of construction projects[J]. Front. Eng, 2022, 9(1): 135-147.
[6] Fikri KUCUKSAYACIGIL, Gündüz ULUSOY. Hybrid genetic algorithm for bi-objective resource-constrained project scheduling[J]. Front. Eng, 2020, 7(3): 426-446.
[7] Shubin SI, Jiangbin ZHAO, Zhiqiang CAI, Hongyan DUI. Recent advances in system reliability optimization driven by importance measures[J]. Front. Eng, 2020, 7(3): 335-358.
[8] Fupei LI, Minglei YANG, Wenli DU, Xin DAI. Development and challenges of planning and scheduling for petroleum and petrochemical production[J]. Front. Eng, 2020, 7(3): 373-383.
[9] Sameh Al-SHIHABI, Mohammad AlDURGAM. Multi-objective optimization for the multi-mode finance-based project scheduling problem[J]. Front. Eng, 2020, 7(2): 223-237.
[10] Lei ZHOU, Zhe LIANG, Chun-An CHOU, Wanpracha Art CHAOVALITWONGSE. Airline planning and scheduling: Models and solution methodologies[J]. Front. Eng, 2020, 7(1): 1-26.
[11] Juan LIU, Fei QIAO, Yumin MA, Weichang KONG. Novel slack-based robust scheduling rule for a semiconductor manufacturing system with uncertain processing time[J]. Front. Eng, 2018, 5(4): 507-514.
[12] Lingxuan LIU, Zhongshun SHI, Leyuan SHI. Minimization of total energy consumption in an m-machine flow shop with an exponential time-dependent learning effect[J]. Front. Eng, 2018, 5(4): 487-498.
[13] Marcel JOLY, Darci ODLOAK, Mario Y. MIYAKE, Brenno C. MENEZES, Jeffrey D. KELLY. Refinery production scheduling toward Industry 4.0[J]. Front. Eng, 2018, 5(2): 202-213.
[14] Lynda M. BOURNE, Patrick WEAVER. The origins of schedule management: the concepts used in planning, allocating, visualizing and managing time in a project[J]. Front. Eng, 2018, 5(2): 150-166.
[15] Mario VANHOUCKE. Planning projects with scarce resources: Yesterday, today and tomorrow’s research challenges[J]. Front. Eng, 2018, 5(2): 133-149.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed