航天测控调度分枝定界算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (31): 17-19.

航天测控调度分枝定界算法

康宁，武小悦

国防科学技术大学信息系统与管理学院，长沙 410073

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-01 发布日期:2011-11-01

Branch and bound algorithm for TT&C scheduling

KANG Ning，WU Xiaoyue

College of Information Systems and Management，National University of Defense Technology，Changsha 410073，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-11-01 Published:2011-11-01

摘要/Abstract

摘要： 通过分析航天测控调度问题的测控需求，建立了航天测控调度整数规划模型，引入了拉格朗日松弛思想并与分枝定界算法结合，设计了基于拉格朗日松弛的分枝定界算法求解航天测控调度问题。通过对两个场景的仿真实验，得到了两个场景的航天测控调度问题最优值，验证了基于拉格朗日松弛的分枝定界算法的有效性。

关键词: 拉格朗日松弛, 航天测控调度, 次梯度优化, 分枝定界

Abstract: This paper analyzes TT&C request of TT&C scheduling problem and constructs an integer programming model of TT&C scheduling，introduces an idea of Lagrangian relaxation and combines the idea with branch and bound algorithm，designs a branch and bound algorithm based on Lagrangian relaxation to solve TT&C scheduling problem.Finally，two scenarios are tested，and obtains the optimal value of TT&C scheduling problem about the two scenarios，the results demonstrate validity of the branch and bound algorithm based on Lagrangian relaxation.

Key words: Lagrangian relaxation, TT&, C scheduling, subgradient optimization, branch and bound

康宁，武小悦. 航天测控调度分枝定界算法[J]. 计算机工程与应用, 2011, 47(31): 17-19.

KANG Ning，WU Xiaoyue. Branch and bound algorithm for TT&C scheduling[J]. Computer Engineering and Applications, 2011, 47(31): 17-19.

[1]	刘悦1，谢谢2. 求解动态停泊计划问题的拉格朗日松弛算法[J]. 计算机工程与应用, 2013, 49(5): 241-247.
[2]	刘山1，顾晔倩1，李雨石1，曹盛文1，刘轩2. 拉格朗日松弛的无人机路径规划[J]. 计算机工程与应用, 2012, 48(27): 233-238.
[3]	晏鹏宇,车阿大,杨乃定,钟娜. 多工件类型的无等待机器人制造单元调度研究[J]. 计算机工程与应用, 2009, 45(9): 13-17.
[4]	杜廷松¹,费浦生²,蹇继贵¹. 非凸二次规划全局极小问题的新型分枝定界算法[J]. 计算机工程与应用, 2008, 44(17): 49-52.
[5]	陶羿¹，朱建青¹，李明². 基于改进遗传算法的物流中心选址优化[J]. 计算机工程与应用, 2007, 43(25): 221-223.
[6]	孙玲，李铁克. 基于约束传播的HFS调度研究[J]. 计算机工程与应用, 2007, 43(19): 7-9.