对地观测卫星任务规划的启发式动态调整算法

针对对地观测卫星任务规划,分析了单个资源失效与多个高优先级任务动态插入情况下已有任务规划方案的动态调整问题。以最大化规划方案任务权值总和为优化目标,提出了基于任务替换的启发式动态调整算法,包括选择替换任务的五种启发式策略:最大灵活度、最小冲突集、最小争议部分、区间剪枝以及任务剪枝策略。分析了影响动态调整算法运行效率的两个关键因素:冲突任务集与动态搜索深度。采用任务重规划率、规划权值变化率与算法运行时间三项指标考察算法效果,通过仿真实验验证了算法的可行性和有效性。

Heuristic dynamic adjust of task scheduling for earth observing satellite

The dynamic adjust problem of task scheduling for multi-earth observing satellite is analyzed,in cases of single resource fail and multi-prior tasks’dynamic insertion.The optimizing objective is to maximize the sum of all scheduled tasks. The heuristic dynamic adjust algorithm has been proposed based on task swapping,including five heuristic strategies to choosing swapped task：maximum flexibility,minimum conflict set,minimum contention,interval prune and task prune.Two critical elements that impact efficiency of the algorithm have been analyzed also.Three indices,including re-scheduling ratio,change ratio of sum weight and total running time are deployed to check the result of this algorithm;the feasibility and effectiveness have been tested through simulation,and promised result is fulfilled.