2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

航天器任务调度模型、算法与通用求解技术综述

杜永浩 邢立宁 姚锋 陈盈果

杜永浩, 邢立宁, 姚锋, 陈盈果. 航天器任务调度模型、算法与通用求解技术综述. 自动化学报, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
引用本文: 杜永浩, 邢立宁, 姚锋, 陈盈果. 航天器任务调度模型、算法与通用求解技术综述. 自动化学报, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
Du Yong-Hao, Xing Li-Ning, Yao Feng, Chen Ying-Guo. survey on models, algorithms and general techniques for spacecraft mission scheduling. Acta Automatica Sinica, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
Citation: Du Yong-Hao, Xing Li-Ning, Yao Feng, Chen Ying-Guo. survey on models, algorithms and general techniques for spacecraft mission scheduling. Acta Automatica Sinica, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656

航天器任务调度模型、算法与通用求解技术综述


DOI: 10.16383/j.aas.c190656
详细信息
    作者简介:

    国防科技大学系统工程学院博士研究生. 2017年获国防科技大学硕士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: duyonghao15@163.com

    国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009 年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. 本文通讯作者. E-mail: xinglining@gmail.com

    国防科技大学系统工程学院研究员. 2013年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: yaofeng@nudt.edu.cn

    国防科技大学系统工程学院副教授. 2014年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: argguo@163.com

    通讯作者: 国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009 年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. 本文通讯作者. E-mail: xinglining@gmail.com
  • 基金项目:  国家自然科学基金(61773120, 61873328), 国家杰出青年科学基金(61525304), 高等学校全国优秀博士学位论文作者专项资金(2014-92), 国家建设高水平大学公派研究生项目(201903170181), 湖南省研究生科研创新项目(CX2018B022)资助

Survey on Models, Algorithms and General Techniques for Spacecraft Mission Scheduling

