摘要
成像调度算法是卫星成像规划中的关键部分之一。建立了卫星成像调度问题的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...
出处
《宇航学报》
EI
CAS
CSCD
北大核心
2008年第2期694-699,共6页
Journal of Astronautics
基金
国家自然科学基金(60604035)
国家863重点项目(2007AA120202)
国家863高技术研究发展项目(2007AA12Z229)
关键词
卫星成像调度
0-1整数规划
拉格朗日松弛
次梯度优化
最大分支算法
Satellite imaging scheduling problem
0-1 integer programming
Lagrangian relaxation
Subgradient optimization
Max weighted component algorithm
