航空学报 > 2013, Vol. 34 Issue (5): 1151-1164   doi: 10.7527/S1000-6893.2013.0204

面向应急条件的多星动态调度方法

王建江1, 朱晓敏1, 吴朝波1,2, 邱涤珊1   

  1. 1. 国防科学技术大学 信息系统工程重点实验室, 湖南 长沙 410073;
    2. 中国人民解放军95246部队, 广西 北海 536000
  • 收稿日期:2012-06-13 修回日期:2012-11-29 出版日期:2013-05-25 发布日期:2013-01-09
  • 通讯作者: 朱晓敏 男, 博士, 讲师。主要研究方向: 云计算, 容错计算, 绿色计算和效能评估。 Tel: 0731-84574552 E-mail: xmzhu@nudt.edu.cn E-mail:xmzhu@nudt.edu.cn
  • 作者简介:王建江 男, 博士研究生。主要研究方向: 多目标组合优化, 卫星资源管理与调度。 Tel: 0731-84574552 E-mail: jianjiangwang@nudt.edu.cn;朱晓敏 男, 博士, 讲师。主要研究方向: 云计算, 容错计算, 绿色计算和效能评估。 Tel: 0731-84574552 E-mail: xmzhu@nudt.edu.cn
  • 基金资助:

    国家自然科学基金(61104180, 71271216);国家"973"计划(6136101)

Multi-satellite Dynamic Scheduling Method for Emergencies

WANG Jianjiang1, ZHU Xiaomin1, WU Chaobo1,2, QIU Dishan1   

  1. 1. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China;
    2. No.95246 Unit, People's Liberation Army of China, Beihai 536000, China
  • Received:2012-06-13 Revised:2012-11-29 Online:2013-05-25 Published:2013-01-09
  • Supported by:

    National Natural Science Foundation of China (61104180, 71271216);National Basic Research Program of China (6136101)

摘要:

针对应急条件下多星动态调度问题,建立了多目标数学规划模型,提出了应急条件多星成像任务合成策略:建立多星多轨任务合成图(MSMOTMG)模型,提出任务合成算法CP-TM。为克服合成导致任务成像机会减少的缺陷,提出了基于合成任务分解的修复技术。此外,为进一步提高调度效率,考虑了任务在等待队列中的向后移位策略,提出了综合考虑任务合成、修复和向后移位的多星动态应急调度(TMRBS-DES)算法。通过大量模拟实验,将TMRBS-DES算法同RBHA算法,以及3个baseline算法(BS-DES、TMR-DES和TMBS-DES)进行了比较。实验结果表明TMRBS-DES算法提高了调度质量,适用于应急条件下多星动态调度问题。

关键词: 成像卫星, 动态应急调度, 数学模型, 任务合成, 向后移位, 修复, 启发式算法

Abstract:

To solve multi-satellite dynamic scheduling problems in emergency, a multi-objective mathematic programming model is established in this paper. A novel task merging strategy is proposed for multiple imaging satellites: a multi-satellite multi-orbit task merging graph (MSMOTMG) model is established and a task merging algorithm—CP-TM is proposed. In addition, a rehabilitation technique based on task decomposition is suggested to overcome the disadvantage that task merging may cause tasks to have less imaging opportunities. To further enhance the schedulability, the backward shift of tasks in the waiting sequences is considered in our study. Furthermore, a novel dynamic algorithm called TMRBS-DES is presented, which comprehensively considers the task merging, rehabilitation and backward shift. Extensive experiments by simulations are conducted to compare TMRBS-DES with an existing algorithm—RBHA as well as three baseline algorithms—BS-DES, TMR-DES and TMBS-DES. Experimental results demonstrate that TMRBS-DES improves the scheduling quality and is suitable for multi-satellite dynamic scheduling in emergency.

Key words: imaging satellite, dynamic emergency scheduling, mathematical model, task merging, backward shift, rehabilitation, heuristic algorithm

中图分类号: