面向应急条件的多星动态调度方法
收稿日期: 2012-06-13
修回日期: 2012-11-29
网络出版日期: 2013-01-09
基金资助
国家自然科学基金(61104180, 71271216);国家"973"计划(6136101)
Multi-satellite Dynamic Scheduling Method for Emergencies
Received date: 2012-06-13
Revised date: 2012-11-29
Online 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算法提高了调度质量,适用于应急条件下多星动态调度问题。
王建江 , 朱晓敏 , 吴朝波 , 邱涤珊 . 面向应急条件的多星动态调度方法[J]. 航空学报, 2013 , 34(5) : 1151 -1164 . DOI: 10.7527/S1000-6893.2013.0204
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.
[1] Bianchessi N, Cordeau J F, Desrosiers J, et al. 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.
[2] Cordeau J, Laporte G. Maximizing the value of an earth observation satellite orbit. Journal of Operational Research Society, 2005, 56(8): 962-968.
[3] Lin W C, Liao D, Liu C, et al. Daily imaging scheduling of an earth observation satellite. IEEE Transactions on System, Man, Cybernetics, Part A: Systems and Humans, 2005, 35(2): 213-223.
[4] Zhu K J, Li J F, Baoyin H X. Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost. Acta Astronautica, 2010, 66(1): 220-229.
[5] Dai G X, Da Q L. The study of combinatorial scheduling problem in emergency systems. Systems Engineering and Electronics, 2000, 20(9): 52-55. (in Chinese) 戴更新, 达庆利. 多资源组合应急调度问题的研究. 系统工程与电子技术, 2000, 20(9): 52-55.
[6] He J M, Liu C L, Cao J, et al. Emergency management and emergency systems—placement, scheduling and algorithms. Beijing: Science Press, 2005. (in Chinese) 何建敏, 刘春林, 曹杰, 等. 应急管理与应急系统——选址、调度与算法. 北京: 科学出版社, 2005.
[7] Bensana E, Verfaillie G, Agnese J C, et al. Exact and inexact methods for the daily management of an earth observation satellite. Proceedings of International Symposium on Space Mission Operations and Ground Data Systems, 1996, 4: 507-514.
[8] Hall N G, Magazine M J. Maximizing the value of a space mission. European Journal of Operational Research, 1994, 78(2): 224-241.
[9] Lin W C, Chang S C. Hybrid algorithms for satellite imaging scheduling. IEEE International Conference on Systems, Man and Cybernetics, 2005, 3: 2518-2523.
[10] Lin W C, Liao D Y. A tabu search algorithm for satellite imaging scheduling. Proceedings of 2004 IEEE International Conference on Systems, Man and Cybernetics, 2004, 2: 1601-1606.
[11] Globus A, Crawford J, Lohn J, et al. Scheduling earth observing fleets using evolitionary algorithms: problem description and approach. Proceedings of 3rd International NASA Workshop on Planning and Scheduling for Space, 2002.
[12] Globus A, Crawford J, Lohn J, et al. A comparison of techniques for scheduling fleets of earth-observing. Journal of Operational Research Society, 2003, 56(8): 962-968.
[13] Pemberton J C, Greenwald L G. On the need for dynamic scheduling of imaging satellites. Proceedings of American Society for Photographing and Remote Sensing (ASPRS-02), 2002.
[14] Liao D Y, Yang Y T. Imaging order scheduling of an earth observation satellite. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 2007, 37(5): 794-802.
[15] Liao D Y, Yang Y T. Satellite imaging order scheduling with stochastic weather condition forecast. Proceedings of 2005 IEEE International Conference on Systems, Man and Cybernetics, 2005, 3: 2524-2529.
[16] Billups S C. Final report of the UCDHSC mathematics clinic: satellite mission scheduling with dynamic tasking. Denver: Mathematics Department, University of Colorado at Denver and Health Sciences Center, 2006.
[17] Wang J M, Li J F, Tan Y J. Study on heuristic algorithm for dynamic scheduling problem of earth observation satellites. Proceedings of 8th International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, 2007, 1: 9-14.
[18] Wu G H, Ma M H, Wang H L, et al. Multi-satellite observation scheduling based on task clustering. Acta Aeronautica et Astronautica Sinica, 2011, 32(7): 1275-1282. (in Chinese) 伍国华, 马满好, 王慧林, 等. 基于任务聚类的多星观测调度方法. 航空学报, 2011, 32(7): 1275-1282.
[19] Bai B C, Ci Y Z, Chen Y W. Dynamic task merging in multi-satellites observing scheduling. Journal of System Simulation, 2009, 21(9): 2646-2649. (in Chinese) 白保存, 慈元卓, 陈英武. 基于动态任务合成的多星观测调度方法. 系统仿真学报, 2009, 21(9): 2646-2649.
[20] Bai B C, He R J, Li J F, et al. Imaging satellite observation scheduling with task merging. Acta Aeronautica et Astronautica Sinica, 2009, 30(11): 2165-2171. (in Chinese) 白保存, 贺仁杰, 李菊芳, 等. 考虑任务合成的成像卫星调度问题. 航空学报, 2009, 30(11): 2165-2171.
[21] He R J. Research on imaging reconnaissance satellite scheduling problem. Changsha: National University of Defense Technology, 2004. (in Chinese) 贺仁杰. 成像侦察卫星调度问题研究. 长沙: 国防科学技术大学, 2004.
/
| 〈 |
|
〉 |
CJA