Acta Aeronautica et Astronautica Sinica ›› 2024, Vol. 45 ›› Issue (16): 329706-329706.doi: 10.7527/S1000-6893.2023.29706
• Electronics and Electrical Engineering and Control • Previous Articles
Hengwei LI1, Qizhang LUO1, Yi GU1, Caizhi FAN2, Guohua WU1()
Received:
2023-10-12
Revised:
2023-10-28
Accepted:
2023-12-22
Online:
2024-01-15
Published:
2024-01-11
Contact:
Guohua WU
E-mail:guohuawu@csu.edu.cn
Supported by:
CLC Number:
Hengwei LI, Qizhang LUO, Yi GU, Caizhi FAN, Guohua WU. Multi⁃objective dynamic scheduling optimization method for relay satellites based on rolling horizon strategy[J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(16): 329706-329706.
Table 2
Experimental scenarios and parameters
实验编号 | 常规任务个数 | 动态任务个数 | 中继卫星个数 | 正态分布 均值 | 标准差 |
---|---|---|---|---|---|
C1 | 100 | 25 | 3 | 600 | 300 |
C2 | 200 | 25 | 3 | 600 | 300 |
C3 | 300 | 25 | 3 | 600 | 300 |
C4 | 400 | 25 | 3 | 600 | 300 |
C5 | 500 | 25 | 3 | 600 | 300 |
C6 | 300 | 15 | 3 | 600 | 300 |
C7 | 300 | 20 | 3 | 600 | 300 |
C8 | 300 | 25 | 3 | 600 | 300 |
C9 | 300 | 30 | 3 | 600 | 300 |
C10 | 300 | 35 | 3 | 600 | 300 |
C11 | 300 | 25 | 2 | 600 | 300 |
C12 | 300 | 25 | 3 | 600 | 300 |
C13 | 300 | 25 | 4 | 600 | 300 |
C14 | 300 | 25 | 5 | 600 | 300 |
C15 | 300 | 25 | 6 | 600 | 300 |
C16 | 300 | 25 | 3 | 500 | 300 |
C17 | 300 | 25 | 3 | 550 | 300 |
C18 | 300 | 25 | 3 | 600 | 300 |
C19 | 300 | 25 | 3 | 650 | 300 |
C20 | 300 | 25 | 3 | 700 | 300 |
Table 4
Algorithm performance with different parameters
实验编号 | AMODSA | MDSA‐NSGA‐II | NSGA-Ⅱ | MODJA | ||||
---|---|---|---|---|---|---|---|---|
平均HV值 | 标准差 | 平均HV值 | 标准差 | 平均HV值 | 标准差 | 平均HV值 | 标准差 | |
C1 | 0.418 | 0.033 | 0.387 | 0.064 | 0.376 | 0.059 | 0.402 | 0.051 |
C2 | 0.642 | 0.047 | 0.605 | 0.087 | 0.589 | 0.054 | 0.611 | 0.066 |
C3 | 0.805 | 0.054 | 0.770 | 0.034 | 0.755 | 0.071 | 0.793 | 0.047 |
C4 | 0.869 | 0.059 | 0.827 | 0.055 | 0.794 | 0.089 | 0.832 | 0.105 |
C5 | 0.925 | 0.075 | 0.861 | 0.132 | 0.802 | 0.086 | 0.901 | 0.133 |
C6 | 0.728 | 0.081 | 0.706 | 0.066 | 0.687 | 0.113 | 0.711 | 0.057 |
C7 | 0.753 | 0.103 | 0.722 | 0.122 | 0.692 | 0.132 | 0.739 | 0.049 |
C8 | 0.805 | 0.054 | 0.770 | 0.034 | 0.755 | 0.071 | 0.793 | 0.047 |
C9 | 0.811 | 0.091 | 0.774 | 0.098 | 0.758 | 0.123 | 0.796 | 0.093 |
C10 | 0.816 | 0.122 | 0.780 | 0.132 | 0.764 | 0.141 | 0.799 | 0.037 |
C11 | 0.480 | 0.043 | 0.442 | 0.119 | 0.423 | 0.061 | 0.463 | 0.083 |
C12 | 0.805 | 0.054 | 0.770 | 0.034 | 0.755 | 0.071 | 0.793 | 0.047 |
C13 | 0.875 | 0.086 | 0.830 | 0.111 | 0.811 | 0.119 | 0.860 | 0.081 |
C14 | 0.891 | 0.098 | 0.857 | 0.129 | 0.833 | 0.087 | 0.867 | 0.053 |
C15 | 0.904 | 0.107 | 0.884 | 0.068 | 0.872 | 0.058 | 0.891 | 0.141 |
C16 | 0.867 | 0.116 | 0.828 | 0.109 | 0.806 | 0.063 | 0.845 | 0.074 |
C17 | 0.823 | 0.062 | 0.801 | 0.051 | 0.778 | 0.116 | 0.810 | 0.077 |
C18 | 0.805 | 0.054 | 0.770 | 0.034 | 0.755 | 0.071 | 0.793 | 0.047 |
C19 | 0.786 | 0.071 | 0.736 | 0.053 | 0.711 | 0.110 | 0.752 | 0.089 |
C20 | 0.769 | 0.057 | 0.742 | 0.097 | 0.728 | 0.085 | 0.747 | 0.067 |
Table 5
Coverage results of different algorithms in different experimental scenarios
实验编号 | 覆盖率 | |||||
---|---|---|---|---|---|---|
C(AMODSA, MDSA‐NSGA‐II) | C(MDSA‐NSGA‐Ⅱ, AMODSA) | C(AMODSA, NSGA-Ⅱ) | C(NSGA-Ⅱ, AMODSA,) | C(AMODSA, MODJA) | C(MODJA, AMODSA) | |
C1 | 1.000 0 | 0 | 1.000 0 | 0 | 0.863 3 | 0.237 2 |
C2 | 1.000 0 | 0 | 1.000 0 | 0 | 0.925 7 | 0.165 5 |
C3 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C4 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C5 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C6 | 0.833 3 | 0.201 9 | 0.904 7 | 0.064 5 | 0.782 4 | 0.273 3 |
C7 | 1.000 0 | 0 | 1.000 0 | 0 | 0.972 2 | 0.054 1 |
C8 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C9 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C10 | 0.921 8 | 0.103 3 | 1.000 0 | 0 | 0.843 7 | 0.210 7 |
C11 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C12 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C13 | 1.000 0 | 0 | 1.000 0 | 0 | 0.988 7 | 0.060 1 |
C14 | 0.927 8 | 0.093 5 | 1.000 0 | 0 | 0.897 7 | 0.154 9 |
C15 | 0.841 4 | 0.178 5 | 0.906 4 | 0.163 1 | 0.763 9 | 0.251 1 |
C16 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C17 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C18 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C19 | 1.000 0 | 0 | 1.000 0 | 0 | 1.000 0 | 0 |
C20 | 0.928 6 | 0.157 8 | 1.000 0 | 0 | 0.973 6 | 0.082 3 |
Table 6
Algorithm computational time in different experimental scenarios
实验编号 | 消耗时间/s | |||
---|---|---|---|---|
AMODSA | MDSA‐NSGA‐Ⅱ | NSGA-Ⅱ | MODJA | |
C1 | 334.2 | 509.7 | 421.2 | 476.2 |
C2 | 406.3 | 586.0 | 493.2 | 521.0 |
C3 | 529.7 | 733.5 | 649.3 | 687.1 |
C4 | 578.3 | 798.1 | 672.8 | 712.7 |
C5 | 612.5 | 803.9 | 678.6 | 764.3 |
C6 | 501.7 | 687.2 | 595.0 | 621.7 |
C7 | 507.6 | 699.3 | 622.8 | 643.8 |
C8 | 529.7 | 733.5 | 649.3 | 687.1 |
C9 | 553.4 | 785.6 | 674.2 | 706.4 |
C10 | 576.8 | 799.8 | 689.3 | 744.8 |
C11 | 465.9 | 633.0 | 574.5 | 593.5 |
C12 | 529.7 | 733.5 | 649.3 | 687.1 |
C13 | 536.5 | 754.7 | 662.7 | 706.9 |
C14 | 564.0 | 768.1 | 699.4 | 727.8 |
C15 | 568.2 | 788.2 | 701.4 | 736.1 |
C16 | 447.3 | 598.3 | 523.9 | 557.3 |
C17 | 498.8 | 657.9 | 587.0 | 623.7 |
C18 | 529.7 | 733.5 | 649.3 | 687.1 |
C19 | 587.3 | 811.3 | 725.3 | 753.2 |
C20 | 601.1 | 814.7 | 733.7 | 774.9 |
1 | BRANDEL D L, WATSON W A, WEINBERG A. NASA’s advanced tracking and data relay satellite system for the years 2000 and beyond[J]. Proceedings of the IEEE, 1990, 78(7): 1141-1151. |
2 | HORAN S. Nontracking antenna performance for inertially controlled spacecraft using TDRSS[J]. IEEE Transactions on Aerospace and Electronic Systems, 2003, 39(4): 1263-1269. |
3 | WANG J J, JIANG C X, ZHANG H J, et al. Aggressive congestion control mechanism for space systems[J]. IEEE Aerospace and Electronic Systems Magazine, 2016, 31(3): 28-33. |
4 | WANG X Y, ZHAO S H, LI Y J, et al. An enhanced MAC protocol based on the IEEE 802.11 for data relay satellite systems[J]. International Journal of Satellite Communications and Networking, 2020, 38(3): 272-283. |
5 | 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. |
6 | PECORELLA T, RONGA L S, CHITI F, et al. Emergency satellite communications: research and standardization activities[J]. IEEE Communications Magazine, 2015, 53(5): 170-177. |
7 | ZHAI X J, NIU X N, TANG H, et al. Robust satellite scheduling approach for dynamic emergency tasks[J]. Mathematical Problems in Engineering, 2015, 2015: 482923. |
8 | 顾中舜. 中继卫星动态调度问题建模及优化技术研究[D]. 长沙: 国防科学技术大学, 2008. |
GU Z S. Research on the relay satellite dynamic scheduling problem modeling and optimizational technology[D].Changsha: National University of Defense Technology, 2008 (in Chinese). | |
9 | ROJANASOONTHON S, BARD J F, REDDY S D. Algorithms for parallel machine scheduling: A case study of the tracking and data relay satellite system[J]. Journal of the Operational Research Society, 2003, 54(8): 806-821. |
10 | ROJANASOONTHON S, BARD J. A GRASP for parallel machine scheduling with time windows[J]. INFORMS Journal on Computing, 2005, 17(1): 32-51. |
11 | ZHUANG S F, YIN Z D, WU Z L, et al. The relay satellite scheduling based on artificial bee colony algorithm[C]∥ 2014 International Symposium on Wireless Personal Multimedia Communications (WPMC). Piscataway: IEEE Press, 2014: 635-640. |
12 | WANG L, JIANG C X, KUANG L L, et al. Mission scheduling in space network with antenna dynamic setup times[J]. IEEE Transactions on Aerospace and Electronic Systems, 2019, 55(1): 31-45. |
13 | CHEN X J, LI X M, WANG X W, et al. Task scheduling method for data relay satellite network considering breakpoint transmission[J]. IEEE Transactions on Vehicular Technology, 2021, 70(1): 844-857. |
14 | 郭超, 熊伟, 郝利云. 基于双层优先级的中继卫星系统任务调度算法[J]. 计算机应用研究, 2018, 35(5): 1506-1510. |
GUO C, XIONG W, HAO L Y. Relay satellite system task scheduling algorithm based on double-layer priority[J]. Application Research of Computers, 2018, 35(5): 1506-1510 (in Chinese). | |
15 | WU G H, LUO Q Z, ZHU Y Q, et al. Flexible task scheduling in data relay satellite networks[J]. IEEE Transactions on Aerospace and Electronic Systems, 2022, 58(2): 1055-1068. |
16 | LI J X, WU G H, LIAO T J, et al. Task scheduling under a novel framework for data relay satellite network via deep reinforcement learning[J]. IEEE Transactions on Vehicular Technology, 2023, 72(5): 6654-6668. |
17 | DAI C Q, LI C, FU S, et al. Dynamic scheduling for emergency tasks in space data relay network[J]. IEEE Transactions on Vehicular Technology, 2021, 70(1): 795-807. |
18 | DENG B Y, JIANG C X, KUANG L L, et al. Two-phase task scheduling in data relay satellite systems[J]. IEEE Transactions on Vehicular Technology, 2018, 67(2): 1782-1793. |
19 | HE L J, LI J D, SHENG M, et al. Dynamic scheduling of hybrid tasks with time windows in data relay satellite networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5): 4989-5004. |
20 | LIN X H, WANG L H, XU H, et al. Event-trigger rolling horizon optimization for congestion management considering peer-to-peer energy trading among microgrids[J]. International Journal of Electrical Power & Energy Systems, 2023, 147(5): 108838. |
21 | JIA Y J, WANG C J, WANG L M. A rolling horizon procedure for dynamic pickup and delivery problem with time windows[C]∥ 2009 IEEE International Conference on Automation and Logistics. Piscataway: IEEE Press, 2009: 2087-2091. |
22 | QIU D S, HE C, LIU J, et al. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy[J]. The Scientific World Journal, 2013(3): 304047. |
23 | 庄树峰. 跟踪与数据中继卫星系统资源调度技术研究[D]. 哈尔滨: 哈尔滨工业大学, 2017. |
ZHUANG S F. Research on resource scheduling technology of tracking and data relay satellite system[D].Harbin: Harbin Institute of Technology, 2017 (in Chinese). | |
24 | 陈英武, 方炎申, 顾中舜. 中继卫星单址链路调度模型与算法研究[J]. 中国空间科学技术, 2007, 27(2): 52-58. |
CHEN Y W, FANG Y S, GU Z S. Algorithms for the single access link scheduling model of tracking and data relay satellite system[J]. Chinese Space Science and Technology, 2007, 27(2): 52-58 (in Chinese). | |
25 | DU J, JIANG C X, GUO Q, et al. Cooperative earth observation through complex space information networks[J]. IEEE Wireless Communications, 2016, 23(2): 136-144. |
26 | CHAND S, HSU V N, Forecast SETHI S., solution, and rolling horizons in operations management problems : A classified bibliography[J]. Manufacturing & Service Operations Management, 2002, 4(1): 25-43. |
27 | DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]∥ Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000: 849-858. |
28 | YU W W, ZHANG L, GE N. An adaptive multiobjective evolutionary algorithm for dynamic multiobjective flexible scheduling problem[J]. International Journal of Intelligent Systems, 2022, 37(12): 12335-12366. |
29 | CALDEIRA R H, GNANAVELBABU A. A Pareto based discrete Jaya algorithm for multi-objective flexible job shop scheduling problem[J]. Expert Systems with Applications, 2021, 170: 114567. |
30 | 李夏苗, 陈新江, 伍国华, 等. 考虑断点续传的中继卫星调度模型及启发式算法[J]. 航空学报, 2019, 40(11): 323233. |
LI X M, CHEN X J, WU G H, et al. Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40(11): 323233 (in Chinese). | |
31 | 王志淋, 李新明. 跟踪与数据中继卫星系统资源调度优化问题[J]. 中国空间科学技术, 2015, 35(1): 36-42. |
WANG Z L, LI X M. Resources scheduling optimization problem of the TDRSS[J]. Chinese Space Science and Technology, 2015, 35(1): 36-42 (in Chinese). | |
32 | 孙刚, 彭双, 陈浩, 等. 面向测控数传资源一体化场景的卫星地面站资源多目标优化方法[J]. 航空学报, 2022, 43(9): 326114. |
SUN G, PENG S, CHEN H, et al. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources[J]. Acta Aeronautica et Astronautica Sinica, 2022, 43(9): 326114 (in Chinese). | |
33 | 孙刚, 陈浩, 彭双, 等. 一种基于偏好MOEA的卫星地面站资源多目标优化算法[J]. 航空学报, 2021, 42(4): 524475. |
SUN G, CHEN H, PENG S, et al. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(4): 524475 (in Chinese). | |
34 | 龙运军, 李恒伟, 尹谦, 等. 基于多目标优化的中继卫星重调度方法[J]. 无线电工程, 2022, 52(7): 1180-1189. |
LONG Y J, LI H W, YIN Q, et al. Relay satellite rescheduling method based on multi-objective optimization[J]. Radio Engineering, 2022, 52(7): 1180-1189 (in Chinese). | |
35 | LIU R Z, SHENG M, XU C, et al. Antenna slewing time aware mission scheduling in space networks[J]. IEEE Communications Letters, 2017, 21(3): 516-519. |
36 | 张彦, 孙占军, 李剑. 中继卫星动态调度问题研究[J]. 系统仿真学报, 2011, 23(7): 1464-1468. |
ZHANG Y, SUN Z J, LI J. Study of TDRS dynamic scheduling problem[J]. Journal of System Simulation, 2011, 23(7): 1464-1468 (in Chinese). | |
37 | 伍国华, 王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法[J]. 航空学报, 2023, 44(12): 327759. |
WU G H, WANG T Y. Large-scale constellation TT & C resource scheduling algorithm based on adaptive simulated annealing[J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(12): 327759 (in Chinese). | |
38 | SHANG K, ISHIBUCHI H. A new hypervolume-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(5): 839-852. |
39 | ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195. |
[1] | Qian YANG, Haoran ZHENG, Xianda CHENG, Wei DONG. Optimization design method for hot air anti⁃icing system based on bleed air control [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729285-729285. |
[2] | Jiezhong DONG, Wuli CHU, Haoguang ZHANG, Bo LUO, Song YAN. Flow control mechanism of diffuser cascade with wavy leading⁃edge based on causal network analysis [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(19): 128336-128336. |
[3] | Chao LIANG, Li YANG, Chengsheng PAN, Yaowen QI. Multi-QoS constraints routing algorithm based on satellite network dynamic resource graph [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(1): 326422-326422. |
[4] | ZOU Ziyuan, CHEN Qifeng. Decision tree-based target assignment for confrontation of multiple space vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(S1): 726910-726910. |
[5] | SUN Gang, PENG Shuang, CHEN Hao, WU Jiangjiang, LI Jun. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326114-326114. |
[6] | ZHENG Shuai, WANG Zihan, ZHAO Haoran, YANG Pengtao, HONG Jun. Layout optimization method of aircraft fuel gauging sensor based on differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 125809-125809. |
[7] | JING Tao, TIAN Xitian. Multi-objective optimization method for aircraft tolerance allocation based on Monte Carlo-adaptive differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 425278-425278. |
[8] | LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792. |
[9] | ZHANG Junfeng, YOU Lubao, YANG Chunwei, HU Rong. Arrival sequencing and scheduling based on multi-objective Imperialist competitive algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 324439-324439. |
[10] | SUN Gang, CHEN Hao, PENG Shuang, DU Chun, LI Jun. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524475-524475. |
[11] | HE Cheng, MA Dongli, JIA Yuhong, YANG Muqing, CHEN Gang. Multi-objective optimization design for joined-wing SensorCraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(12): 224761-224761. |
[12] | LIU Jixin, JIANG Hao, DONG Xinfang, LAN Sijie, WANG Haozhe. Dynamic collaborative sequencing method for arrival flights based on air traffic density [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(7): 323717-323717. |
[13] | SUN Junfeng, ZHOU Zhu, HUANG Yong, PANG Yufei, LU Fengshun, XU Yong. Digital integrated platform for universal aircraft aerodynamic design optimization: DIPasda [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 623348-623348. |
[14] | LI Runze, ZHANG Yufei, CHEN Haixin. Strategies and methods for multi-objective aerodynamic optimization design for supercritical wings [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 623409-623409. |
[15] | PAN Chengsheng, XING Guixuan, QI Yaowen, YANG Li. Topological generation and optimization method in multi-state space information network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(4): 323546-323546. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||
Address: No.238, Baiyan Buiding, Beisihuan Zhonglu Road, Haidian District, Beijing, China
Postal code : 100083
E-mail:hkxb@buaa.edu.cn
Total visits: 6658907 Today visits: 1341All copyright © editorial office of Chinese Journal of Aeronautics
All copyright © editorial office of Chinese Journal of Aeronautics
Total visits: 6658907 Today visits: 1341