More Information
    Corresponding author: XING Li-Ning Professor at the College of Systems Engineering, National University of Defense Technology. He was awarded with the National Excellent Ph. D. Dissertation of China and the New Century Excellent Researcher of Ministry of Education. He is also supported by the Natural Science Funds for Distinguished Young Scholar of Hunan Province. He received his Ph. D. degree from National University of Defense Technology in 2009. His research interest covers intelligent optimization theory, method, and application. Corresponding author of this paper
  • Fund Project:  Supported by National Natural Science Foundation of China (61773120, 61873328), National Science Fund for Distinguished Young Scholars (61525304), National Excellent Doctoral Dissertation Foundation of China (2014-92), State Scholarship Fund of the China Scholarship Council (201903170181), and Hunan Postgraduate Research Innovation Project (CX2018B022)
  • 摘要: 针对航天器任务调度大规模、复杂化的新常态和灵活组网、快速响应的新要求, 综述了航天器任务调度模型、算法与通用求解技术的发展现状. 首先, 基于遥感卫星、通讯中继卫星、导航卫星和航天测控等航天器任务, 从任务排序模型和时间窗口分配模型两个角度出发, 揭示了不同航天器任务调度模型的决策形式和共性特征, 阐明提升模型兼容性、适用性的必要性. 其次, 基于启发式算法、精确求解算法和元启发式算法, 探讨了航天器任务调度算法的适用模型与编码特色, 指明“算法-模型”解耦、算法深度融合的重要性. 在此基础上, 介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等航天器任务调度通用求解技术的模型、算法与主要功能, 说明我国自主研发通用求解技术的必要性和新的应用思路. 最后, 指出了开发航天器任务调度统一化建模语言、打造算法库与测试集等未来航天器任务调度研究的新方向.
  • 图  1  遥感卫星任务排序模型示例. (a) 双星VRP模型. (b) 单星图论模型. (c) 基于最早开始原则的双星JSP模型

    Fig.  1  Illustrations of mission-sequencing models for remote sensing satellites. (a) A VRP model for two satellites. (b) A graph-based model for single satellite. (c) A JSP model for two satellites based on the earliest-beginning principle

    图  2  遥感卫星VTW分配模型示例. (a) 非敏捷卫星VTW分配模型. (b) 敏捷卫星VTW分配模型

    Fig.  2  Illustrations of VTW-allocation models for remote sensing satellites. (a) A model for non-agile satellites. (b) A model for agile satellites

    图  3  敏捷遥感卫星任务离散VTW分配模型示例

    Fig.  3  An illustration of the discrete VTW-allocation model for agile remote sensing satellites

    图  4  通讯中继卫星任务调度问题与遥感卫星任务调度问题的类比. (a) 基于卫星上行链路的通讯中继任务. (b) 基于卫星下行链路的通讯中继任务

    Fig.  4  A comparison between the mission scheduling of communication relay satellites and remote sensing satellites. (a) Uplink-based missions. (b) Downlink-based missions

    图  5  航天器测控任务调度示例. (a) 地基高轨、低轨航天器测控任务. (b) 天基高轨、低轨航天器测控任务

    Fig.  5  Illustrations of spacecraft tracking mission scheduling. (a) Land-based high-orbit and low-orbit tracking missions. (b) Space-based high-orbit and low-orbit tracking missions

    图  6  航天器任务调度模型主要参数关系的一种类图表示(以遥感卫星为例)

    Fig.  6  A class diagram of the relationships among the parameters in spacecraft mission scheduling (exampled by remote sensing satellites)

    图  7  遗传算法求解航天器任务调度问题编码示例. (a) 任务排序模型的编码形式. (b) VTW分配模型的编码形式

    Fig.  7  Illustrations of the GA encoding for spacecraft mission scheduling. (a) The encoding of a mission-sequencing model. (b) The encoding of a VTW-allocation model

    图  8  操作界面示例. (a) 场景(目标与资源)建模界面. (b) 资源属性设置界面

    Fig.  8  A view of the STK/Scheduler. (a) The scenario (targets and resources) modeling. (b) The resource parameter setting

    表  1  航天器任务调度模型研究现状总结

    Table  1  A summary of the studied models for spacecraft mission scheduling

    模型类型模型子类编码过程解码过程模型优缺点常见约束极少考虑的业务约束
    面向资源的任务排序模型VRP模型决策变量表示资源执行任务的顺序规则与约束决定开始时间, 解码后为可行解1. 表示了任务顺序, 便于检查任务顺序和转换时间约束
    2. 在“顺序回放”工作机制下同时决策成像与数传序列
    3. 不便于描述长VTW的任务调度问题与复杂约束
    4. “最优序列”不一定等于“最优结果”, 约束越复杂, 解码过程越可能丢失优质解, 解码的时间成本也越高
    1. 任务执行唯一性约束
    2. 任务可见性约束(即时、空、频域VTW)
    3. 任务顺序约束(如条带拼接、立体成像、顺序回放等)
    4. 任务工作模式约束(如遥感卫星记录、回放、实传模式与录放比约束)
    5. 资源能力约束(如卫星电池、固存容量、任务次数; 测控与数传站负载、工作频率、时长约束等)
    6. 资源转换时间约束
    7. 资源可抢占性与非抢占性约束(如测控任务相控阵等待期可执行其他任务)
    1. 非线性、函数化、过程依赖的资源能力、转换时间约束(如遥感卫星单轨成像时限与该轨侧摆次数、最小摆角、是否实传等相关)
    2. 区分连续、非连续任务的资源能力、转换时间约束(如“高景一号”单轨连续成像次数、时间限制)
    3. 区分阳照条件的资源能力、转换时间约束(如地影区中继卫星工作时限)
    4. 区分待机、工作等的资源能力、转换时间约束(如载荷开关机、执行任务时限)
    5. 单载荷资源模式切换约束(如“北斗”地面站时间同步与数据传输模式的切换)
    6. 多载荷资源模式切换约束(如“资源一号”可见光与高光谱模式的切换)
    7. 遥感卫星基于“整块擦除”的固存管理约束
    图论模型
    JSP模型
    优先级排序模型通过决策变量表示任务分配资源的顺序
    面向任务的VTW分配模型基于规则的分配模型通过0-1变量表示任务的VTW基于规则与约束决定开始时间, 解码后为可行解1. 直接表达了任务VTW和开始时间, 反映了任务顺序
    2. 不限于“顺序回放”, 可分别调度成像与数传序列
    3. 能够描述长VTW的任务调度问题与复杂约束
    4. 基于规则的分配模型解空间较小, 但也存在解码过程
    5. 多重决策和离散VTW分配模型更加完备, 提升了解的多样性, 但解空间较大
    多重决策的分配模型通过0-1变量和整数变量分别表示VTW与开始时间不检查约束, 解码后可能为不可行解
    离散化VTW分配模型通过0-1变量直接表示离散VTW及开始时间
    下载: 导出CSV

    表  2  航天器任务调度研究中常用算法总结

    Table  2  A summary of commonly used algorithms for spacecraft mission scheduling

    算法类型算法子类常用编码模型算法优点算法不足
    启发式算法优先级排序算法任务排序模型1. 结构简单、运算速度快
    2. 符合人的主观认识, 有经验支撑
    3. 有助于缩减问题解空间, 在与其他算法组合使用过程中提升求解效率
    1. 与问题特征和调度模型紧耦合, 通用化程度不高
    2. 求解效果欠佳, 常用于辅助决策, 很少直接用于调度方案的生成
    冲突消解算法以任务排序模型为主
    任务分配算法以VTW分配模型为主
    精确算法分支定界算法任务排序或VTW分配模型1. 可以求得最优解, 在不确定性条件下也能保证解的最优性
    2. 算法思想对其他算法有指导意义, 与其他算法有良好的组合应用前景
    1. 只适用于小规模、简单约束问题, 求解大规模、复杂约束问题能力有限
    2. 通常需要较大程度的问题简化
    动态规划算法
    元启发式算法演化算法遗传算法任务排序或VTW分配模型1. 具有隐并行性和多样的解表示能力
    2. 具有出色的全局寻优能力
    3. 与其他算法混合的兼容性好
    4. 任务排序模型的编码形式简洁、操作简单
    1. 局部搜索能力有限
    2. 任务排序模型的编码方式可能丢失优质解
    3. VTW分配模型的编码方式复杂且冗长, 可能影响优化效率
    蚁群算法以任务排序模型为主
    粒子群算法以VTW分配模型为主
    局部搜索禁忌搜索算法任务排序或VTW分配模型1. 原理简单、易于实现、适用性好
    2. 具有出色的局部搜索能力
    3. 具有一定的局部最优逃逸能力
    1. 全局搜索能力有限, 易陷入局部最优
    2. 依赖于邻域结构的设计
    模拟退火算法以VTW分配模型为主
    其他算法模因算法任务排序或VTW分配模型对局部搜索和演化算法取长补短依赖于框架设计, 可能降低迭代效率
    机器学习决策算法以任务排序模型为主简单、快速并且自适应、自学习“来一个决策一个”, 缺乏全局优化性
    下载: 导出CSV

    表  3  用于航天任务调度的通用求解器总结

    Table  3  A summary of the general techniques for spacecraft mission scheduling

    通用求解器常用调度模型求解算法求解器优点求解器不足
    CPLEX线性规划模型表示的任务排序模型或VTW分配模型分支定界算法等精确求解算法1. 语言简洁, 兼容性好
    2. 内置算法丰富, 降低算法设计难度, 同时开放了算法设计与改进接口
    3. 可以求得最优解, 在不确定性条件下也能保证解的最优性
    4. 用户基础大, 版本持续更新
    1. 很难描述非线性约束或收益, 复杂约束线性化难度大
    2. 很难求解大规模任务调度问题
    3. 算法改进对线性规划理论基础要求高
    4. 缺乏航天领域特色
    STK/Scheduler任务排序模型任务排序算法, 冲突消解算法 1. 与STK兼容, 建模简单
    2. 语言简洁, 兼容性好
    3. STK/Scheduler Online具有远程服务功能
    1. 封装程度较高, 难以描述复杂约束, 二次开发难度大
    2. 缺乏动态调整功能
    3. 算法优化能力有限, 已不再更新
    VTW分配模型 任务分配算法, 冲突消解算法
    Europa2通过标记、事务、对象、类、时间线、规划解描述一个规划模型约束传播等约束规划算法1. 面向状态变量和动作序列, 求解过程直观
    2. 约束传播算法有助于动态调度机制的设计
    1. 缺乏收益函数和调度优化机制
    2. 只适用于小规模(单星单轨)任务调度, 已不再更新
    “高景一号”任务调度分系统任务排序模型基于最早开始原则的任务排序算法1. 模型与算法简洁
    2. 可以考虑全部复杂约束
    1. 调度质量有待提高
    2. 动态调整以人工为主, 结果无法实时反馈
    下载: 导出CSV
  • [1] 姜维, 郝会成, 李一军. 对地观测卫星任务规划问题研究述评. 系统工程与电子技术, 2013, 35(9): 1878−1885 doi:  10.3969/j.issn.1001-506X.2013.09.13

    Jiang Wei, Hao Hui-Cheng, Li Yi-Jun. Review of task scheduling research for the Earth observing satellites. Systems Engineering and Electronics, 2013, 35(9): 1878−1885 doi:  10.3969/j.issn.1001-506X.2013.09.13
    [2] 谢平, 杜永浩, 姚锋, 谭跃进. 敏捷成像卫星自主调度技术综述. 宇航学报, 2019, 40(2): 127−138

    Xie Ping, Du Yong-Hao, Yao Feng, Tan Yue-Jin. Literature review for autonomous scheduling technology of agile earth observation satellites. Journal of Astronautics, 2019, 40(2): 127−138
    [3] 向尚, 陈盈果, 李国梁, 邢立宁. 卫星自主与协同任务调度规划综述. 自动化学报, 2019, 45(2): 252−264

    Xiang Shang, Chen Ying-Guo, Li Guo-Liang, Xing Li-Ning. Review on satellite autonomous and collaborative task scheduling planning. Acta Automatica Sinica, 2019, 45(2): 252−264
    [4] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222−241

    Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Intelligent scheduling technologies for unmanned flying crafts cluster: a literature review. Acta Automatica Sinica, 2020, 46(2): 222−241
    [5] Wolfe W J, Sorensen 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
    [6] Cordeau J F, Laporte G. Maximizing the value of an Earth observation satellite orbit. Journal of the Operational Research Society, 2005, 56(8): 962−968 doi:  10.1057/palgrave.jors.2601926
    [7] Cordeau J F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 2001, 52(8): 928−936
    [8] Bianchessi N, Cordeau J F, Descrosiers J, Laporte G, Raymond V. 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 doi:  10.1016/j.ejor.2005.12.026
    [9] 李菊芳, 谭跃进. 卫星观测联合调度问题的VRP与JSP模型. 系统工程, 2006, 24(6): 111−115 doi:  10.3969/j.issn.1001-4098.2006.06.022

    Li Ju-Fang, Tan Yue-Jin. VRP and JSP models of coordinate scheduling problem for observing satellites. Systems Engineering, 2006, 24(6): 111−115 doi:  10.3969/j.issn.1001-4098.2006.06.022
    [10] 郭玉华, 李军, 赵珂, 王钧, 景宁. 多星联合任务规划中的启发式求解方法研究. 宇航学报, 2009, 30(2): 652−658 doi:  10.3873/j.issn.1000-1328.2009.02.043

    Guo Yu-Hua, Li Jun, Zhao Ke, Wang Jun, Jing Ning. A heuristic method for earth observing satellites united imaging scheduling. Journal of Astronautics, 2009, 30(2): 652−658 doi:  10.3873/j.issn.1000-1328.2009.02.043
    [11] 蔡德荣. 基于蚁群算法的多星联合成像任务规划问题研究[硕士学位论文], 电子科技大学, 中国, 2012

    Cai De-Rong. Research-based the "Ant Colony" Algorithm Multi-Satellite Mission Planning Joint Imaging Problems [Master dissertation], University of Electronic Science and Technology of China, China, 2012
    [12] 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
    [13] Bianchessi N, Righini G. Planning and scheduling algorithms for COSMO-SkyMed constellation. Aerospace Science and Technology, 2008, 12(7): 535−544 doi:  10.1016/j.ast.2008.01.001
    [14] 陈浩, 李军, 景宁, 刘湘辉, 唐宇. 电磁探测卫星星上自主规划模型及优化算法. 航空学报, 2010, 31(5): 1045−1053

    Chen Hao, Li Jun, Jing Ning, Liu Xiang-Hui, Tang Yu. Scheduling model and algorithms for autonomous electromagnetic detection satellites. Acta Aeronautica et Astronautica Sinica, 2010, 31(5): 1045−1053
    [15] 陈祥国, 武小悦. 基于解构造图的卫星数传调度ACO算法. 系统工程与电子技术, 2010, 32(3): 592−597

    Chen Xiang-Guo, Wu Xiao-Yue. ACO algorithm of satellite data transmission scheduling based on solution construction graph. Systems Engineering and Electronics, 2010, 32(3): 592−597
    [16] Xu B, Wang D H, Liu W X, Sun G F. A hybrid navigation constellation inter-satellite link assignment algorithm for the integrated optimization of the inter-satellite observing and communication performance. In: Proceedings of the 2015 China Satellite Navigation Conference. Berlin, Germany: Springer, 2015. 283−296
    [17] 张帆, 王钧, 李军, 景宁. 基于时间序无圈有向图的多准则优化成像调度. 国防科技大学学报, 2005, 27(6): 61−66 doi:  10.3969/j.issn.1001-2486.2005.06.014

    Zhang Fan, Wang Jun, Li Jun, Jing Ning. Multicriteria optimal imaging scheduling based on time ordered acyclic directed graph. Journal of National University of Defense Technology, 2005, 27(6): 61−66 doi:  10.3969/j.issn.1001-2486.2005.06.014
    [18] 王钧. 成像卫星综合任务调度模型与优化方法研究[博士学位论文], 国防科技大学, 中国, 2007

    Wang Jun. Research on Modeling and Optimization Techniques in United Mission Scheduling of Imaging Satellites [Ph. D. dissertation], National University of Defense Technology, China, 2007
    [19] Hall N G, Magazine M J. Maximizing the value of a space mission. European Journal of Operational Research, 1994, 78(2): 224−241 doi:  10.1016/0377-2217(94)90385-9
    [20] 顾中舜, 陈英武. 对地观测卫星调度的混合整数规划模型及求解. 飞行器测控学报, 2007, 26(1): 19−24

    Gu Zhong-Shun, Chen Ying-Wu. MIP model and algorithm for resolving scheduling of earth observation satellites. Journal of Spacecraft TT&C Technology, 2007, 26(1): 19−24
    [21] 贺仁杰, 顾中舜. 成像观测卫星多星联合调度模型及其列生成求解算法研究. 飞行器测控学报, 2008, 27(4): 5−9

    He Ren-Jie, Gu Zhong-Shun. Multi-satellite scheduling model and column generation algorithm for imaging satellites. Journal of Spacecraft TT&C Technology, 2008, 27(4): 5−9
    [22] Xiao Y Y, Zhang S Y, Yang P, You M, Huang J Y. A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties. Reliability Engineering and System Safety, 2019, 188: 263−275 doi:  10.1016/j.ress.2019.03.016
    [23] Lemaître M, Verfaillie G, Jouhaud F, Lachiver J M, Bataille N. Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6(5): 367−381 doi:  10.1016/S1270-9638(02)01173-2
    [24] Xu R, Chen H P, Liang X L, Wang H M. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Systems with Applications, 2016, 51(1): 195−206
    [25] Lin W C, Liao D Y, Liu C Y, Lee Y Y. Daily imaging scheduling of an earth observation satellite. IEEE Transactions on Systems Man and Cybernetics, 2005, 35(2): 213−223 doi:  10.1109/TSMCA.2005.843380
    [26] 程思微, 张辉, 沈林成. 利用混合整数规划的卫星操作规划问题研究. 计算机工程与应用, 2011, 47(3): 229−232 doi:  10.3778/j.issn.1002-8331.2011.03.067

    Cheng Si-Wei, Zhang Hui, Shen Lin-Cheng. Research on satellite operation planning using MIP method. Computer Engineering and Applications, 2011, 47(3): 229−232 doi:  10.3778/j.issn.1002-8331.2011.03.067
    [27] 任仙海, 杨乐平, 朱彦伟. 多GEO卫星接近观测任务规划. 飞行力学, 2011, 29(3): 76−79

    Ren Xian-Hai, Yang Le-Ping, Zhu Yan-Wei. Mission planning for multiple GEO satellite proximity inspection. Flight Dynamics, 2011, 29(3): 76−79
    [28] Sun K, Yang Z Y, Wang P, Chen Y W. Mission planning and action planning for agile earth-observing satellite with genetic algorithm. Journal of Harbin Institute of Technology, 2013, 20(5): 51−56
    [29] Cui K K, Xiang J H, Zhang Y L. Mission planning optimization of video satellite for ground multi-object staring imaging. Advances in Space Research, 2018, 61(6): 1476−1489 doi:  10.1016/j.asr.2017.10.056
    [30] Bensana E, Lemaitre M, Verfaillie G. Earth observation satellite management. Constraints, 1999, 4(3): 293−299 doi:  10.1023/A:1026488509554
    [31] 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
    [32] 靳肖闪, 李军, 刘湘辉, 郭玉华, 景宁. 基于拉格朗日松弛与最大分支算法的卫星成像调度算法. 宇航学报, 2008, 29(2): 310−315

    Jin Xiao-Shan, Li Jun, Liu Xiang-Hui, Guo Yu-Hua, Jing Ning. An algorithm for satellite imaging scheduling based on Lagrangian relaxation and max weighted component algorithm. Journal of Astronautics, 2008, 29(2): 310−315
    [33] Wang P, Reinelt G, Gao P, Tan Y J. A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Computers & Industrial Engineering, 2011, 61(2): 322−335
    [34] Liu X L, Jiang W, Li Y J. Mutation particle swarm optimization for earth observation satellite mission planning. In: Proceedings of the 2012 International Conference on Management Science & Engineering 19th Annual Conference. Dallas, USA: IEEE, 2012. 236−243
    [35] Jiang J, Choi J, Bae H J, Choi I C. Image collection planning for Korea multi-purpose SATellite-2. European Journal of Operational Research, 2013, 230(1): 190−199 doi:  10.1016/j.ejor.2013.04.009
    [36] Wu G H, Liu J, Ma M H, Qiu D S. A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 2013, 40(7): 1884−1894
    [37] Lemaître M, Verfaillie G, Jouhaud F, Lachiver J M, Bataille N. How to manage the new generation of agile earth observation satellites. In: Proceedings of the 6th SpaceOps Conference. Paris, France: ESA, 2000. 1−8
    [38] He Y M, He L, Wang Y, Xiao Y, Chen Y W, Xing L N. Autonomous mission replanning method for imaging satellites considering real-time weather conditions. Journal of Computational and Theoretical Nanoscience, 2016, 13(10): 6967−6973 doi:  10.1166/jctn.2016.5654
    [39] He Y M, Chen Y W, Lu J M, Chen C, Wu G H. 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
    [40] Mok S H, Jo S, Bang H, Leeghim H. Heuristic-based mission planning for an agile earth observation satellite. International Journal of Aeronautical and Space Sciences, 2019, 20(3): 781−791 doi:  10.1007/s42405-018-0105-4
    [41] 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
    [42] Song B Y, Yao F, Chen Y N, Chen Y G, Chen Y W. A hybrid genetic algorithm for satellite image downlink scheduling problem. Discrete Dynamics in Nature and Society, 2018: 1531452
    [43] 张超, 李艳斌. 多敏捷卫星协同任务规划调度方法. 科学技术与工程, 2017, 17(22): 276−282

    Zhang Chao, Li Yan-Bin. Planning and scheduling method for multi agile satellite coordinated mission. Science Technology and Engineering, 2017, 17(22): 276−282
    [44] Liu X L, Laporte G, Chen Y W, He R J. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86: 41−53
    [45] Kim H, Chang Y K. Mission scheduling optimization of SAR satellite constellation for minimizing system response time. Aerospace Science and Technology, 2015, 40(1): 17−32
    [46] Wu G H, Wang H L, Pedrycz W, Li H F, Wang L. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy. Computers & Industrial Engineering, 2017, 113: 576−588
    [47] She Y C, Li S, Zhao Y B. Onboard mission planning for agile satellite using modified mixed-integer linear programming. Aerospace Science and Technology, 2018, 72: 204−216 doi:  10.1016/j.ast.2017.11.009
    [48] Chen X Y, Reinelt G, Dai G M, Spitz A. A mixed integer linear programming model for multi-satellite scheduling. European Journal of Operational Research, 2019, 275(2): 694−707 doi:  10.1016/j.ejor.2018.11.058
    [49] Frank J, Do M, Tran T T. Scheduling ocean color observations for a GEO-stationary satellite. In: Proceedings of the 26th International Conference on International Conference on Automated Planning and Scheduling. California, USA: AAAI, 2016. 376−384
    [50] Sarkheyli A, Bagheri A, Ghorbani-Vaghei B, Askari-Moghadamd R. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions. Aerospace Science and Technology, 2013, 29(1): 287−295 doi:  10.1016/j.ast.2013.04.001
    [51] Niu X N, Zhai X J, Tang H, Wu L X. Multi-satellite scheduling approach for dynamic areal tasks triggered by emergent disasters. In: Proceedings of International Archives of the Photogrammetry Remote Sensing and Spatial Information Sciences. Prague, Czech: ISPRS, 2016. 475−481
    [52] Chen X Y, Reinelt G, Dai G M, Wang M C. Priority-based and conflict-avoidance heuristics for multi-satellite scheduling. Applied Soft Computing, 2018, 69: 177−191 doi:  10.1016/j.asoc.2018.04.021
    [53] Valicka C G, Garcia D, Staid A, Watson J P, Hackebeil G, Rathinam S, 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
    [54] Nag S, Li A S, Merrick J H. Scheduling algorithms for rapid imaging using agile Cubesat constellations. Advances in Space Research, 2018, 61: 891−913 doi:  10.1016/j.asr.2017.11.010
    [55] Zhu W M, Hu X X, Xia W, Jin P. 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
    [56] He L, Liu X L, Laporte G, Chen Y W, Chen Y G. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100: 12−25
    [57] Li J, Li J, Chen H, Jing N. A data transmission scheduling algorithm for rapid-response earth-observing operations. Chinese Journal of Aeronautics, 2014, 27(2): 349−364 doi:  10.1016/j.cja.2014.02.014
    [58] 杜永浩, 邢立宁, 陈盈果, 向尚. 卫星任务调度统一化建模与多策略协同求解方法. 控制与决策, 2019, 34(9): 1847−1856

    Du Yong-Hao Xing Li-Ning, Chen Ying-Guo, Xiang Siang. Unified modeling and multi-strategy collaborative optimization for satellite task scheduling. Control and Decision, 2019, 34(9): 1847−1856
    [59] Bensana E, Verfaillie G, Agnese J C, Bataille N. Exact and inexact methods for the daily management of an earth observation satellite. In: Proceeding of the 4th SpaceOps Conference. Paris, France: ESA, 1996. 507−514
    [60] Vasquez M, Hao J K. A “Logic-constrained" knapsack formulation and a tabu search algorithm for the daily photograph scheduling of an Earth observation satellite. Computational Optimization and Applications, 2001, 20(2): 137−157 doi:  10.1023/A:1011203002719
    [61] Spangelo S, Cutler J, Gilson K, Cohn A. Optimization-based scheduling for the single-satellite, multi-ground station communication problem. Computers & Operations Research, 2015, 57: 1−16
    [62] 高黎, 周利安, 沙基昌. 分布式卫星系统协作任务分配模型及优化算法. 系统工程学报, 2009, 24(4): 445−450 doi:  10.3969/j.issn.1000-5781.2009.04.009

    Gao Li, Zhou Li-An, Sha Ji-Chang. Task allocation model and algorithm for DSS cooperation mechanism. Journal of Systems Engineering, 2009, 24(4): 445−450 doi:  10.3969/j.issn.1000-5781.2009.04.009
    [63] 郝会成, 姜维, 李一军, 袁子清. 基于Multi-Agent敏捷卫星动态任务规划问题. 国防科技大学学报, 2013, 35(1): 53−59 doi:  10.3969/j.issn.1001-2486.2013.01.011

    Hao Hui-Cheng, Jiang Wei, Li Yi-Jun, Yuan Zi-Qing. Research on agile satellite dynamic mission planning based on multi-agent. Journal of National University of Defense Technology, 2013, 35(1): 53−59 doi:  10.3969/j.issn.1001-2486.2013.01.011
    [64] Skobelev P O, Simonova E V, Zhilyaev A A, Travin V S. Application of multi-agent technology in the scheduling system of swarm of earth remote sensing satellites. Procedia Computer Science, 2017, 103: 396−402 doi:  10.1016/j.procs.2017.01.127
    [65] Du B, Li S. A new multi-satellite autonomous mission allocation and planning method. Acta Astronautica, 2019, 163(B): 287−298
    [66] Zheng Z X, Guo J, Gill E. Distributed onboard mission planning for multi-satellite systems. Aerospace Science and Technology, 2019, 89: 111−122 doi:  10.1016/j.ast.2019.03.054
    [67] 邢立宁, 王原, 何永明, 何磊. 基于BP神经网络的星上任务可调度性预测方法. 中国管理科学, 2015, 23(S1): 117−124

    Xing Li-Ning, Wang Yuan, He Yong-Ming, He Lei. An earth observation satellite task schedulability prediction method based on BP artificial network. Chinese Journal of Management Science, 2015, 23(S1): 117−124
    [68] 王冲, 景宁, 李军, 王钧, 陈浩. 一种基于多Agent强化学习的多星协同任务规划算法. 国防科技大学学报, 2011, 33(1): 53−58 doi:  10.3969/j.issn.1001-2486.2011.01.012

    Wang Chong, Jing Ning, Li Jun, Wang Jun, Chen Hao. An algorithm of cooperative multiple satellites mission planning based on multi-agent reinforcement learning. Journal of National University of Defense Technology, 2011, 33(1): 53−58 doi:  10.3969/j.issn.1001-2486.2011.01.012
    [69] Wang C, Li J, Jing N, Wang J, Chen H. A distributed cooperative dynamic task planning algorithm for multiple satellites based on multi-agent hybrid learning. Chinese Journal of Aeronautics, 2011, 24(4): 493−505 doi:  10.1016/S1000-9361(11)60057-5
    [70] Wang H J, Yang Z, Zhou W G, Li D L. Online scheduling of image satellites based on neural networks and deep reinforcement learning. Chinese Journal of Aeronautics, 2019, 32(4): 1011−1019 doi:  10.1016/j.cja.2018.12.018
    [71] Reddy S C, Brown W L. Single Processor Scheduling with Job Priorities and Arbitrary Ready and Due Times. Computer Sciences Corporation, Beltsville, USA, 1986
    [72] Reddy S C. Scheduling of tracking and data relay satellite system (TDRSS) antennas: scheduling with sequence dependent setup times. In: ORSA/TIMS Joint National Meeting. Denver, USA: Military Operations Research Society. 1988
    [73] Rojanasoonthon S, Bard J F, Reddy S D. Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system. Journal of the Operational Research Society, 2003, 54(8): 806−821 doi:  10.1057/palgrave.jors.2601575
    [74] Rojanasoonthon S, Bard J. A GRASP for parallel machine scheduling with time windows. INFORMS Journal on Computing, 2005, 17(1): 32−51 doi:  10.1287/ijoc.1030.0048
    [75] Zhuang S F, Yin Z D, Wu Z L, Shi Z G. The relay satellite scheduling based on artificial bee colony algorithm. In: Proceedings of the 17th International Symposium on Wireless Personal Multimedia Communications. Sydney, Australia: IEEE, 2014. 635−640
    [76] 庄树峰. 跟踪与数据中继卫星系统资源调度技术研究[博士学位论文], 哈尔滨工业大学, 中国, 2017

    Zhuang Shu-Feng. Research on Resource Scheduling Technology of Tracking and Data Relay Satellite System [Ph. D. dissertation], Harbin Institute of Technology, China, 2017
    [77] 贺川, 孟宪贵, 祝转民, 李德峰, 龙运军. 基于执行时段滑动调整策略的中继卫星任务规划算法设计. 飞行器测控学报, 2015, 34(3): 246−253

    He Chuan, Meng Xian-Gui, Zhu Zhuan-Min, Li De-Feng, Long Yun-Jun. Design of mission programming algorithm for TDRS based on execution time slide adjustment strategy. Journal of Spacecraft TT&C Technology, 2015, 34(3): 246−253
    [78] 刘润滋, 盛敏, 唐成圆, 李建东, 杜凯, 杨永安. 基于任务拆分聚合的中继卫星系统任务规划方法. 通信学报, 2017, 38(Z1): 110−117 doi:  10.11959/j.issn.1000-436x.2017243

    Liu Run-Zi, Sheng Min, Tang Cheng-Yuan, Li Jian-Dong, Du Kai, Yang Yong-An. Tasking planning based on task splitting and merging in relay satellite network. Journal on Communications, 2017, 38(Z1): 110−117 doi:  10.11959/j.issn.1000-436x.2017243
    [79] 郭超, 熊伟, 郝利云. 基于双层优先级的中继卫星系统任务调度算法. 计算机应用研究, 2018, 35(5): 1506−1510 doi:  10.3969/j.issn.1001-3695.2018.05.049

    Guo Chao, Xiong Wei, Hao Li-Yun. Relay satellite system task scheduling algorithm based on double-layer priority. Application Research of Computers, 2018, 35(5): 1506−1510 doi:  10.3969/j.issn.1001-3695.2018.05.049
    [80] 顾中舜. 中继卫星动态调度问题建模及优化技术研究[博士学位论文], 国防科技大学, 中国, 2007

    Gu Zhong-Shun. Research on the Relay Satellite Dynamic Scheduling Problem Modeling and Optimizational Technology [Ph. D. dissertation], National University of Defense Technology, China, 2007
    [81] 赵静, 赵卫虎, 李勇军, 赵尚弘, 韩磊, 李轩. 微波/光混合链路数据中继卫星系统资源调度算法. 中国激光, 2013, 40(10): 1005005 doi:  10.3788/CJL201340.1005005

    Zhao Jing, Zhao Wei-Hu, Li Yong-Jun, Zhao Shang-Hong, Han Lei, Li Xuan. Scheduling algorithm for data relay satellite with microwave and laser hybrid links. Chinese Journal of Lasers, 2013, 40(10): 1005005 doi:  10.3788/CJL201340.1005005
    [82] 赵静, 赵卫虎, 李勇军, 赵尚弘, 王翔, 韩磊, 等. 基于改进NSGA-Ⅱ算法的微波/光混合链路中继卫星多目标资源调度算法. 中国激光, 2013, 40(12): 1205003 doi:  10.3788/CJL201340.1205003

    Zhao Jing, Zhao Wei-Hu, Li Yong-Jun, Zhao Shang-Hong, Wang Xiang, Han Lei, et al. Multi-objective resources scheduling algorithm for microwave and laser hybrid links data relay satellite based on improved NSGA-Ⅱ algorithm. Chinese Journal of Lasers, 2013, 40(12): 1205003 doi:  10.3788/CJL201340.1205003
    [83] Zhao W H, Zhao J, Zhao S H, Li Y J, Dong Y, Dong C, et al. Resources scheduling for data relay satellite with microwave and optical hybrid links based on improved niche genetic algorithm. Optik, 2014, 125(3): 3370−3375
    [84] 方炎申, 陈英武, 邹凯, 周利安. 基于约束满足问题的中继卫星调度问题研究. 运筹与管理, 2005, 14(4): 74−79 doi:  10.3969/j.issn.1007-3221.2005.04.017

    Fang Yan-Shen, Chen Ying-Wu, Zou Kai, Zhou Li-An. Research on relay satellite scheduling problem with CSP. Operations Research and Management Science, 2005, 14(4): 74−79 doi:  10.3969/j.issn.1007-3221.2005.04.017
    [85] 方炎申, 陈英武, 顾中舜. 中继卫星调度问题的CSP模型. 国防科技大学学报, 2005, 27(2): 6−10 doi:  10.3969/j.issn.1001-2486.2005.02.002

    Fang Yan-Shen, Chen Ying-Wu, Gu Zhong-Shun. CSP model of the relay satellite scheduling. Journal of National University of Defense Technology, 2005, 27(2): 6−10 doi:  10.3969/j.issn.1001-2486.2005.02.002
    [86] 方炎申, 陈英武, 王军民. 中继卫星多址链路调度问题的约束规划模型及算法研究. 航天返回与遥感, 2006, 27(4): 62−67 doi:  10.3969/j.issn.1009-8518.2006.04.013

    Fang Yan-Shen, Chen Ying-Wu, Wang Jun-Min. Constraint programming model and algorithms for multiple access links scheduling of tracking and data relay satellite system (TDRSS). Spacecraft Recovery & Remote Sensing, 2006, 27(4): 62−67 doi:  10.3969/j.issn.1009-8518.2006.04.013
    [87] 贺川, 李亚晶, 丘震. 按需申请模式下的中继卫星任务规划模型与算法设计. 中国空间科学技术, 2017, 37(6): 46−55

    He Chuan, Li Ya-Jing, Qiu Zhen. Task programming models and algorithms of tracking and data relay satellite in application-on-demand. Chinese Space Science and Technology, 2017, 37(6): 46−55
    [88] 何敏藩, 朱燕麒, 贾学卿. 考虑多滑动窗口的中继卫星调度模型及启发式算法. 郑州大学学报(工学版), 2018, 39(5): 11−21

    He Min-Fan, Zhu Yan-Qi, Jia Xue-Qing. Scheduling model and heuristic algorithm for tracking and data relay satellite considering multiple slide windows. Journal of Zhengzhou University (Engineering Science), 2018, 39(5): 11−21
    [89] 唐旻. 卫星系统数传与测控服务策略研究[硕士学位论文], 国防科技大学, 中国, 2013

    Tang Min. The Research on Strategies of Satellite System Data Transmission and TT&C Serving [Master dissertation], National University of Defense Technology, China, 2013
    [90] Luba O, Boyd L, Gower A, Crum J. GPS III system operations concepts. IEEE Aerospace and Electronic Systems Magazine, 2005, 20(1): 10−18 doi:  10.1109/MAES.2005.1396789
    [91] 赵爽. 卫星导航系统大国间的博弈-谈俄罗斯在美国建GLONASS地面站受阻. 国际太空, 2014, 36(10): 36−40
    [92] Gershman R, Buxbaum K L, Ludwinski J M, Paczkowski B G. Galileo mission planning for low gain antenna based operations. In: Proceedings of the 3rd International Symposium on Space Mission Operations and Ground Data Systems. Washington, USA: NASA, 1994. 279−286
    [93] Iv J C M. Performing the Galileo mission using the S-band low-gain antenna. In: Proceedings of 1994 IEEE Aerospace Applications Conference. Vail, USA: IEEE, 1994. 145-183
    [94] Toribio S. Galileo: Mission planning. In: Proceedings of the SpaceOps 2004 Conference. Montreal, Canada: AIAA, 2004
    [95] Hall S, Moreira F, Franco T. Operations planning for the Galileo constellation. In: Proceedings of the SpaceOps 2008 Conference. Heidelberg, Germany: AIAA, 2008
    [96] Marinelli F, Nocella S, Rossi F, Smriglio S. A Lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 2011, 38(11): 1572−1583
    [97] 龙运军, 陈英武, 邢立宁, 张忠山. 导航卫星上行注入任务调度模型及启发式算法. 国防科技大学学报, 2013, 35(2): 34−39 doi:  10.3969/j.issn.1001-2486.2013.02.007

    Long Yun-Jun, Chen Ying-Wu, Xing Li-Ning, Zhang Zhong-Shan. Uplink task scheduling model and two-phase heuristic algorithm of navigation satellites. Journal of National University of Defense Technology, 2013, 35(2): 34−39 doi:  10.3969/j.issn.1001-2486.2013.02.007
    [98] Tang Y Y, Wang Y K, Chen J Y, Chen H. Uplink scheduling of navigation constellation based on genetic algorithm. In: Proceedings of the 13th International Conference on Signal Processing. Chengdu, China: IEEE, 2017. 1124−1129
    [99] 闫俊刚, 邢立宁, 张忠山, 贺仁杰. 具有双重时间窗约束的作业车间调度算法. 科学技术与工程, 2016, 16(26): 85−92 doi:  10.3969/j.issn.1671-1815.2016.26.013

    Yan Jun-Gang, Xing Li-Ning, Zhang Zhong-Shan, He Ren-Jie. Dual time window constrained job-shop scheduling algorithm. Science Technology and Engineering, 2016, 16(26): 85−92 doi:  10.3969/j.issn.1671-1815.2016.26.013
    [100] 张忠山, 王沛, 贺仁杰, 龙运军. 考虑星间链路的星地时间同步与上注调度的启发式算法. 全球定位系统, 2012, 37(5): 38−45

    Zhang Zhong-Shan, Wang Pei, He Ren-Jie, Long Yun-Jun. A heuristic algorithm for the scheduling of clock synchronization and uplink tasks between satellites and ground stations based on inter-satellite links. GNSS World of China, 2012, 37(5): 38−45
    [101] Parish D A. A Genetic Algorithm Approach to Automating Satellite Range Scheduling [Master dissertation], Air Force Institute of Technology, USA, 1994
    [102] Barbulescu L, Howe A E, Watson J P, Whitley L D. Satellite range scheduling: a comparison of genetic, heuristic and local search. In: Proceedings of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 2002. 611−620
    [103] Barbulescu L, Howe A, Whitley D. AFSCN scheduling: how the problem and solution have evolved. Mathematical and Computer Modelling, 2006, 43(9-10): 1023−1037 doi:  10.1016/j.mcm.2005.12.004
    [104] Barbulescu L, Howe A E, Whitley L D, Roberts M. Understanding algorithm performance on an oversubscribed scheduling application. Journal of Artificial Intelligence Research, 2006, 27(1): 577−615
    [105] 郑晋军, 张乃通, 张丽艳. 合理利用测控资源的动态调度模型. 高技术通讯, 2002, 12(7): 22−27 doi:  10.3321/j.issn:1002-0470.2002.07.005

    Zheng Jin-Jun, Zhang Nai-Tong, Zhang Li-Yan. Dynamical schedule model for rational utilize of TT&C system. High Technology Letters, 2002, 12(7): 22−27 doi:  10.3321/j.issn:1002-0470.2002.07.005
    [106] 张鹏, 冯旭祥, 葛小青. 基于改进遗传算法的多天线地面站硬件资源分配方法. 计算机工程与科学, 2017, 39(6): 1155−1163 doi:  10.3969/j.issn.1007-130X.2017.06.020

    Zhang Peng, Feng Xu-Xiang, Ge Xiao-Qing. A hardware resource allocation method for multi-antenna ground station based on improved genetic algorithm. Computer Engineering and Science, 2017, 39(6): 1155−1163 doi:  10.3969/j.issn.1007-130X.2017.06.020
    [107] Barbulescu L, Watson J P, Whitley L D, Howe A E. Scheduling space-ground communications for the air force satellite control network. Journal of Scheduling, 2004, 7(1): 7−34 doi:  10.1023/B:JOSH.0000013053.32600.3c
    [108] Li Y Q, Wang R X, Liu Y, Xu M Q. Satellite range scheduling with the priority constraint: an improved genetic algorithm using a station ID encoding method. Chinese Journal of Aeronautics, 2015, 28(3): 789−803 doi:  10.1016/j.cja.2015.04.012
    [109] Arbabi M, Garate J A, Kocher D F. Interactive real time scheduling and control. In: Proceedings of the 1985 Summer Simulation Conference. San Diego, USA: Society for Computer Simulation, 1985. 271−277
    [110] 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
    [111] Blöchliger I, Zufferey N. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008, 35(3): 960−975
    [112] 张雁, 党群, 黄永宣. 带预估选择的Memetic算法求解多星测控资源调度问题. 西安交通大学学报, 2009, 43(10): 37−41 doi:  10.7652/xjtuxb200910008

    Zhang Yan, Dang Qun, Huang Yong-Xuan. A memetic algorithm with predictive selection for multi-satellite TT&C resources scheduling problems. Journal of Xi'an Jiaotong University, 2009, 43(10): 37−41 doi:  10.7652/xjtuxb200910008
    [113] 徐小辉. 陆基卫星测控调度问题建模及算法技术研究[硕士学位论文], 清华大学, 中国, 2012

    Xu Xiao-Hui. Study on Land-based Satellite TT&C Scheduling Models and Algorithms [Master dissertation], Tsinghua University, China, 2012
    [114] Zhang N, Feng Z R. Cooperative ant colony optimization for multisatellite resource scheduling problem. In: Proceedings of the Congress on Evolutionary Computation. Singapore, Singapore: IEEE, 2007. 2822−2828
    [115] Zhang N, Feng Z R, Ke L J. Guidance-solution based ant colony optimization for satellite control resource scheduling problem. Applied Intelligence, 2011, 35(3): 436−444 doi:  10.1007/s10489-010-0234-3
    [116] Zhang Z J, Zhang N, Feng Z R. Multi-satellite control resource scheduling based on ant colony optimization. Expert Systems with Applications, 2014, 41(6): 2816−2823 doi:  10.1016/j.eswa.2013.10.014
    [117] Zhang Z J, Hu F N, Zhang N. Ant colony algorithm for satellite control resource scheduling problem. Applied Intelligence, 2018, 48(10): 3295−3305 doi:  10.1007/s10489-018-1144-z
    [118] 陈祥国, 武小悦. 卫星数传资源负荷均衡调度模型及蚁群优化算法. 系统工程, 2008, 26(12): 91−97

    Chen Xiang-Guo, Wu Xiao-Yue. Model of satellite data transmission resource workload balance scheduling and ant colony optimization algorithm. Systems Engineering, 2008, 26(12): 91−97
    [119] 陈祥国. 卫星数传调度的蚁群优化模型及算法研究[博士学位论文], 国防科技大学, 中国, 2010

    Chen Xiang-Guo. Research on Model and Algorithm of Ant Colony Optimization for Satellite Data Transmission Scheduling [Ph. D. dissertation], National University of Defense Technology, China, 2010
    [120] 王海波, 徐敏强, 王日新, 李玉庆. 基于蚁群优化-模拟退火的天地测控资源联合调度. 宇航学报, 2012, 33(11): 1636−1645 doi:  10.3873/j.issn.1000-1328.2012.11.012

    Wang Hai-Bo, Xu Min-Qiang, Wang Ri-Xin, Li Yu-Qing. Solving space and ground TT&C resources integrated scheduling problem with ant colony optimization-simulated annealing algorithm. Journal of Astronautics, 2012, 33(11): 1636−1645 doi:  10.3873/j.issn.1000-1328.2012.11.012
    [121] Vázquez A J, Erwin R S. On the tractability of satellite range scheduling. Optimization Letters, 2015, 9(2): 311−327 doi:  10.1007/s11590-014-0744-8
    [122] Vázquez A J, Scott Erwin R. Robust fixed interval satellite range scheduling. In: Proceedings of the 2015 IEEE Aerospace Conference. Big Sky, USA: IEEE, 2014
    [123] Vázquez A J, Erwin R S. An Introduction to Optimal Satellite Range Scheduling. Berlin, Germany: Springer, 2015. 77−151
    [124] 王远振, 赵坚, 聂成. 多卫星-地面站系统的Petri网模型研究. 空军工程大学学报, 2003, 4(2): 7−11

    Wang Yuan-Zhen, Zhao Jian, Nie Cheng. Study on Petri net model for multi-satellites-ground station system. Journal of Air Force Engineering University (Natural Science Edition), 2003, 4(2): 7−11
    [125] 王远振, 赵坚, 聂成. 多星地面站设备优化调度方法研究. 计算机仿真, 2003, 20(7): 7−19, 54

    Wang Yuan-Zhen, Zhao Jian, Nie Cheng. Study on optimal scheduling for multi-satellites-ground stations system. Computer Simulation, 2003, 20(7): 7−19, 54
    [126] 金光, 武小悦, 高卫斌. 卫星地面站资源配置仿真研究. 系统仿真学报, 2004, 16(11): 2401−2403, 2408 doi:  10.3969/j.issn.1004-731X.2004.11.009

    Jin Guang, Wu Xiao-Yue, Gao Wei-Bin. Simulation-based study on resource deployment of satellite ground station. Journal of System Simulation, 2004, 16(11): 2401−2403, 2408 doi:  10.3969/j.issn.1004-731X.2004.11.009
    [127] 王远振, 高卫斌, 聂成. 多星地面站系统资源配置优化研究综述. 系统工程与电子技术, 2004, 26(4): 437−439, 453 doi:  10.3321/j.issn:1001-506X.2004.04.005

    Wang Yuan-Zhen, Gao Wei-Bin, Nie Cheng. Summary of the resource configuration optimization for a multi-satellite ground station system. Systems Engineering and Electronics, 2004, 26(4): 437−439, 453 doi:  10.3321/j.issn:1001-506X.2004.04.005
    [128] Gooley T D. Automating the Satellite Range Scheduling Process [Master dissertation], Air Force Institute of Technology, USA, 1993
    [129] Gooley T D, Borsi J J, Moore J T. Automating air force satellite control network (AFSCN) scheduling. Mathematical and Computer Modelling, 1996, 24(2): 91−101 doi:  10.1016/0895-7177(96)00093-3
    [130] 贺仁杰, 谭跃进. 基于约束满足的卫星地面站资源优化分配问题研究. 计算机工程与应用, 2004, 40(18): 229−232 doi:  10.3321/j.issn:1002-8331.2004.18.072

    He Ren-Jie, Tan Yue-Jin. Apply constraint satisfaction to optimal allocation of satellite ground station resource. Computer Engineering and Applications, 2004, 40(18): 229−232 doi:  10.3321/j.issn:1002-8331.2004.18.072
    [131] 刘洋, 贺仁杰, 谭跃进. 基于约束满足的多卫星调度模型研究. 系统工程与电子技术, 2004, 26(8): 1076−1079 doi:  10.3321/j.issn:1001-506X.2004.08.020

    Liu Yang, He Ren-Jie, Tan Yue-Jin. Modeling the scheduling problem of multi-satellites based on the constraint satisfaction. Systems Engineering and Electronics, 2004, 26(8): 1076−1079 doi:  10.3321/j.issn:1001-506X.2004.08.020
    [132] Luo K P, Wang H H, Li Y J, Li Q. High-performance technique for satellite range scheduling. Computers & Operations Research, 2017, 85: 12−21
    [133] Xhafa F, Sun J, Barolli A, Biberaj A, Barolli L. Genetic algorithms for satellite scheduling problems. Mobile Information Systems, 2012, 8(4): 351−377 doi:  10.1155/2012/717658
    [134] Xhafa F, Herrero X, Barolli A, Barolli L, Takizawa M. Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem. Journal of Computer and System Sciences, 2013, 79(7): 1086−1100 doi:  10.1016/j.jcss.2013.01.023
    [135] Xhafa F, Herrero X, Barolli A, Takizawa M. A simulated annealing algorithm for ground station scheduling problem. In: Proceedings of the 16th International Conference on Network-based Information Systems. Gwangju, South Korea: IEEE, 2013. 24−30
    [136] Xhafa F, Herrero X, Barolli A, Takizawa M. A tabu search algorithm for ground station scheduling problem. In: Proceedings of the 28th International Conference on Advanced Information Networking & Applications. Victoria, Canada: IEEE, 2014. 1033−1040
    [137] Valicka C G, Garcia D, Staid A, Watson J, Rintoul M, Hackebeil G, et al. Space surveillance network scheduling under uncertainty: models and benefits. In: Proceedings of the Advanced Maui Optical and Space Surveillance Technologies Conference. Hawaii, USA: The Maui Economic Development Board, 2016. 124
    [138] Liu Z B, Feng Z R, Ren Z G. Route-reduction-based dynamic programming for large-scale satellite range scheduling problem. Engineering Optimization, 2019, 51(11): 1944−1964 doi:  10.1080/0305215X.2018.1558445
    [139] Greve G H, Hopkinson K M, Lamont G B. Evolutionary sensor allocation for the space surveillance network. Journal of Defense Modeling and Simulation, 2018, 15(3): 303−322 doi:  10.1177/1548512917712614
    [140] 刘聪锋, 杨洁. 陆基测控资源分配决策支持系统研究. 航空计算技术, 2003, 33(4): 80−83 doi:  10.3969/j.issn.1671-654X.2003.04.022

    Liu Cong-Feng, Yang Jie. Research of decision support system for grand-based tracking telemeter and command resource distribution. Aeronautical Computer Technique, 2003, 33(4): 80−83 doi:  10.3969/j.issn.1671-654X.2003.04.022
    [141] 刘聪锋. 测控资源调度管理系统的构造与实现. 航空计算技术, 2005, 35(3): 68−71 doi:  10.3969/j.issn.1671-654X.2005.03.019

    Liu Cong-Feng. The construct and realization for tracking telemeter and command resource scheduling management system. Aeronautical Computer Technique, 2005, 35(3): 68−71 doi:  10.3969/j.issn.1671-654X.2005.03.019
    [142] 凌晓冬, 刘冰, 武小悦, 吴金美. 基于本体的多星测控调度问题模型研究. 计算机与数字工程, 2010, 38(8): 62−66 doi:  10.3969/j.issn.1672-9722.2010.08.017

    Ling Xiao-Dong, Liu Bing, Wu Xiao-Yue, Wu Jin-Mei. An ontology-based model of multi-satellite TT&C scheduling problem. Computer and Digital Engineering, 2010, 38(8): 62−66 doi:  10.3969/j.issn.1672-9722.2010.08.017
    [143] Jayaweera S K, Erwin R S, Carty J. Distributed space situational awareness (D-SSA) with a satellite-assisted collaborative space surveillance network. IFAC Proceedings Volumes, 2011, 44(1): 8792−8798 doi:  10.3182/20110828-6-IT-1002.00258
    [144] Shen D, Jia B, Chen G S, Pham K, Blasch E. Game optimal sensor management strategies for tracking elusive space objects. In: Proceedings of the 2017 IEEE Aerospace Conference. Big Sky, USA: IEEE, 2017
    [145] 凌晓冬, 武小悦, 刘琦. 基于Agent的航天测控资源调度问题建模分析. 系统工程与电子技术, 2008, 30(11): 2220−2223 doi:  10.3321/j.issn:1001-506X.2008.11.044

    Ling Xiao-Dong, Wu Xiao-Yue, Liu Qi. Analysis of modeling of TT&C resource scheduling problem based on agent technology. Systems Engineering and Electronics, 2008, 30(11): 2220−2223 doi:  10.3321/j.issn:1001-506X.2008.11.044
    [146] 杜红梅, 刘明盛. 基于多智能体协作技术的卫星测控资源动态调度问题解算. 装备指挥技术学院学报, 2010, 21(3): 76−80

    Du Hong-Mei, Liu Ming-Sheng. The method of satellite TT&C resources dynamic scheduling problem based on the technique of multi-agent collaboration. Journal of the Academy of Equipment Command & Technology, 2010, 21(3): 76−80
    [147] 冯宏胜, 陈杨, 武小悦. 卫星地面站资源配置的SVM回归模型. 飞行器测控学报, 2011, 30(2): 15−19

    Feng Hong-Sheng, Chen Yang, Wu Xiao-Yue. SVM regression model for satellite ground station resources allocation. Journal of Spacecraft TT&C Technology, 2011, 30(2): 15−19
    [148] Ahn H S, Jung O, Choi S, Son J H, Chung D, Kim G. An optimal satellite antenna profile using reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, 2011, 41(3): 393−406 doi:  10.1109/TSMCC.2010.2055049
    [149] Air Force Office of Scientific Research. Exploiting elementary landscapes for search (AFSCN scheduling problems) [Online], available: http://www.cs.colostate.edu/sched/data.html, May 1, 2019
    [150] Beaumet G, Verfaillie G, Charmeau M C. Feasibility of autonomous decision making on board an agile earth-observing satellite. Computational Intelligence, 2015, 27(1): 123−139
    [151] 刘晓娣, 李军, 陈浩, 靳肖闪, 陈荦. 多卫星成像任务规划的冲突消解. 电光与控制, 2008, 15(10): 10−15 doi:  10.3969/j.issn.1671-637X.2008.10.003

    Liu Xiao-Di, Li Jun, Chen Hao, Jin Xiao-Shan, Chen Luo. How to solve the collision in multi-satellite imaging mission planning. Electronics Optics & Control, 2008, 15(10): 10−15 doi:  10.3969/j.issn.1671-637X.2008.10.003
    [152] 冉承新, 熊纲要, 王慧林, 邱涤珊. 电子侦察卫星任务规划调度模型与算法研究. 通信对抗, 2009, 30(1): 3−8, 13

    Ran Cheng-Xin, Xiong Gang-Yao, Wang Hui-Lin, Qiu Di-Shan. Study of electronic reconnaissance satellite mission scheduling model and algorithm. Communication Countermeasures, 2009, 30(1): 3−8, 13
    [153] 刘彬彬, 李晖, 赵曼, 董理君, 吴杰. 基于任务压缩的成像卫星任务规划. 无线电工程, 2017, 47(11): 73−78 doi:  10.3969/j.issn.1003-3106.2017.11.16

    Liu Bin-Bin, Li Hui, Zhao Man, Dong Li-Jun, Wu Jie. Imaging satellite mission planning based on task compression. Radio Engineering, 2017, 47(11): 73−78 doi:  10.3969/j.issn.1003-3106.2017.11.16
    [154] 金光, 武小悦, 高卫斌. 卫星地面站资源调度优化模型及启发式算法. 系统工程与电子技术, 2004, 26(12): 1839−1841, 1875 doi:  10.3321/j.issn:1001-506X.2004.12.026

    Jin Guang, Wu Xiao-Yue, Gao Wei-Bin. Ground station resource scheduling optimization model and its heuristic algorithm. Systems Engineering and Electronics, 2004, 26(12): 1839−1841, 1875 doi:  10.3321/j.issn:1001-506X.2004.12.026
    [155] 杨萍, 杨锋, 吴斌, 黄永宣. 用启发式算法和基于冲突的回跳算法求解卫星测控资源调度问题. 宇航学报, 2007, 28(6): 1609−1613 doi:  10.3321/j.issn:1000-1328.2007.06.033

    Yang Ping, Yang Feng, Wu Bin, Huang Yong-Xuan. Heuristic algorithm and conflict-based backjumping algorithm for satellite TT&C resource scheduling. Journal of Astronautics, 2007, 28(6): 1609−1613 doi:  10.3321/j.issn:1000-1328.2007.06.033
    [156] Tsatsoulis C, Van Dyne M. Integrating artificial intelligence techniques to generate ground station schedules. In: Proceedings of the 2014 IEEE Aerospace Conference. Big Sky, USA: IEEE, 2014
    [157] Lemaître M, Verfaillie G, Fargier H, Lang J, Bataille N, Lachiver J M. Equitable allocation of earth observing satellites resources. In: Proceedings of the 5th ONERA-DLR Aerospace Symposium. Toulouse, French: ONERA, 2003
    [158] Du Y H, Wang T, Xin B, Wang L, Chen Y G, Xing L N. A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Transactions on Evolutionary Computation, 2019 doi:  10.1109/TEVC.2019.2934148
    [159] 周军升. 基于多Agent的多星任务分配问题研究[硕士学位论文], 国防科技大学, 中国, 2009

    Zhou Jun-Sheng. Research on Task Allocation for Multiple Satellites Based on Multiple Agents [Master dissertation], National University of Defense Technology, China, 2009
    [160] 邱涤珊, 黄维, 黄小军, 马满好. 电子侦察卫星任务合成探测及混合调度. 系统工程与电子技术, 2011, 33(9): 2012−2018 doi:  10.3969/j.issn.1001-506X.2011.09.18

    Qiu Di-Shan, Huang Wei, Huang Xiao-Jun, Ma Man-Hao. Task merging and detecting with hybrid scheduling for electronic reconnaissance satellites. Systems Engineering and Electronics, 2011, 33(9): 2012−2018 doi:  10.3969/j.issn.1001-506X.2011.09.18
    [161] 孙凯, 邢立宁, 陈英武. 基于分解优化策略的多敏捷卫星联合对地观测调度. 计算机集成制造系统, 2013, 19(1): 127−136

    Sun Kai, Xing Li-Ning, Chen Ying-Wu. Agile earth observing satellites mission scheduling based on decomposition optimization algorithm. Computer Integrated Manufacturing Systems, 2013, 19(1): 127−136
    [162] Land A H, Doig A G. An automatic method of solving discrete programming problems. Econometrica, 1960, 28(3): 497−520 doi:  10.2307/1910129
    [163] Little J D C, Murty K G, Sweeney D W, Karel C. An algorithm for the traveling salesman problem. Operations Research, 1963, 11(6): 972−989 doi:  10.1287/opre.11.6.972
    [164] 王沛, 谭跃进. 多星联合对地观测调度问题的列生成算法. 系统工程理论与实践, 2011, 31(10): 1932−1939 doi:  10.12011/1000-6788(2011)10-1932

    Wang Pei, Tan Yue-Jin. Column generation for the earth observation satellites scheduling problem. Systems Engineering-Theory & Practice, 2011, 31(10): 1932−1939 doi:  10.12011/1000-6788(2011)10-1932
    [165] Ribeiro G M, Constantino M F, Lorena L A N. Strong formulation for the Spot 5 daily photograph scheduling problem. Journal of Combinatorial Optimization, 2009, 20(4): 385−398
    [166] 王建江. 云层不确定条件下光学对地观测卫星调度问题研究[博士学位论文], 国防科技大学, 中国, 2015

    Wang Jian-Jiang. Research on the Scheduling of Optical Earth Observation Satellites under Uncertainties of Clouds [Ph. D. dissertation], National University of Defense Technology, China, 2015
    [167] 靳肖闪, 李军, 王钧, 景宁. 基于随机搜索与松弛方法的多卫星联合成像优化调度研究. 兵工学报, 2009, 30(1): 49−55 doi:  10.3321/j.issn:1000-1093.2009.01.010

    Jin Xiao-Shan, Li Jun, Wang Jun, Jing Ning. Research on optimizing scheduling of multi-satellite joint imaging based on stochastic search and relaxation methods. Acta Armamentarii, 2009, 30(1): 49−55 doi:  10.3321/j.issn:1000-1093.2009.01.010
    [168] Bellman R, Kalaba R. Dynamic Programming and Modern Control Theory. New York, USA: Academic Press, 1966. 1−112
    [169] 白保存, 贺仁杰, 李菊芳, 陈英武. 卫星单轨任务合成观测问题及其动态规划算法. 系统工程与电子技术, 2009, 31(7): 1738−1742 doi:  10.3321/j.issn:1001-506X.2009.07.046

    Bai Bao-Cun, He Ren-Jie, Li Ju-Fang, Chen Ying-Wu. Satellite orbit task merging problem and its dynamic programming algorithm. Systems Engineering and Electronics, 2009, 31(7): 1738−1742 doi:  10.3321/j.issn:1001-506X.2009.07.046
    [170] Damiani S, Verfaillie G, Charmeau M C. A continuous anytime planning module for an autonomous earth watching satellite. In: Proceedings of the 15th International Conference on Automated Planning and Scheduling. California, USA: AAAI, 2005. 19−28
    [171] 刘洋, 陈英武, 谭跃进. 卫星地面站系统任务调度的动态规划方法. 中国空间科学技术, 2005, 25(1): 44−47 doi:  10.3321/j.issn:1000-758X.2005.01.008

    Liu Yang, Chen Ying-Wu, Tan Yue-Jin. The method of mission planning of the ground station of satellite based on dynamic programming. Chinese Space Science and Technology, 2005, 25(1): 44−47 doi:  10.3321/j.issn:1000-758X.2005.01.008
    [172] 秦丽, 张箐. 基于动态规划的遥感卫星数据分发策略研究. 遥感信息, 2016, 31(5): 30−35 doi:  10.3969/j.issn.1000-3177.2016.05.005

    Qin Li, Zhang Jing. Distribution strategy of satellite remote sensing data based on dynamic programming. Remote Sensing Information, 2016, 31(5): 30−35 doi:  10.3969/j.issn.1000-3177.2016.05.005
    [173] Holland J H. Adaptation in Natural and Artificial Systems to Biology, Control, and Artificial Intelligence. Ann Arbor, USA: University of Michigan Press, 1975. 20−31
    [174] 周毅荣, 陈浩, 李龙梅, 陈荦, 景宁. 一种基于免疫遗传的卫星数传调度方法. 小型微型计算机系统, 2015, 36(12): 2725−2729 doi:  10.3969/j.issn.1000-1220.2015.12.020

    Zhou Yi-Rong, Chen Hao, Li Long-Mei, Chen Luo, Jing Ning. Immune genetic algorithm for satellite data transmission scheduling. Journal of Chinese Computer Systems, 2015, 36(12): 2725−2729 doi:  10.3969/j.issn.1000-1220.2015.12.020
    [175] Chen H, Zhou Y, Du C, Li J. A satellite cluster data transmission scheduling method based on genetic algorithm with rote learning operator. In: Proceedings of the IEEE 2016 Congress on Evolutionary Computation. Vancouver, Canada: IEEE, 2016. 5076−5083
    [176] 李云峰, 武小悦. 遗传算法在卫星数传调度问题中的应用. 系统工程理论与实践, 2008, 28(1): 124−131 doi:  10.3321/j.issn:1000-6788.2008.01.018

    Li Yun-Feng, Wu Xiao-Yue. Application of genetic algorithm in satellite data transmission scheduling problem. Systems Engineering-Theory & Practice, 2008, 28(1): 124−131 doi:  10.3321/j.issn:1000-6788.2008.01.018
    [177] 韩传奇, 刘玉荣, 李虎. 基于改进遗传算法对小卫星星群任务规划研究. 空间科学学报, 2019, 39(1): 129−134 doi:  10.11728/cjss2019.01.129

    Han Chuan-Qi, Liu Yu-Rong, Li Hu. Mission planning for small satellite constellations based on improved genetic algorithm. Chinese Journal of Space Science, 2019, 39(1): 129−134 doi:  10.11728/cjss2019.01.129
    [178] 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. International Journal of Disaster Risk Reduction, 2018, 28: 813−825 doi:  10.1016/j.ijdrr.2018.02.013
    [179] Hosseinabadi S, Ranjbar M, Ramyar S, Amel-Monirian M. Scheduling a constellation of agile earth observation satellites with preemption. Journal of Quality Engineering and Production Optimization, 2017, 2(1): 47−64
    [180] Du Y H, Xing L N, Zhang J W, Chen Y G, He Y M. MOEA based memetic algorithms for multi-objective satellite range scheduling problem. Swarm and Evolutionary Computation, 2019, 50: 100576 doi:  10.1016/j.swevo.2019.100576
    [181] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. In: Proceedings of the 1st European Conference on Artificial Life. London, England: The MIT Press, 1991. 134−142
    [182] 邱涤珊, 郭浩, 贺川, 伍国华. 敏捷成像卫星多星密集任务调度方法. 航空学报, 2013, 34(4): 882−889

    Qiu Di-Shan, Guo Hao, He Chuan, Wu Guo-Hua. Intensive task scheduling method for multi-agile imaging satellites. Acta Aeronautica et Astronautica Sinica, 2013, 34(4): 882−889
    [183] 耿远卓, 郭延宁, 李传江, 马广富, 李文博. 敏捷凝视卫星密集点目标聚类与最优观测规划. 控制与决策, 2020, 35(3): 613−621

    Geng Yuan-Zhuo, Guo Yan-Ning, Li Chuan-Jiang, Ma Guang-Fu, Li Wen-Bo. Optimal mission planning with task clustering for intensive point targets observation of staring mode agile satellite. Control and Decision, 2020, 35(3): 613−621
    [184] 严珍珍, 陈英武, 邢立宁. 基于改进蚁群算法设计的敏捷卫星调度方法. 系统工程理论与实践, 2014, 34(3): 793−801 doi:  10.12011/1000-6788(2014)3-793

    Yan Zhen-Zhen, Chen Ying-Wu, Xing Li-Ning. Agile satellite scheduling based on improved ant colony algorithm. Systems Engineering-Theory & Practice, 2014, 34(3): 793−801 doi:  10.12011/1000-6788(2014)3-793
    [185] 陈宇宁, 邢立宁, 陈英武. 基于蚁群算法的灵巧卫星调度. 科学技术与工程, 2011, 11(3): 484−489, 502 doi:  10.3969/j.issn.1671-1815.2011.03.012

    Chen Yu-Ning, Xing Li-Ning, Chen Ying-Wu. Scheduling of agile satellites based on ant colony algorithm. Science Technology and Engineering, 2011, 11(3): 484−489, 502 doi:  10.3969/j.issn.1671-1815.2011.03.012
    [186] 朱新新, 谭跃进, 邓宏钟, 邢立宁. 求解成像卫星调度问题的改进蚁群算法. 科学技术与工程, 2012, 12(31): 8322−8326 doi:  10.3969/j.issn.1671-1815.2012.31.037

    Zhu Xin-Xin, Tan Yue-Jin, Deng Hong-Zhong, Xing Li-Ning. The improved ant colony algorithm solving the scheduling problem of imaging satellites. Science Technology and Engineering, 2012, 12(31): 8322−8326 doi:  10.3969/j.issn.1671-1815.2012.31.037
    [187] Gao K B, Wu G H, Zhu J H. Multi-satellite observation scheduling based on a hybrid ant colony optimization. Advanced Materials Research, 2013, 765-767: 532−536 doi:  10.4028/www.scientific.net/AMR.765-767.532
    [188] Wu G H, Ma M H, Zhu J H, Qiu D S. 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
    [189] 邢立宁, 陈英武. 基于混合蚁群优化的卫星地面站系统任务调度方法. 自动化学报, 2008, 34(4): 414−418

    Xing Li-Ning, Chen Ying-Wu. Mission planning of satellite ground station system based on the hybrid ant colony optimization. Acta Automatica Sinica, 2008, 34(4): 414−418
    [190] 姚锋, 邢立宁. 求解卫星地面站调度问题的演化学习型蚁群算法. 系统工程与电子技术, 2012, 34(11): 2270−2274 doi:  10.3969/j.issn.1001-506X.2012.11.14

    Yao Feng, Xing Li-Ning. Learnable ant colony optimization algorithm for solving satellite ground station scheduling problems. Systems Engineering and Electronics, 2012, 34(11): 2270−2274 doi:  10.3969/j.issn.1001-506X.2012.11.14
    [191] 黄双临, 马冬青, 方冬梅, 崔涛. 基于改进蚁群算法的卫星数传调度. 无线电工程, 2015, 45(7): 27−30, 58 doi:  10.3969/j.issn.1003-3106.2015.07.08

    Huang Shuang-Lin, Ma Dong-Qing, Fang Dong-Mei, Cui Tao. Satellite data transmission scheduling based on improved ant colony system. Radio Engineering, 2015, 45(7): 27−30, 58 doi:  10.3969/j.issn.1003-3106.2015.07.08
    [192] Li Z X, Li J, Mu W T. Space-ground TT&C resources integrated scheduling based on the hybrid ant colony optimization. In: Proceedings of the 28th Conference of Spacecraft TT&C Technology. Singapore, Singapore: Springer, 2016. 179−196
    [193] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia: IEEE, 1995. 1942−1948
    [194] Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation. Orlando, USA: IEEE, 1997. 4104−4108
    [195] 汤绍勋, 易先清, 罗雪山. 面向预警卫星调度问题的改进粒子群算法. 系统工程, 2012, 30(1): 116−121

    Tang Shao-Xun, Yi Xian-Qing, Luo Xue-Shan. An improved particle swarm optimization algorithm for early warning satellites scheduling problems. Systems Engineering, 2012, 30(1): 116−121
    [196] 常飞, 武小悦. 基于改进粒子群算法的卫星数传任务调度. 系统工程与电子技术, 2009, 31(10): 2404−2408 doi:  10.3321/j.issn:1001-506X.2009.10.028

    Chang Fei, Wu Xiao-Yue. Satellite data transmission task scheduling based on advanced particle swarm optimization. Systems Engineering and Electronics, 2009, 31(10): 2404−2408 doi:  10.3321/j.issn:1001-506X.2009.10.028
    [197] Chen H, Li L M, Zhong Z N, Li J. 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
    [198] Chen Y, Zhang D Y, Zhou M Q, Zou H. Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization. In: Proceedings of Advances in Information Technology and Industry Applications. Berlin, Germany: Springer, 2012. 441−448
    [199] 国晓博, 刘金灿, 周红彬. 分布式卫星系统数传调度研究. 无线电通信技术, 2016, 42(4): 29−32 doi:  10.3969/j.issn.1003-3114.2016.04.08

    Guo Xiao-Bo, Liu Jin-Can, Zhou Hong-Bin. Research on transmission task scheduling for distributed satellite systems. Radio Communications Technology, 2016, 42(4): 29−32 doi:  10.3969/j.issn.1003-3114.2016.04.08
    [200] 刘建银, 王忠伟. 面向森林资源观测的成像卫星任务规划算法设计. 中南林业科技大学学报, 2018, 38(10): 41−46

    Liu Jian-Yin, Wang Zhong-Wei. Research on the tasks scheduling algorithm for imaging satellite observing forest area. Journal of Central South University of Forestry & Technology, 2018, 38(10): 41−46
    [201] Glover F. Tabu search-part I. ORSA Journal on Computing, 1989, 1(3): 190−205 doi:  10.1287/ijoc.1.3.190
    [202] Glover F. Tabu search-part II. ORSA Journal on Computing, 1990, 2(1): 4−32 doi:  10.1287/ijoc.2.1.4
    [203] 贺仁杰, 谭跃进. 具有时间窗口约束的并行机床调度问题研究. 系统工程, 2004, 22(5): 18−22 doi:  10.3969/j.issn.1001-4098.2004.05.004

    He Ren-Jie, Tan Yue-Jin. On parallel machine scheduling problem with time windows. Systems Engineering, 2004, 22(5): 18−22 doi:  10.3969/j.issn.1001-4098.2004.05.004
    [204] 左春荣, 王海燕. 基于禁忌搜索算法测地卫星任务调度研究. 计算机工程与应用, 2010, 46(1): 215−217, 245 doi:  10.3778/j.issn.1002-8331.2010.01.064

    Zuo Chun-Rong, Wang Hai-Yan. Research on scheduling of earth observing satellites based on taboo search algorithm. Computer Engineering and Applications, 2010, 46(1): 215−217, 245 doi:  10.3778/j.issn.1002-8331.2010.01.064
    [205] 陈英武, 方炎申, 李菊芳, 贺仁杰. 卫星任务调度问题的约束规划模型. 国防科技大学学报, 2006, 28(5): 126−132 doi:  10.3969/j.issn.1001-2486.2006.05.026

    Chen Ying-Wu, Fang Yan-Shen, Li Ju-Fang, He Ren-Jie. Constraint programming model of satellite mission scheduling. Journal of National University of Defense Technology, 2006, 28(5): 126−132 doi:  10.3969/j.issn.1001-2486.2006.05.026
    [206] 李菊芳, 贺仁杰, 姚锋, 谭跃进. 成像卫星集成调度的变邻域禁忌搜索算法. 系统工程理论与实践, 2013, 33(12): 3040−3044 doi:  10.12011/1000-6788(2013)12-3040

    Li Ju-Fang, He Ren-Jie, Yao Feng, Tan Yue-Jin. Variable neighborhood tabu search algorithm for integrated imaging satellites scheduling problem. Systems Engineering-Theory & Practice, 2013, 33(12): 3040−3044 doi:  10.12011/1000-6788(2013)12-3040
    [207] 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
    [208] Metropolis N, Rosenbluth A W, Rosenbluth M N, Teller A H. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953, 21: 1087−1091 doi:  10.1063/1.1699114
    [209] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220: 671−680 doi:  10.1126/science.220.4598.671
    [210] 黄瀚, 张晓倩. 基于图论模型的成像卫星任务规划方法研究. 桂林航天工业学院学报, 2016, 21(2): 155−158 doi:  10.3969/j.issn.1009-1033.2016.02.005
    [211] 贺仁杰, 高鹏, 白保存, 李菊芳, 姚锋, 邢立宁. 成像卫星任务规划模型、算法及其应用. 系统工程理论与实践, 2011, 31(3): 411−422 doi:  10.12011/1000-6788(2011)3-411

    He Ren-Jie, Gao Peng, Bai Bao-Cun, Li Ju-Fang, Yao Feng, Xing Li-Ning. Models, algorithms and applications to the mission planning system of imaging satellites. Systems Engineering-Theory & Practice, 2011, 31(3): 411−422 doi:  10.12011/1000-6788(2011)3-411
    [212] Gao P, Li W, Yao F, Bai B C, Yang J. Simulated annealing algorithm for EOS scheduling problem with task merging. In: Proceedings of the International Conference on Modelling, Identification and Control. Shanghai, China: IEEE, 2011. 547−522
    [213] 徐欢, 祝江汉, 王慧林. 基于模拟退火算法的电子侦察卫星任务规划问题研究. 装备指挥技术学院学报, 2010, 21(3): 62−66

    Xu Huan, Zhu Jiang-Han, Wang Hui-Lin. Research on mission planning for electronic reconnaissance satellites based on simulated annealing. Journal of the Academy of Equipment Command & Technology, 2010, 21(3): 62−66
    [214] Du Y H, Xing L N, Chen Y G, Wang L, Ren T. Integrated agile observation satellite scheduling problem considering different memory environments: a case study. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2020, 42: 76 doi:  10.1007/s40430-019-2121-0
    [215] 黄生俊, 邢立宁, 郭波. 基于改进模拟退火的多星任务规划方法. 科学技术与工程, 2012, 12(31): 8293−8298 doi:  10.3969/j.issn.1671-1815.2012.31.031

    Huang Sheng-Jun, Xing Li-Ning, Guo Bo. Multi-satellites mission scheduling technique based on improved simulated annealing. Science Technology and Engineering, 2012, 12(31): 8293−8298 doi:  10.3969/j.issn.1671-1815.2012.31.031
    [216] Lin Z H. Mission planning for electromagnetic environment monitors satellite based on simulated annealing algorithm. In: Proceedings of the 28th Canadian Conference on Electrical and Computer Engineering. Halifax, Canada: IEEE, 2015. 530−535
    [217] 姚锋, 李菊芳, 李文, 王沛. 对地观测卫星动态能力评估系统. 火力与指挥控制, 2010, 35(12): 18−21 doi:  10.3969/j.issn.1002-0640.2010.12.006

    Yao Feng, Li Ju-Fang, Li Wen, Wang Pei. Study on dynamic capability assessment system of earth observation satellites. Fire Control & Command Control, 2010, 35(12): 18−21 doi:  10.3969/j.issn.1002-0640.2010.12.006
    [218] Moscato P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech Con-Current Computation Program 158-79, California Institute of Technology, Pasadena, USA, 1989
    [219] Dawkins R. The Selfish Gene. New York, USA: Oxford University Press, 1976. 189−201
    [220] Li J, Li J, Jing N, Hu W D, Chen H. A satellite schedulability prediction algorithm for EO SPS. Chinese Journal of Aeronautics, 2013, 26(3): 705−716 doi:  10.1016/j.cja.2013.04.058
    [221] 刘嵩, 白国庆, 陈英武. 地球观测网络成像任务可调度性预测方法. 宇航学报, 2015, 36(5): 583−588 doi:  10.3873/j.issn.1000-1328.2015.05.013

    Liu Song, Bai Guo-Qing, Chen Ying-Wu. Prediction method for imaging task schedulability of earth observation network. Journal of Astronautics, 2015, 36(5): 583−588 doi:  10.3873/j.issn.1000-1328.2015.05.013
    [222] CPLEX Optimization Studio. CPLEX User's Manual. New York, USA: IBM Corporation, 2015. 1−9
    [223] 徐忠良, 谭跃进. 面向区域目标的测绘卫星任务调度方法. 科学技术与工程, 2012, 12(28): 7303−7308, 7349 doi:  10.3969/j.issn.1671-1815.2012.28.032

    Xu Zhong-Liang, Tan Yue-Jin. Area target-oriented mission scheduling of mapping satellites. Science Technology and Engineering, 2012, 12(28): 7303−7308, 7349 doi:  10.3969/j.issn.1671-1815.2012.28.032
    [224] 王沛, 李菊芳, 谭跃进. 编队卫星对地观测调度问题模型比较研究. 系统工程与电子技术, 2010, 32(8): 1689−1694 doi:  10.3969/j.issn.1001-506X.2010.08.29

    Wang Pei, Li Ju-Fang, Tan Yue-Jin. Comparison of earth observation scheduling model for satellite formation. Systems Engineering and Electronics, 2010, 32(8): 1689−1694 doi:  10.3969/j.issn.1001-506X.2010.08.29
    [225] Orbit Logic. STK Scheduler [Online], available: http://www.orbitlogic.com/stk-scheduler.html, May 1, 2019
    [226] 李英先, 刘扬, 方青. 基于STK/Schedule实现中继卫星业务调度. 现代电子技术, 2012, 35(10): 122−125 doi:  10.3969/j.issn.1004-373X.2012.10.039

    Li Ying-Xian, Liu Yang, Fang Qing. Realization of TDRSS mission scheduling based on STK/Schedule. Modern Electronics Technique, 2012, 35(10): 122−125 doi:  10.3969/j.issn.1004-373X.2012.10.039
    [227] 李云峰, 武小悦. STK/Scheduler在卫星数传调度中的应用研究. 计算机仿真, 2008, 25(3): 70−74 doi:  10.3969/j.issn.1006-9348.2008.03.019

    Li Yun-Feng, Wu Xiao-Yue. Application of STK/Scheduler in satellite data transmission scheduling. Computer Simulation, 2008, 25(3): 70−74 doi:  10.3969/j.issn.1006-9348.2008.03.019
    [228] 白敬培, 阎慧, 高永明, 王忠敏. 基于STK/Scheduler的航天任务调度应用研究. 装备指挥技术学院学报, 2010, 21(3): 71−75

    Bai Jing-Pei, Yan Hui, Gao Yong-Ming, Wang Zhong-Min. Application of space mission scheduling based on STK/Scheduler. Journal of the Academy of Equipment Command & Technology, 2010, 21(3): 71−75
    [229] Li Y X, Fang Q, Tan J B. Application of relay satellite scheduling based on STK/X. In: Proceedings of the 2011 IEEE CIE International Conference on Radar. Chengdu, China: IEEE, 2011. 288−291
    [230] Fisher W A, Herz E. A flexible architecture for creating scheduling algorithms as used in STK Scheduler. In: Proceedings of the 8th International Workshop on Planning and Scheduling for Space. California, USA: AAAI, 2013
    [231] Herz A F, Stoner F, Hall R, Fisher W. SSA sensor tasking approach for improved orbit determination accuracies and more efficient use of ground assets. In: Proceedings of the Advanced Maui Optical and Space Surveillance Technologies Conference. Hawaii, USA: The Maui Economic Development Board, 2013
    [232] NASA. EUROPA-2.6 [Online], available: https://github.com/nasa/europa/tree/Releases/EUROPA-2.6, May 1, 2019
    [233] Muscettola N, Nayak P P, Pell B, Williams B C. Remote agent: to boldly go where no AI system has gone before. Artificial Intelligence, 1998, 103(1-2): 5−47 doi:  10.1016/S0004-3702(98)00068-X
    [234] Tran D, Chien S, Sherwood R, Castano R, Cichy B, Davies A, et al. The autonomous sciencecraft experiment onboard the EO-1 spacecraft. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA: ACM, 2005. 163−164
    [235] Chien S, Sherwood R, Rabideau G, Castano R, Davies A, Burl M, et al. The Techsat-21 autonomous space science agent. In: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA: ACM, 2002. 570−577
    [236] Frank J, Jonsson A, Morris R, Smith D E, Norvig P. Planning and scheduling for fleets of earth observing satellites. In: Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics and Automation for Space. Montreal, Canada: Canadian Space Agency, 2001
    [237] Bedrax-Weiss T, Frank J, Jonsson A, McGann C. Europa 2: Plan database services for planning and scheduling applications. In: Proceedings of the 14th International Conference on Automated Planning and Scheduling, California, USA: AAAI, 2004
    [238] 刘越畅, 钟秀玉, 房宜汕, 陈剑彪. 基于Europa2的智能规划动态仿真与建模. 计算机工程与应用, 2012, 48(17): 211−214, 219 doi:  10.3778/j.issn.1002-8331.2012.17.042

    Liu Yue-Chang, Zhong Xiu-Yu, Fang Yi-Shan, Chen Jian-Biao. Dynamic simulation and modeling for AI planning based on Europa. Computer Engineering and Applications, 2012, 48(17): 211−214, 219 doi:  10.3778/j.issn.1002-8331.2012.17.042
    [239] NASA. Scheduling and planning interface for exploration [Online], available: https://github.com/nasa/OpenSPIFe, May 1, 2019
  • [1] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述[J]. 自动化学报, doi: 10.16383/j.aas.c170681
    [2] 向尚, 陈盈果, 李国梁, 邢立宁. 卫星自主与协同任务调度规划综述[J]. 自动化学报, doi: 10.16383/j.aas.c180068
    [3] 王大轶, 屠园园, 刘成瑞, 何英姿, 李文博. 航天器控制系统可重构性的内涵与研究综述[J]. 自动化学报, doi: 10.16383/j.aas.2017.c160700
    [4] 曾奎, 耿云海, 陈炳龙. 基于傅里叶级数的小推力航天器快速轨迹设计[J]. 自动化学报, doi: 10.16383/j.aas.2016.c150859
    [5] 段文杰, 王大轶, 刘成瑞. 一种线性系统可重构控制分析方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.02726
    [6] 黄静, 李传江, 马广富, 刘刚. 基于广义逆的欠驱动航天器姿态机动控制[J]. 自动化学报, doi: 10.3724/SP.J.1004.2013.00285
    [7] 王小乐, 黄宏斌, 邓苏. 处理顺序约束的信息物理融合系统静态任务表调度算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2012.01870
    [8] 唐立新, 赵任. 强化Dynasearch & TS算法求解酸轧生产调度问题[J]. 自动化学报, doi: 10.3724/SP.J.1004.2010.00304
    [9] 张长胜, 孙吉贵, 杨轻云, 郑黎辉. 一种求解车间调度的混合算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00332
    [10] 吴启迪, 乔非, 李莉, 吴莹. 基于数据的复杂制造过程调度[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.00807
    [11] 王素欣, 高利, 崔小光, 曹宏美. 多需求点车辆调度模型及其群体智能混合求解[J]. 自动化学报, doi: 10.3724/SP.J.1004.2008.00102
    [12] 邢立宁, 陈英武. 基于混合蚁群优化的卫星地面站系统任务调度方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2008.00414
    [13] 赵君, 刘全利, 王伟. 冷轧生产调度模型及算法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2008.00565
    [14] 张居阳, 孙吉贵, 杨轻云. 半在线调度中约束求解算法研究[J]. 自动化学报, doi: 10.1360/aas-007-0765
    [15] 杜晓丽, 王俊丽, 蒋昌俊. 异构环境下基于松弛标记法的任务调度[J]. 自动化学报, doi: 10.1360/aas-007-0615
    [16] 支青, 蒋昌俊. 一种适于异构环境的任务调度算法[J]. 自动化学报
    [17] 杨根科, 吴智铭, 陈贇. 减链约束多处理器任务在三处理器中的调度[J]. 自动化学报
    [18] 李智斌, 吴宏鑫, 解永春, 王晓磊, 于志杰, 王颖. 航天器智能控制实验平台[J]. 自动化学报
    [19] 康一梅, 郑应平. 同等并行处理机上独立任务的调度[J]. 自动化学报
    [20] 汪时萍, 仲伟俊, 夏安邦. 积木模型生成技术及其在城市供水调度中的应用[J]. 自动化学报
  • 加载中
计量
  • 文章访问数:  6
  • HTML全文浏览量:  5
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-14
  • 录用日期:  2020-04-06

航天器任务调度模型、算法与通用求解技术综述

doi: 10.16383/j.aas.c190656
    基金项目:  国家自然科学基金(61773120, 61873328), 国家杰出青年科学基金(61525304), 高等学校全国优秀博士学位论文作者专项资金(2014-92), 国家建设高水平大学公派研究生项目(201903170181), 湖南省研究生科研创新项目(CX2018B022)资助
    作者简介:

    国防科技大学系统工程学院博士研究生. 2017年获国防科技大学硕士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: duyonghao15@163.com

    国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009 年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. 本文通讯作者. E-mail: xinglining@gmail.com

    国防科技大学系统工程学院研究员. 2013年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: yaofeng@nudt.edu.cn

    国防科技大学系统工程学院副教授. 2014年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. E-mail: argguo@163.com

    通讯作者: 国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009 年获国防科技大学博士学位. 主要研究方向为智能优化理论、方法与应用. 本文通讯作者. E-mail: xinglining@gmail.com

摘要: 针对航天器任务调度大规模、复杂化的新常态和灵活组网、快速响应的新要求, 综述了航天器任务调度模型、算法与通用求解技术的发展现状. 首先, 基于遥感卫星、通讯中继卫星、导航卫星和航天测控等航天器任务, 从任务排序模型和时间窗口分配模型两个角度出发, 揭示了不同航天器任务调度模型的决策形式和共性特征, 阐明提升模型兼容性、适用性的必要性. 其次, 基于启发式算法、精确求解算法和元启发式算法, 探讨了航天器任务调度算法的适用模型与编码特色, 指明“算法-模型”解耦、算法深度融合的重要性. 在此基础上, 介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等航天器任务调度通用求解技术的模型、算法与主要功能, 说明我国自主研发通用求解技术的必要性和新的应用思路. 最后, 指出了开发航天器任务调度统一化建模语言、打造算法库与测试集等未来航天器任务调度研究的新方向.

English Abstract

杜永浩, 邢立宁, 姚锋, 陈盈果. 航天器任务调度模型、算法与通用求解技术综述. 自动化学报, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
引用本文: 杜永浩, 邢立宁, 姚锋, 陈盈果. 航天器任务调度模型、算法与通用求解技术综述. 自动化学报, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
Du Yong-Hao, Xing Li-Ning, Yao Feng, Chen Ying-Guo. survey on models, algorithms and general techniques for spacecraft mission scheduling. Acta Automatica Sinica, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
Citation: Du Yong-Hao, Xing Li-Ning, Yao Feng, Chen Ying-Guo. survey on models, algorithms and general techniques for spacecraft mission scheduling. Acta Automatica Sinica, 2020, 46(x): 1−27. doi: 10.16383/j.aas.c190656
  • 21世纪以来, 我国航天事业步入快速发展时期. 随着“高分辨率对地观测系统”“北斗卫星导航定位系统”等国家重大专项的相继开展, 以及商业航天产业的蓬勃发展, 我国在轨航天器规模持续增加, 总数位居世界第二. 在此期间, 各类航天器平台与载荷能力也经历了深刻变革. 为适应大规模、复杂化的航天器管控新常态, 融合现代运筹学、计算科学与相关领域知识的航天器任务调度技术起到了举足轻重的作用.

    航天器任务调度技术是指在航天器使命任务与管控需求的驱动下, 通过对任务与资源的建模, 消解航天器任务执行过程中的约束冲突, 最大化航天器任务与管控效益的一种优化技术. 在诸多学者与航天从业人员的推动下, 航天器任务调度技术得到了快速的发展, 在美国DigitalGlobe高分辨率对地观测系统、欧盟Galileo卫星导航系统和我国“高分”系列对地观测系统、“北斗”卫星导航系统等国内外先进的航天系统中得到了充分的实践与验证. 在此过程中, 作为调度技术的两大要素, 航天器任务调度模型与调度算法的重要性也日益凸显.

    调度模型是航天器任务调度的重要基础, 是决定问题描述方式、指导算法设计、影响问题复杂度的关键因素. 现阶段, 线性规划模型、图论模型、约束满足模型等各类调度模型已被广泛运用于航天器任务调度问题研究中. 在这些研究中, 一方面, 许多调度模型表现出鲜明的问题特色与针对性, 引入了与调度问题紧密相关的决策手段; 另一方面, 许多模型也表现出了较大的相似性, 折射出航天器任务调度问题的一些共性特征. 因此, 面对模型种类和应用场景繁多的航天器任务调度技术发展现状, 建立一个怎样的调度模型, 是决定调度问题是否可解、问题特征是否可描述、应用场景是否可拓展的重要环节.

    调度算法是航天器任务调度的优化手段, 是实现模型解算、输出调度方案、决定问题求解质量的关键因素. 在航天器规模增长与能力发展的趋势下, 启发式算法、精确求解算法和元启发式算法等一系列形式各异的调度算法被应用于航天器任务调度问题的求解中. 这些调度算法表现出良好的优化效果, 但往往也暴露出与调度模型或应用场景紧耦合的编码方式或设计思想, 导致许多优秀的航天器任务调度算法在提出之后并没有得到广泛的应用或进一步的发展. 由此, 在琳琅满目的调度算法中挑选出合适的算法、设计合理的编码结构、吸纳优秀算法中的先进思想, 也是航天器任务调度技术研究发展的必然要求.

    为梳理航天器任务调度相关模型与算法、分析其特点与发展趋势, 一些综述工作相继开展[1-4]. 不过, 这些文献大多聚焦于某一类航天器(如遥感卫星)或某一种应用场景(如自主协同)的航天器任务调度模型或算法, 很少站在航天领域的全局视角, 探讨不同类型航天器任务调度模型的共性特征与区别, 分析不同调度算法的适用性与编码特点. 未来, 航天器任务调度模型必须满足复杂化、组网化的问题特点, 调度算法也需满足大规模、快速响应的优化需求, 这就要求相关从业人员对各类航天器任务调度模型与算法深刻理解与熟练运用, 摆脱“问题-模型-算法”紧耦合的传统思维. 鉴于此, 本文试图系统地梳理航天器任务调度研究中的模型与算法, 揭示调度模型的共性特征, 归纳调度算法的使用特点, 为航天器任务调度技术研究未来发展提供参考. 同时, 在二者基础上发展起来的通用求解技术是改善航天调度系统兼容性、提升综合管控水平的关键技术, 故本文也试图梳理适用于航天器任务调度的通用求解工具, 探索我国航天器任务调度通用求解技术发展的新道路.

    本文分别对航天器任务调度模型、算法和通用求解技术等三个方面进行了梳理与总结. 第1节根据航天器类型的不同, 将现阶段具有调度需求的主要航天器任务分为遥感卫星任务、通讯中继卫星任务、导航卫星任务和航天器测控任务, 分别阐述了各类航天器任务调度的常用模型及特征. 第2节根据优化原理的不同, 将航天器任务调度算法分为启发式算法、精确求解算法和元启发式算法, 重点讨论了各类算法的编码特点和优缺点. 第3节分别介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等具有通用特色的航天器任务调度工具, 并分析了其适用性与应用前景. 最后, 第4节综合研究现状, 对航天器任务调度领域未来的研究趋势进行了展望.

    • 在任务调度问题的求解过程中, 问题建模往往是首要步骤. 在航天器任务调度相关研究中, 各类航天器任务往往由不同的职能部门负责调度, 并采用不同的问题建模方式, 影响着任务与资源处理、决策变量设计和模型编码等诸多方面. 根据职能部门的不同, 可以将航天器任务分为运控任务与测控任务两大类:

      定义1 (航天器运控任务) 为实现遥感卫星、中继通讯卫星和导航卫星等航天器的使命任务和任务数据的回传, 在航天器特定工作模式和载荷的支撑下, 由所属运控部门针对任务目标或数据接收目标制定的一类专门任务.

      定义2 (航天器测控任务) 为保障航天器正常运行, 满足航天器遥测、跟踪和指令上注等日常需要, 在航天器载荷和地面管控资源的共同支撑下, 由测控部门针对航天器统一制定的一类任务.

      由此, 在上述定义的基础上, 本节梳理了遥感卫星、中继通讯卫星、导航卫星和航天器测控等常见的航天器任务调度模型, 分析了不同航天器任务调度问题的建模特色、决策变量形式和模型优缺点, 揭示不同航天器任务调度模型之间的共性特征与区别, 阐明建模过程中提升模型兼容性、适用性和求解效率等方面的必要性, 为航天器任务调度的模型研究提供参考.

    • 遥感卫星任务是指针对地表、海洋、大气和太空等环境中的目标, 通过星上遥感载荷进行信息数据收集并传输给地面设备的一类航天器运控任务. 遥感卫星是目前在轨数量最多的航天器, 在农业、经济、军事等领域发挥着不可替代作用. 因此, 遥感卫星任务也是现阶段种类最为繁多、需求量最大、应用最为广泛的一类航天器运控任务.

      遥感卫星任务调度是一类具有NP(Non-deterministic Polynomial)难特性的组合优化问题[5], 该问题往往具有序列优化与资源优化的双重特点, 既要决策任务执行的先后顺序, 又要为任务合理地分配卫星及其载荷资源. 由此, 根据调度模型中决策对象的不同, 本节将遥感卫星任务调度模型分为面向资源的任务排序模型(简称任务排序模型)和面向任务的资源分配模型(简称资源分配模型)两大类, 并基于此对遥感卫星任务调度模型展开进一步的阐述.

    • 20世纪末, 面对遥感卫星任务调度这一全新的问题, 人们尝试从经典运筹学模型中寻找解决方案. 在这些模型中, 决策变量主要表示资源执行任务的先后顺序, 反映任务连续执行过程中的时序逻辑和能力约束, 对早期遥感卫星任务调度问题的求解起到重要帮助.

      (1) 车辆路径规划模型

      车辆路径规划(Vehicle Routing Problem, VRP)模型是最早用于遥感卫星任务调度问题求解的模型之一, 其中卫星被视为车辆, 任务目标被视为车辆访问的城市, 如图1(a). Cordeau等[6]将遥感卫星对目标的可见性转化为任务的时间窗口约束, 并采用了一种VRP求解算法[7]解决了单轨遥感卫星任务调度问题. 随后, Bianchessi等[8]将该算法应用于多星多轨的任务调度场景中. 李菊芳等[9]、郭玉华等[10]和蔡德荣[11]指出卫星成像任务与数传任务可视为VRP模型中的装卸货动作, 求解了固存容量约束下的任务调度问题. 虽然上述研究在卫星任务、工作模式、固存约束等方面进行了诸多简化, 但VRP模型中任务排序的建模思想为卫星任务调度研究打开了新思路.

      图  1  遥感卫星任务排序模型示例. (a) 双星VRP模型. (b) 单星图论模型. (c) 基于最早开始原则的双星JSP模型

      Figure 1.  Illustrations of mission-sequencing models for remote sensing satellites. (a) A VRP model for two satellites. (b) A graph-based model for single satellite. (c) A JSP model for two satellites based on the earliest-beginning principle

      (2) 图论模型

      图1(b)所示的图论模型通过点和线的方式直观地描述卫星任务之间的时序与冲突关系, 在遥感卫星任务调度中也得到诸多应用. 例如, Gabrel等[12]、Bianchessi等[13]和陈浩等[14]将成像任务调度问题抽象为有向无圈图模型, 陈祥国等[15]通过构造任务调度位置图和任务调度关系图分别描述了数传任务的序列与执行资源. 针对多星联合调度问题, Xu等[16]建立了基于最小生成树的图论模型, 张帆等[17]和王钧[18]构建了分层优化的图论模型. 不过, 图论模型的缺陷也十分明显, 由于该模型的约束表达能力有限, 往往需要较大程度的问题简化, 诸如区域目标成像、成像数传一体化调度、固存擦除等复合任务约束很难在传统图论模型中进行表示.

      (3) 车间调度模型

      作业车间调度(Job-shop Scheduling Problem, JSP)和流水车间调度(Flow-shop Scheduling Problem, FSP)等模型中关于工件加工顺序的约束特点满足卫星区域目标成像、立体成像等实际需求, 故二者也常用于描述遥感卫星任务调度问题. 早在1994年, Hall等[19]就给出了遥感卫星任务调度的JSP模型. Cordeau等[6]、李菊芳等[9]、顾中舜等[20]和贺仁杰等[21]指出, 遥感卫星执行任务的过程可以看作为不同类型的机器(卫星、地面站)分配工序(成像任务、数传任务)的过程, 如图1(c). 此外, Xiao等[22]设计了一种两阶段式的任务调度框架, 通过FSP模型对卫星成像与数传任务进行了一体化的调度.

      上述任务排序模型便于检查相邻任务之间的转换时间约束, 贴近卫星管理的实际情况, 加之早期遥感卫星几乎均采用“顺序回放”的工作模式, 即数传顺序与成像顺序保持一致, 故诸多其他遥感卫星调度文献中也保留着该建模思想. 例如, Lemaître等[23]研究法国敏捷星座Pleiades时通过决策变量表示卫星任务的先后顺序, 并指出卫星电量与固存约束也可通过调整卫星任务顺序得以满足; Xu等[24]通过决策变量表示了任务在执行序列中的位置; Lin等[25]、程思微等[26]、任仙海等[27]、Sun等[28]和Cui等[29]均通过决策变量表示了遥感卫星任务目标之间的路径或顺序等.

      不过, 任务排序模型存在一个明显的解码过程, 通常仿照传统VRP、图论和JSP模型尽可能早地执行任务, 如图1(c). 但实际上, 该解码过程在现阶段卫星复杂的约束逻辑下(如时间依赖性约束、非线性收益等)可能会丢失优质解, 即“最优序列”不一定等于“最优结果”. 问题约束越复杂, 任务排序模型就越可能丢失优质解, 同时解码过程的时间成本也越高. 另一方面, 随着星载固存技术的发展, 诸多近年来发射的遥感卫星(如“高景一号”)已无需满足“顺序回放”的约束, 即成像序列与数传序列可以不一致. 若在数传窗口稀缺或某些任务有特殊需求的情况下, 分别优化卫星成像序列与数传序列很可能更利于任务收益的最大化. 对此, 学者们提出了面向任务的资源分配模型, 既保留了任务排序建模的思想, 同时直接决策了任务执行的具体时间, 成为各类遥感卫星任务调度研究中的重要模型.

    • 与任务排序模型相比, 资源分配模型不再决策任务顺序, 而是面向任务需求, 决策任务被执行的资源, 如图2(a). 由于卫星与任务目标的可见性是任务执行的前提, 二者的可见时间窗口(Visible Time Window, VTW)一直以来都被视为卫星调度的关键资源, 故资源分配模型又可称为VTW分配模型. 例如, Bensanna等[30]、Gabrel[31]、靳肖闪等[32]、Wang等[33]、Liu等[34]、Jiang等[35]和Wu等[36]以0-1决策变量表示了遥感卫星执行任务所选的VTW, 求解了法国SPOT、韩国SATellite-2、我国“环境”系列和中巴“资源”系列等遥感卫星成像任务调度问题. 在上述文献中, 由于0-1变量所表示的VTW同时包含了卫星载荷信息和任务执行时间, 反映了卫星执行任务的顺序, 无需VRP、JSP模型中的解码过程, 使得模型表示更加简洁.

      图  2  遥感卫星VTW分配模型示例. (a) 非敏捷卫星VTW分配模型. (b) 敏捷卫星VTW分配模型

      Figure 2.  Illustrations of VTW-allocation models for remote sensing satellites. (a) A model for non-agile satellites. (b) A model for agile satellites

      然而, 敏捷遥感卫星技术的发展也暴露出了传统VTW分配模型的局限性. 近年来发射的遥感卫星通常具备俯仰成像能力, 即能够先于或晚于目标上空进行远距离的倾斜成像, 这一技术为遥感卫星在目标上空过境时带来了更长的VTW和更多的成像机会[37], 如图2(b). 因此, 在敏捷遥感卫星任务调度模型中, 不仅需要决策任务执行的VTW, 还需要决定任务在该VTW内具体的开始时刻. 针对这一问题, 学者们通过以下三种方法对模型进行了改进:

      (1) 基于规则的VTW分配模型

      与上节任务排序模型中的解码思想相似, Lemaître等[23]、He等[38-39]、Mok等[40]、Chu等[41]和Song等[42]基于最早开始原则, 将卫星任务安排在VTW内满足约束的最早位置; 张超等[43]、Liu等[44]以成像质量优先原则安排任务, 并在模型中处理了时间依赖的姿态转换与梯段成像质量约束; Xu等[24]根据任务安排过程中可能出现的不同情况设计了专门的卫星窗口更新策略; Kim等[45]在SAR星座成像调度问题中仅考虑了侧视成像模式, 即在VTW的中点安排成像任务; Wu等[46]以合并任务优先、最早开始等原则安排成像任务, 并指出任务合并的相关约束导致了其模型非线性的特征. 不过, 虽然这些解码过程能够帮助VTW分配模型适用于敏捷遥感卫星调度问题, 但基于规则的解码方式一定程度也限制了算法对更大解空间的探索, 在复杂约束情况下的时间成本可能也较高.

      (2) 多重决策的VTW分配模型

      Lemaître等[23]、She等[47]、Chen等[48]和Frank等[49]在用0-1变量表示任务VTW的同时, 还通过一个整数变量表示了任务在VTW内的开始时刻. Sarkheyli等[50]通过双重决策变量表示了敏捷遥感卫星任务的VTW和开始时刻, 并考虑了星上固存整块擦除的业务约束, 该约束在其他研究中很少涉及; Niu等[51]、Chen等[52]也采用了相同的决策变量, 并计算了非线性的姿态转换时间约束. 在该模型中, 0-1变量决策了执行任务的卫星以及VTW, 整数变量决策了该任务的开始时间, 避免了上一种方法中基于规则的解码过程, 具有更好的模型完备性.

      (3) 离散化VTW分配模型

      Wang等[33]、Valicka等[53]、Nag等[54]、Zhu等[55]、He等[56]、Li等[57]和杜永浩等[58]将遥感卫星成像或数传任务的VTW进行离散化处理, 通过0-1变量直接决策了任务的离散VTV(即开始与结束时间), 如图3. 该方法与多重决策的VTW分配模型在本质上是相同的, 但减少了决策变量的数量, 使得模型更加简洁. 与基于规则的VTW分配模型相比, 后两种模型在解的表示过程中摆脱了启发式规则的影响, 能够保障复杂约束条件下解的多样性, 更加贴近敏捷遥感卫星管控的实际情况. 不过, 这两种模型很大程度上扩大了问题的解空间, 可能产生较多的不可行解, 求解难度随之增加, 故需要高性能优化算法的支持. 同时, VTW离散化的程度是可控的(现阶段卫星任务的最小精度通常为秒级), 故合理的VTW离散粒度也有助于提升该模型的有效性.

      图  3  敏捷遥感卫星任务离散VTW分配模型示例

      Figure 3.  An illustration of the discrete VTW-allocation model for agile remote sensing satellites

      此外, 还有学者将遥感卫星任务调度问题抽象为背包问题[6, 59-61], 但通常忽略了卫星执行任务的先后顺序, 对问题简化程度较高, 且近年来没有较大发展. 许多学者基于Multi-Agent模型[62-66]与机器学习模型[67-70]等研究了面向自主卫星的分布式协同任务调度问题, 但此类问题通常突出星上自主性和快响性特点, 不属于现阶段用户需求驱动与地面统一管控体制下的卫星日常任务调度范畴, 故本节不讨论这些模型.

    • 随着遥感卫星数量和对地观测数据量的不断提升, 地面数传站难以满足现阶段遥感星群大规模、高频率的数据传输需求. 因此, 为在轨卫星与地面站提供数据中转服务的通讯中继卫星起到了十分重要的作用. 由于在轨道上承担的使命任务与地面数传站相近, 通讯中继卫星也被称为“天基数传站”.

      通讯中继卫星的任务调度问题与遥感卫星任务调度问题中的数传调度部分在诸多方面具有很大的相似度: 1) 二者均是在VTW的基础上对目标执行数传任务, 如图4; 2) 二者在工作模式、电量、固存等方面具有相似的约束; 3) 通讯中继链路的单址链路和多址链路支持不同的链路数与频段, 这与遥感卫星不同的成像载荷具有相似的特点. 因此, 通讯中继卫星任务调度模型也可参考遥感卫星任务调度模型进行分类.

      图  4  通讯中继卫星任务调度问题与遥感卫星任务调度问题的类比. (a) 基于卫星上行链路的通讯中继任务. (b) 基于卫星下行链路的通讯中继任务

      Figure 4.  A comparison between the mission scheduling of communication relay satellites and remote sensing satellites. (a) Uplink-based missions. (b) Downlink-based missions

      (1) 任务排序模型方面

      早在1986年, Reddy等[71-72]就用点和弧分别描述通讯中继卫星任务之间的优先关系; Rojanasoonthon等[73-74]、庄树峰等[75-76]、贺川等[77]和刘润滋等[78]指出中继卫星任务调度问题可视为一类VRP问题或并行机器调度问题, 并通过决策变量反映了卫星执行任务的先后顺序; 郭超等[79]结合任务紧急程度、执行难度和VTW属性分别定义了任务的综合优先级, 并基于优先级顺序依次为任务分配VTW和开始时间. 可见, 此类模型延续了遥感卫星任务排序模型的建模特点, 在决策变量表示和解码原则等方面具有一致性.

      (2) VTW分配模型方面

      在通讯中继卫星执行任务的过程中, 往往也会出现VTW长度超过任务时长的情况, 即相关研究中提到的“滑动窗口”. 在这些研究中, 通常采用启发式规则确定任务在VTW内的开始时间. 例如, 顾中舜[80]、赵静等[81-83]通过0-1变量表示了通讯中继任务执行的VTW, 并基于优先级顺序和最早开始原则依次计算任务的开始时间; 方炎申等[84-86]在启发式规则的基础上引入了专家系统规则; 贺川等[87]以任务最小损失机会确定开始时间; 何敏藩等[88]设计了最早、最晚和随机开始策略等.

      在一些其他文献中, 通讯中继卫星的任务调度问题并不单独考虑, 例如, 在遥感卫星成像与数传一体化任务调度的研究中, Li等[57]将中继卫星视为一个地面数传站, 该处理方式也是现阶段遥感卫星调度系统中的常用方法. 此外, 中继卫星有时也承担部分航天器的测控任务, 故有相当一部分的通讯中继卫星任务被纳入航天器测控任务范畴中[89]. 可见, 通讯中继卫星常被视为一种保障其他航天器任务调度需求的通用资源. 因此, 考虑到通讯中继卫星的使命任务与管控特点, 以及其在调度模型上与其他卫星调度问题的相似性, 相关研究应侧重与其他类型卫星任务调度问题的集成性与协同性.

    • 目前, 世界上主要的导航系统包括美国全球定位系统(Global Positioning System, GPS)、欧洲“伽利略”(Galileo)导航系统、俄罗斯全球定位系统(Global Navigation Satellite System, GLONASS)和我国“北斗”导航系统. 导航卫星的运控任务主要是建立卫星与地面或与其他卫星之间通讯链路, 以保障导航系统的定位精度和授时精度, 以及导航电文、星历信息等数据的实时互传. 因此, 导航卫星任务调度问题可以看作为星地建链任务与星间建链任务的调度问题.

      (1) GPS与GLONASS导航系统

      GPS是全球最早建成的导航定位系统, 并在2005年就完成了全球范围的地面站部署, 可在任何时刻实现星地建链, 通常无需考虑VTW约束[90]. GLONASS也在俄罗斯本土与周边国家大量部署地面站[91], 卫星的可见性也较高. 由此, GPS与GLONASS系统中的星地通讯链路充裕, 对任务与资源调度的需求程度较低, 相关的公开文献较少.

      (2) Galileo导航系统

      早在1994年, Gershman等[92]和Iv等[93]就讨论了Galileo导航系统的任务调度问题. Toribio等[94]介绍了Galileo导航系统任务调度过程中的主要设备信息和组织架构, 给出了短期规划、长期规划和应急规划的概念. Hall等[95]介绍了Galileo导航系统的调度系统(Spacecraft Constellation Planning Facility, SCPF), 给出了任务调度的主要流程, 指出该系统每周约调度1500余项任务, 周计划调度时间为10分钟等. 不过, 上述研究均没有给出导航卫星任务调度的具体模型或算法. Marinelli等[96]基于离散VTW的0-1变量表示了导航任务的开始与结束时间, 对30颗Galileo导航卫星的星地建链周计划进行了调度.

      (3) “北斗”导航系统

      针对“北斗”导航系统星地建链任务调度问题, 龙运军等[97]基于0-1变量表示了执行任务的地面站及VTW, 并通过另外两个整数变量分别表示了任务的开始与结束时间, 处理了测站建链数量、天线转换时间等实际约束, 对建链时长、任务完成度等目标进行了优化. Tang等[98]通过离散VTW表示了导航任务的开始时间, 对任务完成度和负载均衡度等目标进行了优化. 考虑到任务等待时间和设备使用时间的双重时间约束, 闫俊刚等[99]将导航卫星任务调度问题抽象为带有双重VTW约束的JSP问题. 张忠山等[100]在星地建链任务的基础上还考虑星间建链任务, 给出了基于任务排序模型的两阶段式任务调度方案.

      尽管关于导航卫星任务调度的公开文献较少, 但该问题中的星地建链任务和星间建链任务, 分别与陆基航天器测控任务和天基航天器测控任务有较大的相似度. 部分研究还将导航卫星任务调度纳入航天器测控任务调度的范畴[96-98]. 因此, 下面重点介绍一些航天器测控任务调度的模型.

    • 航天器测控任务是航天器遥测、跟踪、指令上注等一系列任务的统称, 是保障航天器正常运行和长效管控的重要前提. 航天器测控任务以地基测控任务为主, 如图5(a), 也包含部分天基(基于通讯中继卫星的)测控任务, 如图5(b). 可见, 与航天器运控任务调度相似, 资源与目标的VTW也是航天器测控任务调度的关键资源, 其中低轨目标测控任务的VTW长度通常等于任务时长, 而高轨目标测控任务的VTW长度通常大于任务时长. 因此, 航天器测控任务调度问题的研究很大程度上保留了与运控任务调度相似的问题描述方式与建模习惯, 主要采用优先级排序模型、图论模型和VTW分配模型等进行相关研究.

      图  5  航天器测控任务调度示例. (a) 地基高轨、低轨航天器测控任务. (b) 天基高轨、低轨航天器测控任务

      Figure 5.  Illustrations of spacecraft tracking mission scheduling. (a) Land-based high-orbit and low-orbit tracking missions. (b) Space-based high-orbit and low-orbit tracking missions

      (1) 优先级排序模型

      优先级排序模型属于一种面向资源的任务排序模型, 其中任务的优先级指任务分配资源的优先级. 该模型与VRP等任务排序模型相似, 但不会通过决策变量指明任务资源, 而是直接根据任务排序结果依次分配资源. 例如, Parish等[101]、Barbulescu等[102-104]、郑晋军等[105]和张鹏等[106]通过0-1变量表示了一个待调度的任务序列, 并基于最早开始原则依次为任务分配VTW与开始时间, 将航天器测控任务调度问题转换为任务集的最优排序问题. Barbulescu等[107]还指出航天器测控任务调度问题可由一类带准备时间的单机调度问题归约得到, 证明了该问题的NP完全性. Li等[108]将每一个测控VTW都视为待执行的任务, 并通过0-1变量表示了待调度的任务序列. 该模型编码形式简单, 受到了诸多青睐, 但也因其只决策任务资源分配的顺序, 且完全依靠启发式规则为任务逐一分配资源与时间, 该模型在复杂的航天器测控任务调度问题中可能表现不佳.

      (2) 面向低轨航天器的图论模型

      作为另一种任务排序模型, 图论模型在航天器测控任务调度研究中也应用广泛. 早在1985年, Arbabi等[109]就给出了航天器测控任务的图论模型. Zufferey和Blöchliger等[110-111]将航天器测控任务视为图, 将测控资源描述为不同颜色, 将任务调度问题转化为图着色问题, 而其中任务开始时间也依赖于最早开始原则; 张雁等[112]、徐小辉[113]、Zhang等[114-117]和陈祥国等[118-119]以节点表示航天器VTW, 通过边表示了任务在不同VTW之间的冲突关系, 处理了任务执行唯一性和无重叠等约束, 将航天器测控任务调度问题转化为最大独立集问题; 王海波等[120]、Vázquez等[121]在航天器与测站可见关系图的基础上, 以节点表示测控任务的开始时间, 以边表示同一个测站连续执行测控任务的转换过程; Vázquez等[122-123]还给出了分布式、鲁棒性和实时调度的模型. 此外, Petri网模型也被用于航天器测控任务调度研究中[124-127]. 不过, 上述研究中通常仅考虑低轨航天器, 由于低轨航天器测控任务时长等于其VTW长度, 故任务间的资源冲突、天线仰角和转换时间约束等相对确定、易于描述. 但在高轨航天器测控任务中, VTW长度通常超过任务所需的测控时间, 故针对包含高轨航天器的测控任务调度问题, 还需更加合适的模型加以描述.

      (3) 考虑高轨航天器的VTW分配模型

      针对高、低轨航天器联合测控任务调度问题, Gooley等[128-129]建立了两阶段式的VTW分配模型, 基于0-1变量表示了测控任务的VTW, 并优先调度低轨航天器的测控任务, 再通过一个整数变量表示高轨测控任务在VTW内的开始时间; 贺仁杰等[130]、刘洋等[131]和Luo等[132]也采用同样的决策变量描述了高、低轨航天器联合测控调度问题, 建立了一体化的测控任务调度模型; Xhafa等[133-136]、Valicka等[137]通过整数变量直接表示了航天器测控任务的开始时间; Marinelli等[96]基于离散VTW和0-1变量建立了Galileo导航星座测控任务调度模型. 针对大规模测控任务调度场景, Liu等[138]基于0-1变量表示了测控任务的VTW, 并基于冲突消解规则决定任务在VTW内的开始时间. 上述VTW分配模型不仅决策了测控任务的VTW与资源, 同时也确定了任务在长VTW内的具体开始时间, 适合于包含高轨航天器的测控任务调度场景.

      此外, 还有0-1背包模型[139]、基于本体与规则库的模型[140-142]、博弈论模型[143-144]、Multi-Agent模型[145-146]和机器学习模型[147-148]等也被应用于航天器测控任务调度的研究中.

      在上述研究中, 航天器测控任务调度算例通常分为两种: 1) 基于STK的仿真算例, 任务数通常小于100, 测站数小于10; 2) 美国空军技术学院(Air Force Institute of Technology, AFIT)发布的7个高、低轨航天器联合测控任务调度标准测试集(Benchmark)[149](最近更新于2003年), 其中平均每天测控任务规模为308, 测站数为19. 考虑到任务和资源规模上的差异, 这两类算例的求解难度也截然不同. 而实际上, 我国航天测控部门现阶段面临的任务规模早已超过AFIT Benchmark的规模. 由此, 当前诸多基于小规模算例的相关研究均存在一定的局限性.

    • 本节从任务排序模型和VTW分配模型两个角度梳理了遥感卫星、通讯中继卫星、导航卫星和航天器测控任务调度研究的主要模型, 并对各类模型的特点、决策变量形式和优缺点进行了分析. 表1将上述内容进行了总结, 其中, 结合卫星型号项目研发经历, 还梳理了我国航天器任务调度实际需求中极少被相关文献考虑的业务约束. 这些约束很大程度上限制了航天器任务调度最新研究成果的转化和应用. 因此, 如何通过标准化、模块化和简洁化的方式将这些复杂的业务约束纳入航天器任务调度模型中, 应成为未来研究的重要内容之一.

      表 1  航天器任务调度模型研究现状总结

      Table 1.  A summary of the studied models for spacecraft mission scheduling

      模型类型模型子类编码过程解码过程模型优缺点常见约束极少考虑的业务约束
      面向资源的任务排序模型VRP模型决策变量表示资源执行任务的顺序规则与约束决定开始时间, 解码后为可行解1. 表示了任务顺序, 便于检查任务顺序和转换时间约束
      2. 在“顺序回放”工作机制下同时决策成像与数传序列
      3. 不便于描述长VTW的任务调度问题与复杂约束
      4. “最优序列”不一定等于“最优结果”, 约束越复杂, 解码过程越可能丢失优质解, 解码的时间成本也越高
      1. 任务执行唯一性约束
      2. 任务可见性约束(即时、空、频域VTW)
      3. 任务顺序约束(如条带拼接、立体成像、顺序回放等)
      4. 任务工作模式约束(如遥感卫星记录、回放、实传模式与录放比约束)
      5. 资源能力约束(如卫星电池、固存容量、任务次数; 测控与数传站负载、工作频率、时长约束等)
      6. 资源转换时间约束
      7. 资源可抢占性与非抢占性约束(如测控任务相控阵等待期可执行其他任务)
      1. 非线性、函数化、过程依赖的资源能力、转换时间约束(如遥感卫星单轨成像时限与该轨侧摆次数、最小摆角、是否实传等相关)
      2. 区分连续、非连续任务的资源能力、转换时间约束(如“高景一号”单轨连续成像次数、时间限制)
      3. 区分阳照条件的资源能力、转换时间约束(如地影区中继卫星工作时限)
      4. 区分待机、工作等的资源能力、转换时间约束(如载荷开关机、执行任务时限)
      5. 单载荷资源模式切换约束(如“北斗”地面站时间同步与数据传输模式的切换)
      6. 多载荷资源模式切换约束(如“资源一号”可见光与高光谱模式的切换)
      7. 遥感卫星基于“整块擦除”的固存管理约束
      图论模型
      JSP模型
      优先级排序模型通过决策变量表示任务分配资源的顺序
      面向任务的VTW分配模型基于规则的分配模型通过0-1变量表示任务的VTW基于规则与约束决定开始时间, 解码后为可行解1. 直接表达了任务VTW和开始时间, 反映了任务顺序
      2. 不限于“顺序回放”, 可分别调度成像与数传序列
      3. 能够描述长VTW的任务调度问题与复杂约束
      4. 基于规则的分配模型解空间较小, 但也存在解码过程
      5. 多重决策和离散VTW分配模型更加完备, 提升了解的多样性, 但解空间较大
      多重决策的分配模型通过0-1变量和整数变量分别表示VTW与开始时间不检查约束, 解码后可能为不可行解
      离散化VTW分配模型通过0-1变量直接表示离散VTW及开始时间

      表1中不难发现, 遥感卫星、通讯中继卫星、导航卫星和航天器测控任务调度研究中的常用模型具有非常大的相似性, 其本质上是因为上述航天器任务调度问题的相似性. 尽管航天器会搭载不同的载荷、被赋予不同的任务, 但任务与资源在时、空、频域的可见性始终是问题建模的出发点和落脚点. 以遥感卫星为例, 调度模型中主要参数的实例化关系可由图6表示, 其中资源类包含了载荷、平台等实际资源和VTW等抽象资源, 任务类包含了属性和决策变量等. 基于任务与资源的可见性, 任务类中的开始时间可与VTW直接关联, 形成贯通模型的信息流, 还原航天器任务调度问题的本来特点. 由此, 围绕“任务-资源”可见性这一共性特征, 上述航天器任务调度问题具有统一化描述与建模的可行性[58].

      图  6  航天器任务调度模型主要参数关系的一种类图表示(以遥感卫星为例)

      Figure 6.  A class diagram of the relationships among the parameters in spacecraft mission scheduling (exampled by remote sensing satellites)

      不过, 由于任务使命与资源的差异, 上述航天器任务调度问题也存在着诸多不同, 包括: 1) 固存约束差异, 遥感卫星、通讯中继卫星通常需要重点考虑固存约束, 而导航卫星任务中的数据量较小、航天器测控任务中的数据传输通常使用备用固存或无需数传, 故一般不考虑固存约束; 2) 阳照约束差异, 可见光、高光谱和近红外等光学遥感卫星任务通常对任务的阳照性有要求, 而导航卫星、测控任务通常对阳照性没有要求; 3) 资源能力约束差异, 在遥感卫星任务中, 出于对卫星的保护, 通常设置一些复杂的业务约束, 限制了卫星资源执行任务的能力; 而导航卫星、航天器测控等任务主要依靠地面资源, 故资源能力约束通常较少. 4) 任务时长差异, 遥感卫星、通讯中继卫星和航天器测控任务时长通常为定值, 而导航卫星的任务时长常为变量. 上述约束差异是反映航天器任务调度问题特征、区别航天器任务调度类型的主要因素.

    • 综上, 在分析各类航天器任务调度模型共性特征与区别的基础上, 本节总结了现有研究存在的三个方面的不足并给出对策:

      (1) 不同类型的航天器任务调度问题模型相似却又不兼容, 缺乏统一的建模理论与建模语言.

      通过本节的分析发现, 各类航天器任务调度模型具有很大的相似性, 其围绕任务与资源在时、空、频域可见性的建模原则是统一的. 然而, 这些模型又因应用场景的约束特点、需求种类和求解习惯等存在一定差异. 因此, 设计通用化、统一化的航天器任务调度建模方法与建模语言, 是研究航天器通用建模与求解技术, 满足未来不同类型、不同约束和不同体制下航天器综合管控需求的重要途径.

      (2) 诸多航天器任务调度问题简化程度高, 缺乏部署航天业务管控系统的实际应用价值.

      表1列举了诸多相关研究中极少考虑的实际约束. 虽然一定程度的问题简化能够缩减问题规模、提升求解效率, 但有些简化(如不考虑固存擦除)已影响问题的建模方式和调度方案的可用性, 导致研究成果无法转化并应用于实际航天管控系统中. 因此, 梳理各类航天器任务调度问题中关键约束、通用约束以及特色约束, 尽可能在调度模型中还原各类航天器业务管理的真实需求, 是保障相关技术实用性价值的重要前提.

      (3) 在模型层面降低航天器任务调度问题规模、提升问题求解效率的有效机制没有得到重视.

      一直以来, 调度算法是航天器任务调度问题中主要研究的对象, 而调度模型受到的重视程度远远不足. 实际上, 调度模型很大程度上决定了调度算法的编码形式、邻域结构、搜索空间等影响优化效率的关键因素. 因此, 在未来航天器任务调度问题研究中, 设计科学的调度模型和建模策略, 是缩减问题规模、降低算法编码复杂度、提升算法求解效率、促进模型与算法解耦的必然要求.

    • 在航天器任务调度模型的基础上, 任务调度算法起到模型解算、收益优化和方案输出的作用, 是实例化问题模型、决定模型求解质量的关键环节. 启发式算法、精确求解算法和元启发式算法是三类常用的调度算法, 在航天器任务调度领域得到了诸多应用. 实践表明, 这三类算法通常具有独特的性能优势, 例如, 启发式算法可以快速构造高质量的初始解, 精确求解算法能够给出特定场景下的最优解, 元启发式算法具有良好的复杂解空间寻优能力以及与前两种算法的兼容性等. 同时, 上述算法也往往与航天器任务调度的模型紧密相关, 存在适用性、可拓展性不足等现实问题, 亟待更多的发展和实践的检验.

      因此, 本节从启发式算法、精确求解算法和元启发式算法等三个方面总结航天器任务调度研究中的常用算法, 探讨不同算法的编码形式、邻域结构、辅助策略和优缺点, 阐明上述调度算法的适用模型, 指出算法与模型解耦、算法深度融合等方面的必要性, 为航天器任务调度的算法研究提供参考.

    • (1) 优先级排序算法

      优先级排序算法是在优先级排序模型的基础上, 基于优先级顺序和其他规则为任务序列分配资源与时间的算法. 该算法具有通俗易懂、结构简单、运算速度快等优点, 符合人的主观经验, 是航天器任务调度研究与实际调度系统中的常用算法.

      这些优先级排序算法中的排序规则通常是以任务优先级顺序[81-82, 105-106]为主, 也包含一些与VTW时间、长度、数量等属性有关的组合优先级顺序[79-80]; 常用的资源分配规则包括最早开始原则[23, 39-40, 46, 110-111]、最晚开始原则[88]、最大成像质量原则[43-44, 150]和最小可能冲突原则等[138]. 由于此类算法往往与排序模型紧耦合, 相关内容已于上文介绍, 且算法原理相对简单, 故不再讨论.

      (2) 冲突消解算法

      冲突消解(Conflict-avoidance或De-conflicting) 算法是指通过分析任务之间、任务与资源之间的可能冲突, 在任务调度的过程中降低冲突程度、提供冲突解决方案的一类方法.

      在遥感卫星任务调度应用方面, 刘晓娣等[151]在任务排序模型的基础上分别设计了基于成像概率和非互斥链的冲突消解算法; 冉承新等[152]在调度的过程中引入了冲突判断与冲突度评估策略, 作为遗传算法交叉与变异操作的先验知识; 刘彬彬等[153]通过对卫星成像任务持续时间进行压缩, 实现了部分约束的冲突消解; Chen等[52]以最小化冲突的方式完成了初始任务序列的构造, 并在迭代优化的过程中也引入了该冲突消解机制.

      在航天器测控任务调度应用方面, 金光等[154]基于最小冲突原则设计了任务资源的分配算法; 杨萍等[155]计算了航天器测控任务的可能冲突集并设计了基于冲突的回调算法, 实现了在资源分配过程中的“回溯”机制; Tsatsoulis等[156]给出了基于案例、规则和迭代等多种冲突消解机制; Luo等[132]计算了航天器测控任务的不可消解冲突集, 进而设计了航天器测控任务预调度算法和重调度算法, 取得了目前AFIT Benchmark中的最佳结果.

      此外, 图论模型中边的构造通常也蕴含着冲突识别与消解的思维. 可见, 冲突消解算法在诸多航天器任务调度研究中表现出快速、有效的优化特点, 但很少直接作为任务调度问题的求解算法, 大部分情况下用于生成调度初始解或辅助其他优化算法. 此外, 冲突消解算法大多围绕任务与VTW的约束关系, 不同算法之间的冲突消解原理、方法较为相似, 且与问题约束紧耦合, 在算法理论方面难有突破.

      (3) 任务分配算法

      任务分配算法是针对航天器任务调度规模较大、优化效率偏低的问题, 依据某种经验或规则对航天器任务进行预分配的算法. 与冲突消解算法一样, 任务分配算法通常也作为调度过程中的辅助算法. 任务分配算法有助于缓解航天器任务调度问题中的“组合爆炸”现象, 对缩减任务调度解空间、提升优化效率有着重要作用.

      以遥感卫星任务调度应用场景为例, Lemaître等[157]设计了遥感卫星任务公平分配原则, 基于任务权重、卫星能力等将任务均匀地分配给不同的卫星; Xu等[24]、Wang等[33]计算了任务之间VTW重叠度, 并将任务分配给VTW重叠度最低的卫星; Du等[158]通过VTW重叠度、任务优先级等多种任务特征评估、预测了任务被卫星执行的可能性, 并将任务分配给执行可能性最高的卫星; 周军升[159]在任务分配过程中引入了合同网的“ 招标、投标、评标”机制, 提升了任务分配的可靠性; 邱涤珊等[160]、孙凯等[161]将任务调度问题分解为任务分配和任务合成两个子问题; He等[56]设计了一种包含反馈机制的任务分配与调度框架, 实现了任务调度进程中对未调度任务的重新分配, 在大规模敏捷卫星任务调度场景中取得出色的优化效果.

      上述启发式算法均有效降低了问题的决策维度和求解难度, 但其应用效果很大程度上也取决于算法设计的合理程度, 且大多与问题场景、任务与资源特征紧耦合, 对问题的适应性不足. 对此, 充分利用航天器任务调度场景的特征和经验, 设计通用化、自适应的启发式算法, 是解决新常态下大规模、复杂化航天器任务调度问题的必要途径.

    • 精确求解算法能够在小规模的航天器任务调度问题中求得全局最优解, 在动态或不确定的环境中也能保证解的全局最优性. 虽然精确求解算法一般很难在有限的时间内求解大规模、复杂约束的航天器任务调度问题, 但其中诸多思想对问题建模、解空间优化等方面也具有指导意义, 故本节简要介绍相关研究中常用的两种精确求解算法.

      (1) 分支定界算法

      分支定界(Branch and Bound, B&B)算法是由Land等[162]于1960年提出, 并由Little等[163]于1963年正式命名的一种精确求解算法. B&B算法通过分支、剪支和定界等手段缩小解空间, 再通过各个分支搜寻最优解, 是现阶段求解整数线性规划问题最常用的算法之一. 由于航天器任务调度问题常被简化为线性规划问题, 故B&B算法在该领域也得到了诸多应用[22, 41, 48, 53]. 同时, 为改善在大规模任务调度问题中的求解效率, B&B算法也常与列生成法[8, 33, 164]、割平面法[165-166]和Lagrangian松弛法[25, 96, 167]等共同用于航天器任务调度的问题求解或边界求解中. 此外, B&B算法通常能够利用数学规划求解器CPLEX完成设计、改进和问题求解工作, CPLEX中的诸多剪支、松弛策略对航天领域的B&B算法设计也起到重要的参考价值.

      (2) 动态规划算法

      动态规划算法(Dynamic Programming, DP)是由Bellman等[168]于1966年提出的一种通过问题分解和递归手段搜寻最优解的一类精确求解算法. 针对遥感卫星成像任务调度问题, Lemaître等[23]采用基于图论模型的DP算法对问题进行了求解; 白保存等[169]将问题分解为单轨任务最优合成问题; Damiani等[170]设计了一个包含当前任务、卫星电量和固存容量的评价向量, 并将问题分解为评价向量的最优任务组合问题. 针对遥感卫星数传任务调度问题, 刘洋等[171]将问题分解为VTW中数传任务的最优组合问题; 秦丽等[172]将问题按时间划分成了若干个阶段. 上述DP算法所采用的问题分解思想对大规模航天器任务调度问题的求解也具有参考价值.

    • 演化算法主要指通过模拟自然界生物种群演化机理和群体行为, 对组合优化问题进行迭代寻优的一类元启发式算法. 演化算法在航天器任务调度领域应用广泛, 本节选取遗传算法、蚁群算法和粒子群算法等三类典型的演化算法, 对其在航天器任务调度问题求解过程中的模型基础、编码方式和改进策略等进行介绍.

      (1) 遗传算法

      遗传算法(Genetic Algorithm, GA)是由Holland[173]于1975年提出的一种模拟进化论“自然选择”原理和遗传机理的演化算法. GA以种群的形式和概率化的遗传机理进行迭代优化, 具有隐并行性、多样化的解表示能力和出色的全局寻优能力, 在航天器任务调度问题中得到广泛应用.

      在任务排序模型的基础上, Parish[101]提出了求解AFIT Benchmark的经典算法Genitor, 该算法利用基因段表示测控任务的资源分配顺序, 如图7(a), 解码过程即依次为任务3、5、2、4、6和1分配资源; 周毅荣[174]和Chen等[175]设计了一种包含免疫遗传算法和学习策略的GA, 在大规模多星多站测控任务调度中取得出色的优化效果. 上述基因编码方式与任务排序模型契合度高, 成为航天器任务调度算法中一种常见的编码方式. Sun等[28]、Song等[42]、张鹏等[106]、李云峰等[176]和韩传奇等[177]也基于该编码形式, 以及成像质量优先、局部搜索、深度优先搜索、冲突消解和精英保留等策略有效求解了航天器任务调度问题.

      图  7  遗传算法求解航天器任务调度问题编码示例. (a) 任务排序模型的编码形式. (b) VTW分配模型的编码形式

      Figure 7.  Illustrations of the GA encoding for spacecraft mission scheduling. (a) The encoding of a mission-sequencing model. (b) The encoding of a VTW-allocation model

      在VTW分配模型的基础上, Kim等[45]、Li等[57]和Niu等[178]通过0-1基因值表示遥感卫星执行任务的VTW, 如图7(b), 解码过程即为任务1分配VTW2, 以此类推; Hosseinabadi等[179]通过基因段分别表示了执行任务的卫星、VTW; 孙凯等[161]用整数基因值表示遥感卫星执行任务的VTW, 并在算法中引入知识模型与参数学习策略; Xhafa等[133-134]采用直接编码的形式表示了航天器测控任务, 并设计了包含种群竞争与淘汰策略的GA; Tang等[98]和Du等[180]通过基因值分别表示了导航卫星任务和测控任务的离散化VTW, 并进一步设计了多目标的优化算法; 张超等[43]还在传统GA的迭代机制中引入Metropolis准则, 通过基因变量表示VTW和任务工作模式, 实现了敏捷遥感卫星任务调度问题的优化.

      可见, 基于任务排序模型和VTW分配模型, GA都能较好地完成解的表示和问题求解. 不过, 受任务排序模型本身编码过程的限制, 基于该模型的GA可能会在优化过程中丢失优质解; 而基于VTW分配模型的GA可能出现编码长度过长、基因表示类型过多的情况, 对算法迭代与搜索效率可能产生一定的影响. 因此, 合理的航天器任务调度模型与编码方式, 以及有针对性地算法改进措施, 对GA求解航天器任务调度问题起到重要作用.

      (2) 蚁群算法

      蚁群优化(Ant Colony Optimization, ACO)算法是由Colorni等[181]于1991年提出的一种模拟蚁群寻径行为的演化算法. ACO通过蚁群寻径过程中信息素的积累、反馈、挥发与通讯等机制不断调整蚁群路径, 表现出良好的渐近收敛性、隐并行性和全局寻优能力.

      在遥感卫星任务调度方面, 邱涤珊等[182]、耿远卓等[183]基于蚁群系统、最大最小蚂蚁、动态转移概率等策略求解了遥感卫星任务调度问题; 严珍珍等[184]、陈宇宁等[185]在传统ACO中引入了知识学习与信息素限制策略; 针对ACO优化周期长、易陷入局部最优的问题, 朱新新等[186]等基于综合启发信息、冲突消解和扰动策略决策任务序列和VTW. 此外, Gao等[187]、Wu等[188]在ACO的框架中引入局部搜索策略, 也取得了出色的优化效果.

      在导航卫星和航天器测控任务调度方面, Zhang等[114-117]设计了蚁群间的合作交流机制; 邢立宁等[189-190]在ACO中引入导向局部搜索策略和知识模型, 提升了算法在大规模测控任务调度问题中的局部与全局寻优能力; 陈祥国等[15]在蚂蚁转移概率中引入伪随机影响, 并基于测控任务的冲突消解策略缩减了ACO的搜索空间. 针对导航卫星任务调度的问题中, 黄双临等[191]在蚁群系统的基础上设计了动态的偏向探索概率, 实现蚂蚁探索比例的自适应性调整; Li等[192]考虑到ACO优化初期信息素匮乏的现象, 混合使用了GA与ACO, 也取得了良好的优化效果.

      ACO及其改进策略在航天器任务调度问题中得到诸多应用, 但由于ACO路径优化的基本思想, 相关研究中的ACO通常以蚂蚁路径表示卫星执行任务的顺序, 其调度模型也以任务排序模型为主. 因此, ACO也会受解码策略的影响导致优质解的丢失, 在具有复杂约束逻辑的任务调度场景中可能不利于全局寻优.

      (3) 粒子群算法

      粒子群优化(Particle Swarm Optimization, PSO)算法是由Kennedy等[193]于1995年提出的一种模拟鸟群觅食行为的演化算法. 与GA和ACO算法相比, PSO结构简洁、易于实现, 也具有收敛快、鲁棒性好的特点. 最初的PSO主要用于连续优化问题, 现阶段航天器任务调度研究中采用的PSO算法大部分是以Kennedy等[194]于1997年提出的离散粒子群优化(Discrete Particle Swarm Optimization, DPSO)算法为基础的.

      考虑到传统PSO算法不能求解离散优化问题, 汤绍勋等[195]通过粒子位置矢量表示执行任务的VTW, 通过粒子维度表示VTW的数量; 常飞等[196]通过粒子表示任务VTW被选择的概率, 基于概率顺序完成解码, 并引入基于种群多样性的粒子自动增减机制; Chen等[197]在粒子向量中同时表示了数传任务的VTW和卫星工作模式, 并引入量子行为和变异算子增强了算法全局寻优能力. 此外, Chen等[198]、国晓博等[199]和刘建银等[200]在粒子向量中表示了任务资源, 并引入遗传、禁忌和方向回溯等机制, 完成了高低轨航天器联合测控任务、森林遥感卫星区域目标观测等任务调度问题的研究.

      由于上述算法通常以面向离散优化的DPSO为基础, 故其调度模型也以VTW分配模型为主. 不过, PSO算法本身拥有连续优化与离散优化的双重特点, 过于侧重离散化的编码形式可能不利于算法的寻优. 相反, 采用离散优化(决策VTW)与连续优化(决策任务开始时间)的编码方式, 可能更适合现阶段具有长VTW特点的航天器任务调度问题.

    • 局部搜索算法是指从初始解出发, 不断搜索邻域空间并有选择地向优质解移动的一类元启发式算法. 现阶段航天器任务调度研究中常用的局部搜索算法包括禁忌搜索算法和模拟退火算法等. 本节分别对两种算法在航天器任务调度求解过程中的模型基础、邻域结构和搜索策略等进行介绍.

      (1) 禁忌搜索算法

      禁忌搜索(Tabu Search, TS)算法是由Glover[201-202]于1986年提出的一种带有记忆策略的局部搜索算法. TS算法通过禁忌表记录寻优过程中的局部最优解或产生局部最优解的操作, 以避免对局部最优空间的重复搜索, 达到跳出局部最优、开辟优质解空间的效果. TS算法操作简单、实用性好, 是最早用于航天器任务调度问题求解的算法之一.

      在任务排序模型的基础上, Cordeau等[6-7]利用一种求解VRP问题的TS算法实现了遥感卫星单轨任务的调度; 贺仁杰等[203]基于JSP模型设计了工件插入、移动、交换机器等邻域结构; 左春荣等[204]设计了在任务序列中增减、替换任务的邻域结构; 陈英武和李菊芳等[205-206]基于任务序列设计了多种邻域结构, 并设计了基于变邻域策略的TS算法; Blöchliger等[111]基于图着色模型中的颜色选择设计邻域结构, 并采用变禁忌长度的TS算法求解航天器测控任务调度问题.

      在VTW分配模型的基础上, Xhafa等[136]通过对VTW和开始时间扰动的方式构造邻域; Sarkheyli等[50]设计了任务增减和VTW内冲突消解等邻域结构, 并选取任务与VTW的匹配关系作为禁忌对象; Habet等[207]设计了邻域评估机制, 用于提升TS算法在遥感卫星任务调度过程中的邻域搜索效率. 此外, 禁忌搜索还被用于基于背包模型的航天器任务调度问题[60]的求解中.

      TS算法表现出良好的问题适用性和求解效果, 但也由于机制较为简单, 近几年来应用TS算法直接求解航天器任务调度问题的研究较少. 因此, TS算法应与最新的智能优化技术深度融合, 才能更好地适应复杂化、多样化的航天器任务调度问题.

      (2) 模拟退火算法

      模拟退火(Simulated Annealing, SA)算法由Metropolis等[208]于1953年提出, 并由Kirkpatrick等[209]于1983年应用于组合优化领域. SA算法是一种源于固体退火原理的局部搜索算法, 根据温度变化概率性地接受劣解, 达到跳出局部最优、开辟优质解空间的效果. 由于SA算法通常受初始解质量和问题规模影响较小, 具有良好的渐进收敛性, 在航天器任务调度问题中得到诸多应用.

      在任务排序模型的基础上, 黄瀚等[210]通过插入或交换任务序列中互斥顶点等方式构造邻域, 并设计了包含二次搜索和精英策略的SA算法. 在VTW分配模型的基础上, 贺仁杰等[211]、Gao等[212]设计了任务增减、合并或分解的邻域结构, 并在SA算法中加入了随机扰动、重调度等策略; 徐欢等[213]、Du等[214]通过交换决策变量的方式直接构造SA算法的邻域; 黄生俊等[215]借鉴蚁群算法中的反馈特性, 结合先验、后验知识进行邻域设计, 并在算法陷入局部最优时触发扰动; Wu等[46]基于自适应概率设计了任务增减、迁移等邻域操作, 并在SA算法中引入自适应的温度控制和禁忌策略; Lin等[216]通过交换任务VTW和载荷频段的方式构造邻域, 并混合使用了SA与DP算法, 有效求解了遥感卫星多载荷任务调度问题.

      此外, 针对航天器任务调度问题规模巨大、易陷入局部最优的特点, 近年来变邻域搜索[217]、自适应大邻域搜索[44, 56]等局部搜索算法也得到诸多应用, 取得了出色的优化效果.

    • (1) 模因算法

      模因算法(Memetic Algorithm, MA)是由Moscato[218]于1989年提出的一种融合演化算法与局部搜索算法的一类混合元启发式算法. 其中, “Memetic”源于Dawkins著作《The Selfish Gene》[219]中“Meme”一词, 寓意文化层面的遗传基因, 故MA又称为文化基因算法. MA既保留了演化算法基于种群进化的优化特点, 又拥有局部搜索算法优秀的局部寻优能力, 起到了对二者取长补短的效果. MA在航天器任务调度领域也得到了诸多应用, 根据演化算法与局部搜索算法的混合形式, 可以分为以下三种:

      1) 基于演化算法框架的MA, 即Moscato[218]最早提出的MA. 例如, Du等[180]、邢立宁等[189-190]和刘建银等[200]分别在求解航天器任务调度的GA、ACO和PSO算法中引入了局部搜索机制. 此类MA可以视为一种基于个体改进和修复策略的演化算法, 是最常用的一类MA. 不过, 针对个体的局部搜索机制也将增加种群迭代的时间, 故设计合理的搜索频率、迭代次数与触发条件是此类MA的关键.

      2) 基于局部搜索框架的MA. 例如, 贺仁杰等[203]和黄生俊等[215]分别在TS和SA中引入了个体交叉、信息素反馈等演化策略. 此类MA可以视为一种通过演化策略设计邻域结构、引导搜索方向的局部搜索算法, 但由于缺乏种群的支持, 此类MA在解的多样性、隐并行性等方面不及演化算法.

      3) 基于分层框架的MA. 例如, 为发挥GA早期寻优和SA深度搜索的能力, Zhu等[55]设计了基于GA和SA的两阶段式优化算法, 在遥感星座任务调度中也取得了出色的效果. 不过, 此类MA对编码形式的通用性、算法切换的合理性也有更高的要求.

      可见, MA实际上是一种演化算法与局部搜索算法组合的框架. 针对复杂化、大规模的航天器任务调度需求, 相互协同、取长补短、优势互补的算法组合框架对问题求解将起到十分重要的帮助.

      (2) 基于机器学习的决策算法

      基于机器学习的决策算法是指通过监督学习、强化学习等机器学习手段, 训练航天器任务调度决策模型, 进而对航天器任务进行调度的一类方法. 在监督学习方面, Li等[220]利用鲁棒决策树、支持向量机和人工神经网络构造了一种遥感卫星任务可调度性预测模型; 刘嵩等[221]从遥感卫星历史数据中提取了任务优先级、持续时间和冲突度等特征, 基于变隐含层的BP神经网络模型构造了任务可调度性预测模型; 考虑云雾遮挡等不确定性因素, 邢立宁等[67]提取了气象特征, 并利用任务可调度预测模型设计了遥感卫星自主任务调度算法; Du等[158]通过进化神经网络算法训练任务可调度性预测模型, 将任务分配给最有可能执行该任务的卫星, 显著提高了大规模敏捷遥感卫星任务调度的效率.

      在强化学习方面, 针对遥感卫星协同任务调度问题, 王冲等[68-69]分别通过Q学习算法和进化神经网络算法训练了卫星在动作集中的选择策略; Wang等[70]通过A3C算法训练了遥感卫星任务调度决策模型, 当新任务达到时, 该模型将决定任务执行与否, 并为决定执行的任务分配一个最长的VTW, 为星上任务的自主调度提供了解决方案.

      基于机器学习决策算法可视为一种利用高级规则指导任务排序或任务分配的算法, 具有启发式算法简单、快速和机器学习技术自适应、自学习的综合特征. 目前各类航天器管控部门都积累了大量的任务调度历史数据, 故相关技术具有很强的应用前景. 另一方面, 虽然上述算法实现了航天器任务的自主调度, 但也呈现出“来一个决策一个”的局限性, 难以保障大规模任务调度的全局优化性. 同时, 上述算法均对所研究的问题进行了大幅度简化, 以便提取用于模型训练的任务与资源特征, 但在现阶段航天器任务调度问题日趋复杂的情况下, 基于简单特征的决策模型可能很难取得理想的效果.

    • 本节从启发式算法、精确求解算法和元启发式算法等三个角度梳理了航天器任务调度研究中的常用算法, 并对各类算法的编码特点、邻域结构和优缺点进行了分析. 表2将上述内容进行了总结. 这些算法成功求解了诸多航天器任务调度难题, 贡献了重要的理论与实践经验, 但与此同时, 也存在以下两点不足:

      表 2  航天器任务调度研究中常用算法总结

      Table 2.  A summary of commonly used algorithms for spacecraft mission scheduling

      算法类型算法子类常用编码模型算法优点算法不足
      启发式算法优先级排序算法任务排序模型1. 结构简单、运算速度快
      2. 符合人的主观认识, 有经验支撑
      3. 有助于缩减问题解空间, 在与其他算法组合使用过程中提升求解效率
      1. 与问题特征和调度模型紧耦合, 通用化程度不高
      2. 求解效果欠佳, 常用于辅助决策, 很少直接用于调度方案的生成
      冲突消解算法以任务排序模型为主
      任务分配算法以VTW分配模型为主
      精确算法分支定界算法任务排序或VTW分配模型1. 可以求得最优解, 在不确定性条件下也能保证解的最优性
      2. 算法思想对其他算法有指导意义, 与其他算法有良好的组合应用前景
      1. 只适用于小规模、简单约束问题, 求解大规模、复杂约束问题能力有限
      2. 通常需要较大程度的问题简化
      动态规划算法
      元启发式算法演化算法遗传算法任务排序或VTW分配模型1. 具有隐并行性和多样的解表示能力
      2. 具有出色的全局寻优能力
      3. 与其他算法混合的兼容性好
      4. 任务排序模型的编码形式简洁、操作简单
      1. 局部搜索能力有限
      2. 任务排序模型的编码方式可能丢失优质解
      3. VTW分配模型的编码方式复杂且冗长, 可能影响优化效率
      蚁群算法以任务排序模型为主
      粒子群算法以VTW分配模型为主
      局部搜索禁忌搜索算法任务排序或VTW分配模型1. 原理简单、易于实现、适用性好
      2. 具有出色的局部搜索能力
      3. 具有一定的局部最优逃逸能力
      1. 全局搜索能力有限, 易陷入局部最优
      2. 依赖于邻域结构的设计
      模拟退火算法以VTW分配模型为主
      其他算法模因算法任务排序或VTW分配模型对局部搜索和演化算法取长补短依赖于框架设计, 可能降低迭代效率
      机器学习决策算法以任务排序模型为主简单、快速并且自适应、自学习“来一个决策一个”, 缺乏全局优化性

      (1) 航天器任务调度算法与模型紧耦合, 算法设计的灵活性不足.

      各类航天器任务调度算法均有其适用的任务调度模型, 这也是造成现阶段航天器任务调度模型与算法紧耦合、调度算法通用性不足的主要原因. 因此, 结合航天器任务调度模型研究现状, 研究模型与算法解耦、算法灵活可配的航天器任务调度架构具有重要的实践意义.

      (2) 不同算法之间深度协同、合理搭配的有效机制还未形成.

      各类算法均有不同的优缺点和适用性, 例如启发式算法常用于辅助决策, 精确算法求解大规模问题能力有限, 演化算法全局寻优能力强等. 虽然模因算法给出了一种很好的算法协同思路, 但其现阶段在求解能力、问题适用性等方面仍有提升空间. 因此, 对不同类型的算法进行合理搭配, 形成深度协同、取长补短、优势互补的算法组合框架也是求解大规模、复杂化航天器任务调度问题的必要途径.

    • 航天器任务调度通用求解技术是指可以针对不同类型的航天器任务建立通用化的任务调度模型, 或采用不同任务调度算法进行模型解算的通用求解器、工具箱、算法包等. 航天器任务调度通用求解技术可以解决不同场景下的航天器任务调度、异构多航天器协同任务调度等现实问题, 方便地调用多样化、可拓展的调度算法, 为从业人员提供便捷、丰富且有效的问题建模与求解手段. 因此, 航天器任务调度通用求解技术对提升航天器综合管控自动化、智能化和一体化水平起到重要作用, 是衡量一个国家航天综合实力的重要标准, 也是航天部门亟需发展的关键技术.

      目前, 具有通用建模与求解特色的航天器任务调度工具有CPLEX、STK/Scheduler、Europa2和我国商业遥感卫星“高景一号”任务调度分系统等. 本节对上述四种通用求解技术的建模特色、求解算法和主要功能进行梳理, 总结上述通用求解技术的优缺点, 结合航天综合管控的发展现状, 指出我国自主研发航天器任务调度通用求解器的必要性和新的应用思路, 为航天器任务调度通用求解工具的研究与设计提供参考.

    • CPLEX是美国IBM公司开发的一款数学规划求解器, 适用于线性规划、二次规划等问题[222]. 在建模语言方面, CPLEX语言简洁易懂, 并可以与C++、Java和Python等主流编程语言兼容; 在求解质量方面, CPLEX内置了单纯形、分支定界等一系列精确求解算法, 可以给出问题的最优解, 保持了一系列经典运筹学Benchmark中的最优记录, 因此也被应用于航天器任务调度问题的求解中.

      针对遥感卫星成像与数传任务一体化调度问题, Xiao等[22]建立了分段式的FSP模型, 并通过CPLEX对问题进行了求解. 不过, 由于问题的NP难特性, 在7200 s的优化时间内只能完成20个任务的调度; 考虑到敏捷卫星时间依赖的姿态转换约束无法由线性函数表示, Liu等[44]通过CPLEX对简化后的问题进行了优化, 但也仅能完成12个任务; 为保障不确定环境下任务调度的最优性, Valicka等[53]采用CPLEX对考虑随机云层遮挡的遥感卫星任务进行了调度, 优化时间约为2000 s-3000 s; 针对“资源三号”遥感卫星任务调度问题, 徐忠良等[223]通过CPLEX完成了11个任务的优化调度; Bensana等[59]成功利用CPLEX对卫星单轨任务进行了调度, 但无法完成多轨任务的有效调度.

      另一方面, CPLEX可与其他算法或策略混合使用, 一定程度上能够提升航天器任务调度问题的求解效率. 例如, 针对Galileo导航星座任务调度问题, Marinelli等[96]在CPLEX中引入了Lagrangian松弛和其他启发式策略, 能够在18000 s的优化时间内对360个导航卫星任务进行调度. 同时, Marinelli还指出在无其他辅助策略的情况下, CPLEX的求解能力仅为120个任务. Xu等[24]、王沛等[224]将局部搜索算法与CPLEX相结合, 在1800 s的时间内对100个遥感卫星任务进行了调度.

      上述研究表明, 虽然CPLEX在求解小规模航天器任务调度问题、不确定性任务调度问题和问题边界等方面表现出色, 但在求解大规模任务调度问题的时候效率低下, 且无法准确描述非线性的约束条件和收益. 因此, 在现阶段任务规模不断增长的情况下, CPLEX很难满足航天管控部门对任务调度质量与速率的双重需要, 很难在实际的航天业务调度系统中投入使用.

    • STK/Scheduler是美国Orbit Logic公司开发的一款卫星任务调度商用软件[225], 可在STK 6.0以上版本中直接调用. STK/Scheduler可以在STK模型和数据的基础上快速地建立任务调度模型, 通过内置的算法给出任务调度方案, 并具有友好的用户操作界面, 如图8. 其中, STK所计算的卫星轨道与VTW具有较高的准确性, 故STK也常作为航天器任务调度研究中VTW的计算工具.

      图  8  操作界面示例. (a) 场景(目标与资源)建模界面. (b) 资源属性设置界面

      Figure 8.  A view of the STK/Scheduler. (a) The scenario (targets and resources) modeling. (b) The resource parameter setting

      STK/Scheduler中包含以下5种调度算法: 1) One-Pass算法, 即基于任务优先级顺序和内置的期望函数分别确定任务资源与开始时间, 是一种典型的任务排序算法; 2) Sequential算法, 即在One-Pass算法的基础上同时考虑任务VTW时间、时长等其他因素; 3) Multi-Pass算法, 即基于规则多次运行One-Pass算法并调整调度方案, 是一种任务排序与冲突消解相结合的算法; 4) Neural Network算法, 即基于规则为任务分配VTW与开始时间并修复不可行解, 是一种任务分配与冲突消解相结合的算法; 5) Random算法, 与Neural Network算法相似, 但在分配VTW与开始时间时采用随机策略.

      李英先等[226]基于STK/Scheduler实现了通讯中继卫星的任务调度, 但考虑约束较为简单, 没有对频段匹配、切换时间等具有中继卫星特色的约束条件进行建模; 李云峰等[227]指出STK/Scheduler发送命令的时间较长, 不利于大规模的任务调度; 白敬培等[228]对5种内置算法进行了测试, 结果表明Multi-Pass算法和Random算法在短时间内的优化效果最佳; Li等[229]在STK/Scheduler的软件基础上引入了任务动态调整机制; Fisher等[230]给出了STK/Scheduler自定义算法的介绍, 但也仅限于对排序规则、交换策略等的调整功能. 以上, 虽然STK/Scheduler在航天器任务调度问题中取得了一定的效果, 但在问题复杂化、多元化的发展趋势下, STK/Scheduler也暴露出一些不足:

      1) 虽然对航天器任务、资源进行了用户友好化的封装, 但也很大程度上限制了任务、资源的属性与约束格式, 不利于包含复杂任务或约束的问题求解, 二次开发的难度较大;

      2) 缺乏对任务、资源、收益或约束条件的动态调整功能, 常用于静态的航天器任务调度问题;

      3) 主要功能最后更新于2006年, 没有包含进化算法、禁忌搜索等现阶段主流的智能优化算法, 对规则的依赖性较大. 随着近年来航天器任务调度问题规模与复杂性的不断提升, 其内置算法的求解效果可能不佳.

      另一方面, 2013年, Herz等[231]在航天器测控任务调度的问题中使用了STK/Scheduler Online, 通过互联网访问了STK/Scheduler服务器, 完成了场景建模、参数配置、优化调度等一系列功能. 这种远程式的任务调度方式使得用户的访问便捷、高效, 有助于服务功能的迭代更新和故障的快速修复, 在高性能服务器的支持下也有助于调度效率的提升. 因此, STK/Scheduler Online也为航天器任务调度系统的设计与部署提供了一种新思路.

    • Europa2 (2nd Generation of Extensible Universal Remote Operations Architecture)是NASA开发的面向航天器任务规划的第二代可扩展式通用远程操作体系结构[232], 已在NASA哈勃空间望远镜[233]、DS-1自主卫星[234]等项目中得到应用. 与规划领域经典语言PDDL (Planning Domain Description Language)不同, Europa2所基于的NDDL (New Domain Description Language)是一种基于状态变量、面向对象与声明性的语言, 故Europa2中主要通过定义标记、事务、对象、类、时间线和规划解等完成对一类航天器任务场景的描述, 并通过约束传播等约束规划技术给出一个可行的方案[235-238].

      基于状态变量的特点, Europa2主要面向航天器任务规划问题, 如航天器执行任务的动作逻辑、状态转移等. 该问题主要描述航天器任务的逻辑关系, 给出满足约束的可行方案, 对资源调度的需求较少. 而本文所探讨的任务调度问题主要解决任务资源与时间的分配, 例如执行任务的VTW、航天器及其电量、固存等载荷资源等. 故针对航天器任务调度问题, Europa2存在以下不足:

      1) 缺乏收益函数和调度优化机制, Europa2通过约束规划等方法给出可行的航天器动作序列, 但无法在收益函数的驱动下迭代地给出更优的调度方案;

      2) 基于约束传播的约束规划算法只能适用于小规模的任务场景, 例如单星单轨20个任务的规划时间已非常长, 且最新版本Europa2.6发布于2011年[232], 已很难适应现阶段大规模、复杂化的航天器管控新常态.

      不过, Europa2中的约束传播算法能够在新任务到达、任务或资源属性变更的情况下快速给出可行方案, 这对面向快速响应需求的动态任务调度算法与框架设计具有启发意义. 此外, NASA于2015年公布了一款基于Europa2的开源规划调度工具包OpenSPIFe (Open Scheduling and Planning Interface for Exploration)[239]. OpenSPIFe具备动作规划、动态调整、界面可视化等功能, 但相关应用较少, 有待进一步研究.

    • “高景一号”是我国首个商用敏捷遥感星座, 目前由4颗位于太阳同步轨道的0.5米分辨率光学成像卫星构成, 每颗卫星的轨道周期约为97分钟. 按照相关计划, 还将陆续发射20余颗敏捷遥感卫星, 与现有的4颗卫星组建新的“高景一号”星座网络. 鉴于“高景一号”星座的商业化运营模式和不断增加的卫星数量, 如何充分调度卫星任务、最大化经济收益是“高景一号”运控部门迫切关心的问题.

      目前, “高景一号”任务调度分系统采用的调度模型之一为任务排序模型, 并基于成像质量最高原则(即在VTW中点处执行任务)对任务序列进行解码. 由于在模型解码过程中会对任务序列进行约束检查, 解码后均为可行方案. 因此, 该调度模型的通用性也较强, 在此过程中复杂任务约束也均能得到处理.

      在任务排序模型的基础上, “高景一号”任务调度分系统所采用的调度算法主要为任务分配算法和优先级排序算法. 例如, 基于任务收益、持续时间、窗口数量等一系列任务与资源属性, 定义任务的综合优先级, 并基于优先级降序构建单星任务序列、依次分配资源. 由于机制简单, “高景一号”任务调度分系统能够较快地给出单星任务调度结果, 但也暴露出任务调度效果不佳、卫星缺乏协同、资源利用不充分等问题.

      另一方面, 当通过人工调整的方式对任务排序结果进行进一步优化时, 仍需重新进行解码与约束检查工作. 由于人工调整的结果并不能得到实时反馈, 故人工调整的方式存在一定的盲目性, 即可能出现人工调整结果不及原方案的情况. 由此, 该模型与算法虽然能够处理复杂的卫星业务约束, 但任务调度效率和快速响应能力仍有待提高.

    • 本节梳理了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统的基本原理、适用性和优缺点, 表3对本节内容进行了总结. 通过本节的综述与分析可知:

      表 3  用于航天任务调度的通用求解器总结

      Table 3.  A summary of the general techniques for spacecraft mission scheduling

      通用求解器常用调度模型求解算法求解器优点求解器不足
      CPLEX线性规划模型表示的任务排序模型或VTW分配模型分支定界算法等精确求解算法1. 语言简洁, 兼容性好
      2. 内置算法丰富, 降低算法设计难度, 同时开放了算法设计与改进接口
      3. 可以求得最优解, 在不确定性条件下也能保证解的最优性
      4. 用户基础大, 版本持续更新
      1. 很难描述非线性约束或收益, 复杂约束线性化难度大
      2. 很难求解大规模任务调度问题
      3. 算法改进对线性规划理论基础要求高
      4. 缺乏航天领域特色
      STK/Scheduler任务排序模型任务排序算法, 冲突消解算法 1. 与STK兼容, 建模简单
      2. 语言简洁, 兼容性好
      3. STK/Scheduler Online具有远程服务功能
      1. 封装程度较高, 难以描述复杂约束, 二次开发难度大
      2. 缺乏动态调整功能
      3. 算法优化能力有限, 已不再更新
      VTW分配模型 任务分配算法, 冲突消解算法
      Europa2通过标记、事务、对象、类、时间线、规划解描述一个规划模型约束传播等约束规划算法1. 面向状态变量和动作序列, 求解过程直观
      2. 约束传播算法有助于动态调度机制的设计
      1. 缺乏收益函数和调度优化机制
      2. 只适用于小规模(单星单轨)任务调度, 已不再更新
      “高景一号”任务调度分系统任务排序模型基于最早开始原则的任务排序算法1. 模型与算法简洁
      2. 可以考虑全部复杂约束
      1. 调度质量有待提高
      2. 动态调整以人工为主, 结果无法实时反馈

      (1) 现阶段尚无能够满足航天器任务调度需求的通用求解器.

      虽然上述航天器任务调度通用求解器均在一些应用场景中取得了良好的求解效果, 但每一款求解器的局限性也非常明显: 例如, CPLEX难以处理大规模与非线性问题, STK/Scheduler复杂约束处理与二次开发难度大, Europa2缺乏对收益函数的优化, “高景一号”任务调度分系统优化能力有限等. 即使STK/Scheduler与Europa2能够适用于简单的航天器任务调度问题, 但其内置算法也相对落后, 已多年未发布新版本. 目前, 航天器任务调度问题正向着大规模、复杂化和动态需求常态化的趋势快速发展, 上述航天器任务调度通用求解器尚不能满足发展的要求.

      (2) 我国需要研发具有自主知识产权的航天器任务调度通用求解技术.

      综合考虑约束描述能力、求解效果、版权与服务支持等因素, CPLEX、STK/Scheduler、Europa2并未在我国航天系统中得到应用. 或许STK/Scheduler和Europa2等航天器任务调度通用求解器已有融合先进技术的新版本, 但并未对外公布. 因此, 我国需要研发适合我国国情、具有自主知识产权的航天器任务调度通用求解技术, 在核心技术上掌握主动权, 为提升我国航天综合管控实力提供技术支撑.

      (3) 基于云平台的远程航天器任务调度服务是一种新的应用思路.

      STK/Scheduler Online提供了一种在线式的航天器任务调度服务新模式. 该模式使用户访问更加便捷、高效, 有助于服务功能的迭代更新和故障的快速修复, 在高性能服务器的支持下也能提升任务调度的效率. 因此, 结合现阶段云计算的技术优势, 向航天部门提供远程的任务调度服务是一种新颖、高效的应用思路.

    • 航天器任务调度是航天器管控的重要内容, 是发挥航天系统社会经济效益、实现航天器使命价值的重要保障. 随着航天事业的快速发展, 作为调度技术的两大要素, 航天器任务调度模型与调度算法已得到广泛研究, 并在各大航天调度系统中得以检验. 在此过程中, 涌现出一批优秀的调度模型、算法和通用求解技术, 为航天器任务调度研究贡献了重要的理论体系与实践经验. 本文系统地梳理了近年来航天器任务调度研究中的模型、算法与通用求解技术, 总结了相关技术中的共性特征与区别, 为未来航天器任务调度的研究工作提供了参考.

      本文的主要工作如下: 1) 根据航天器任务目标的不同, 将现阶段具有调度需求的主要航天器任务分为遥感卫星任务、通讯中继卫星任务、导航卫星任务和航天器测控任务, 阐述了各类航天器任务调度的常用模型及特征; 2) 根据优化原理的不同, 将航天器任务调度算法分为启发式算法、精确求解算法和元启发式算法, 探讨了各类算法的编码特点和优缺点; 3) 介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等具有通用特色的航天器任务调度工具, 分析了其适用性与应用前景.

      然而, 通过本文的综述也发现, 现阶段航天器任务调度研究暴露出“模型-问题-算法”紧耦合的弊端, 模型与算法的兼容性与可拓展性不足, 难以适应航天系统灵活组网、快速响应的新常态. 由此, 本文指出以下几点未来航天器任务调度研究的新方向:

      (1) 研究航天器任务调度统一化建模语言.

      航天器任务调度统一化建模语言是解决航天器任务调度模型兼容性问题的根本途径. 通过本文综述发现, 诸多航天器任务调度模型具有很大的相似性, 其围绕任务与资源在时、空、频域可见性的建模原则是统一的. 现阶段已有几款成熟的统一化建模语言, 但这些语言缺乏航天领域和组合优化领域的应用特色. 由此, 研究统一化且具备领域特色的航天器任务调度建模语言, 是发展航天器通用建模与求解技术, 满足未来航天器灵活管控需要的内在要求.

      (2) 研究航天系统管控体制下有效应对大规模任务调度问题的解空间优化技术.

      随着航天器规模持续增加以及航天系统组网的常态化发展, 解空间规模已成为限制航天器任务调度效率的关键因素. 目前, 任务分配、分层规划等方法可将大规模航天器任务调度问题分解为诸多子问题, 虽然提升了调度效率, 但也违背了航天系统综合管控、一体化调度的发展趋势, 丢失了问题的全局优化特点. 近年来, 深度学习、强化学习等技术发展迅速, 并在旅行商、车辆路径规划等经典组合优化问题中得到了成功应用. 基于机器学习的技术优势, 可以研究航天器任务调度解空间优化技术, 在保留全局性优化特点的基础上, 实现大规模任务调度解空间规模的精准缩减, 以满足航天系统综合管控与快速响应的双重需求.

      (3) 共同打造航天器任务调度算法库与测试集.

      以往, 调度模型兼容性不足是限制航天器任务调度算法通用化发展的主要原因, 而上述航天器统一化建模语言可以解决这一问题. 以后, 航天器任务调度算法不再局限于某一特定的航天应用场景, 而将适用于更多的具有普遍意义的航天器任务调度问题. 鉴于此, 打造一个开源的、持续更新的航天器任务调度算法库, 有助于营造世界范围内相关学者及业务人员共研共享的发展环境. 同时, 为检验算法性能、促进良性竞争, 打造兼具算法测试、教学、新案例发布等功能的航天器任务调度标准测试集也具有十分重要的意义.

      (4) 研发具有自主知识产权的航天器任务调度通用求解技术.

      在上述研究方向的基础上, 研发适合我国国情、具有自主知识产权、满足国家航天战略发展需要的航天器任务调度通用求解技术势在必行. 通用求解技术的研发是实现我国在轨航天器综合管控、灵活组网这一目标的出发点和落脚点. 未来, 在通用求解技术的支撑下, 资源卫星、商业卫星、侦察卫星、导航卫星、中继卫星、空间站与地面站网等不同类型、隶属不同部门的航天任务资源将密切联动, 更大限度地发挥我国航天系统的社会经济效益.

WeChat 关注分享

返回顶部

目录

    /

    返回文章
    返回