最小化全局完成时间的成像卫星任务规划算法  

Scheduling Algorithm for Image Satellite to Minimize the Global Make-span

作　　者：张利宁[1] 邱涤珊[1] 李皓平[2] 祝江汉[1] 

机构地区：[1]国防科技大学信息系统与管理学院,长沙410073 [2]北方电子设备研究所,北京100191

出　　处：《小型微型计算机系统》2011年第6期1218-1221,共4页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(97361361)资助

摘　　要：成像侦察卫星任务规划问题是一类典型多约束组合优化问题.最小化全局完成时间是任务规划领域时效性要求较高情况下的一种优化目标.提出一种整合整数规划与约束规划方法,在最小化任务规划方案全局完成时间的目标下,求解成像侦察卫星任务规划问题的组合算法.该算法通过应用Benders分解将原约束整数规划模型划分为主问题与子问题两部分,采用软件MOSEK与GECODE对主、子问题分别求解.根据子问题求解结果生成剪枝约束,返回主问题迭代,直到获得优化解.算法有效性通过仿真实验进行了检验并取得预期效果.Task scheduling for image reconnaissance satellite is a typical combinatorial problem.Minimizing global make-span is a standard optimization objective in task scheduling field.Under this objective,a hybrid algorithm that combined integer programming and constraint programming was proposed in this paper to solve this problem.The constrained integer programming model of this problem was decomposed into master and sub-problem through Benders＇ decomposition;these two parts were solved by the state-of-the-art software MOSEK and GECODE separately.Generated Benders cuts were sent to the master problem for iterative solving process until an optimizing solution obtained.The efficiency of this algorithm was tested by simulation,and promised result was fulfilled.

关 键 词：成像侦察卫星 任务规划 全局完成时间 组合优化 Benders分解 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]