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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (30): 241-245.

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

张利宁1，黄小军1，邱涤珊1，李皓平2

1.国防科学技术大学信息系统与管理学院，长沙 410073
2.北京市海淀区947信箱9分箱，北京 100191

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-10-21 发布日期:2011-10-21

Heuristic dynamic adjust of task scheduling for earth observing satellite

ZHANG Lining1，HUANG Xiaojun1，QIU Dishan1，LI Haoping2

1.College of Information System and Management，National University of Defense Technology，Changsha 410073，China
2.Sub-post Box #9，Post Box #947，Haidian District，Beijing 100191，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-10-21 Published:2011-10-21

摘要/Abstract

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

关键词: 对地观测卫星, 任务规划, 资源失效, 动态任务插入, 启发式算法

Abstract: 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.

Key words: earth-observing satellite, task scheduling, resource fail, dynamic task insertion, heuristic algorithm

张利宁1，黄小军1，邱涤珊1，李皓平2. 对地观测卫星任务规划的启发式动态调整算法[J]. 计算机工程与应用, 2011, 47(30): 241-245.

ZHANG Lining1，HUANG Xiaojun1，QIU Dishan1，LI Haoping2. Heuristic dynamic adjust of task scheduling for earth observing satellite[J]. Computer Engineering and Applications, 2011, 47(30): 241-245.

[1]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[2]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[3]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[4]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[5]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[6]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[7]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[8]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.
[9]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[10]	刘竹松，李生. 正余混沌双弦鲸鱼优化算法[J]. 计算机工程与应用, 2018, 54(7): 159-163.
[11]	王长宝1，杨习贝1，2，窦慧莉1，陈向坚1，王平心3. 邻域决策错误率的局部约简方法研究[J]. 计算机工程与应用, 2018, 54(6): 95-99.
[12]	吴伟民，李泽熊，林志毅，吴汪洋，方典禹. 飞蛾纵横交叉混沌捕焰优化算法[J]. 计算机工程与应用, 2018, 54(3): 136-141.
[13]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[14]	徐雪松1，徐歆尧2. 一种多结构数据的同步拟合方法[J]. 计算机工程与应用, 2017, 53(6): 73-79.
[15]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.