置换表示方法求解多卫星多地面站调度问题  

On permutation-based integrated scheduling for earth observing system

作　　者：靳肖闪[1] 李军[1] 王钧[1] 景宁[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,湖南长沙410073

出　　处：《控制理论与应用》2010年第4期407-414,共8页Control Theory & Applications

基　　金：国家自然科学基金资助项目(60604035);国家863高技术研究发展项目(2007AA12Z229);国家科技支撑计划课题(2006BAG01A07)

摘　　要：针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.The integrated scheduling for earth observing system deals with multiple imaging satellites and ground stations simultaneously;it is a NP-hard oversubscribed scheduling problem involving lots of constraints.Permutationbased methods are presented to solve this complicated optimization problem.First,the integrated scheduling is expressed as permutation sequences,and a data-transfer-time-window preempted algorithm is put forward as the schedule builder,which ensures the searching for optimal schedules.Next,a genetic stochastic search method is designed to search for optimal permutations by using the permutation schedule builder and the stochastic neighborhood search algorithm with memory.Finally,the computational results on several scheduling instances show that our method enhances the local search ability for genetic search with an improvement-rate of 4.64%.

关 键 词：多卫星多地面站调度 置换表示 遗传算法 随机邻域搜索 

分 类 号：V556[航空宇航科学与技术—人机与环境工程]