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

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

成像侦察卫星任务规划问题是一类典型多约束组合优化问题.最小化全局完成时间是任务规划领域时效性要求较高情况下的一种优化目标.提出一种整合整数规划与约束规划方法,在最小化任务规划方案全局完成时间的目标下,求解成像侦察卫星任务规划问题的组合算法.该算法通过应用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.