电子侦察卫星动态调度问题的快速启发式算法  

Fast Heuristic Algorithm for Electronic Reconnaissance Satellite Dynamic Scheduling Problem

作　　者：黄小军[1] 张利宁[1] 邱涤珊[1] 祝江汉[1] 

机构地区：[1]国防科技大学信息系统与管理学院军事运筹实验室,湖南长沙410073

出　　处：《小型微型计算机系统》2010年第11期2246-2250,共5页Journal of Chinese Computer Systems

基　　金：国家安全重大基础研究项目(61361-01)资助

摘　　要：卫星电子侦察中针对动态突发事件重新制定侦察计划是侦察任务规划所要解决的基本问题.分析导致动态调度的扰动因素,把不同扰动下的动态调度问题归结为一类复杂约束下的任务插入问题.建立混合整数规划模型,提出快速启发式任务插入算法(含三个基本算法——直接插入任务算法、移位插入任务算法和替换插入任务算法);基于初始调度方案的优良特性,极大降低动态调度复杂性.仿真实验表明:该算法能有效解决电子侦察卫星动态调度问题.In the course of electronic reconnaissance, how to redesign the satellite reconnaissance schedule according to the dynamic unexpected incidents is the basic problem of satellite reconnaissance mission planning. Based on the analysis of the disturbance resulting in the dynamic scheduling, the electronic reconnaissance satellite （ ERS ） dynamic scheduling problem under different disturbance was come down to a kind of task insertion problem under complex constraints, and the corresponding mixed integer programming model was formulated. Then a fast heuristic tasks insertion algorithm （ FHTIA ） was proposed to solve the problem. FHTIA comprised three basic operators--directly insert tasks algorithm, shift and insert tasks algorithm, replace tasks algorithm. Taking advantage of the eminent performance, the complexity of the ERS dynamic scheduling problem was reduced greatly. The simulation results showed that FHTIA could solve ERS dynamic scheduling problem effectively and quickly.

关 键 词：卫星动态调度 快速启发式任务插入算法 混合整数规划模型 扰动 

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