基于拉格朗日松弛与最大分支算法的卫星成像调度算法  

An Algorithm for Satellite Imaging Scheduling Based on Lagrangian Relaxation and Max Weighted Component Algorithm

作　　者：靳肖闪[1] 李军[1] 刘湘辉[1] 郭玉华[1] 景宁[1] 

机构地区：[1]国防科技大学电子科学与工程学院,长沙410073

出　　处：《宇航学报》2008年第2期694-699,共6页Journal of Astronautics

基　　金：国家自然科学基金(60604035);国家863重点项目(2007AA120202);国家863高技术研究发展项目(2007AA12Z229)

摘　　要：成像调度算法是卫星成像规划中的关键部分之一。建立了卫星成像调度问题的0-1整数规划模型,该问题具有NP完全特性。提出了一种基于拉格朗日松弛与最大分支算法的多项式时间复杂度的优化算法。该算法可以计算出接近最优解的上界及可行解,并给出可行解的优化度。基于该算法提出了一种先验可行解条件下改进上界及可行解的二次优化算法。实验结果表明,该算法在时间性、优化度等方面取得满意的结果。Scheduling algorithm is key to satellite imaging planning problem.This paper formulates the satellite imaging scheduling problem as a 0-1 integer programming model,which is NP complete.To solve this problem,a subgradient optimization algorithm based on max weighted component algorithm is proposed in the paper.This algorithm has an O(N2)-complexity,and it is convergent.A good feasible solution and upper bound can be computed by it.A secondary optimization algorithm can improve the feasible solution and upper...

关 键 词：卫星成像调度 0-1整数规划 拉格朗日松弛 次梯度优化 最大分支算法 

分 类 号：TP70[自动化与计算机技术—检测技术与自动化装置]