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

《对地观测卫星任务规划的启发式动态调整算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用2011．47(30)241对地观测一p星任务规划的启发式动态调整算法张利宁1，黄小军‘，邱涤珊1，李皓平2ZHANGLining‘，HUANGXiaojunl，OIUDishanl，LIHaopin921．国防科学技术大学信息系统与管理学院，长沙4100732．北京市海淀区947信箱9分箱，北京1001911．CollegeofInformationSystemandManagement，NationalUnivers

2、ityofDefenseTechnology，Changsha410073，China2．Sub-postBox撑9。PostBox≠≠947，HaidianDistrict，Beijing100191，ChinaZHANGLining．HUANGXiaojun。QIUDishan。eta1．Heuristicdynamicadjustoftaskschedulingforearthobservingsatellite．ComputerEngineeringandApplications．2011．47

3、(30)：241-245．Abstract：Thedynamicadjustproblemoftaskschedulingformulti—earthobservingsatelliteisanalyzed，incasesofsinglere-sourcefailandmulti-priortasks’dynamicinsertion．Theoptimizingobjectiveistomaximizethesumofallscheduledtasks．Theheuristicdynamicadjust

4、algorithmhasbeenproposedbasedontaskswapping，includingfiveheuristicstrategiestochoosingswappedtask：maximumflexibility，minimumconflictset，minimumcontention，intervalpruneandtaskprune．Twocrit—icalelementsthatimpactefficiencyofthealgorithmhavebeenanalyzedalso

5、．Threeindices，includingre—schedulingratio，changeratioofsumweightandtotalrunningtimearedeployedtochecktheresultofthisalgorithm；thefeasibilityandef-fectivenesshavebeentestedthroughsimulation，andpromisedresultisfulfilled．Keywords：earth—observingsatellite；ta

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

7、率、规划权值变化率与算法运行时间三项指标考察算法效果，通过仿真实验验证了算法的可行性和有效性。关键词：对地观测卫星；任务规划；资源失效；动态任务插入；启发式算法DOI：10．3778(j．issn．1002．8331．2011．30．065文章编g-：1002．8331(2011)30．0241．05文献标识码：A巾图分类哮：N945l引言对地观测卫星的日常任务规划问题是一类典型的大规模组合优化问题。该问题的最大特点在于卫星在执行某种任务的时候，必须在相应的可视时I'日J窗U之内完成。因此，卫旱调度问题

8、要求不仅要对卫星资源进行分配，还要对卫星可视时间窗U进行分配。是一个包含了两个选择过程的复杂的资源分配I’廿J题。目前对该问题展开的主要研究集中于预先规划，即任务执行启动前的静态规划”‘4，。对于不确定环境F，即任务规划方案的动态调整问题的研究较少。GervardVerfaillie等在文献【5】中提出了一种针对单星有新任务到达的动态凋度问题的求解思路，即新任务能够插入到渊度方案中的条件是：由新任务插入而引起的原方案中的任务变化，仅仅是改变