摘要
针对NP难解的多星成像过度调度问题,从置换空间到问题空间的映射方法和置换空间搜索算法两方面进行了研究。基于资源优先卫星分配算法,建立了置换空间到问题空间的映射关系,以在置换空间优化多星成像调度。提出了一种分散式随机搜索算法,基于有记忆随机邻域搜索,在置换空间上搜索产生优化调度的置换序列。实验表明,所提算法相对模拟退火算法平均获得3.12%的改进。
Multi-satellites imaging scheduling is a NP-hard oversul）scribed scheduling problem. Our work focuses on permutation scheduling algorithms and permutation searching algorithms. A resource preempted satelliles assign algorithm is put forward to build the mapping from permutation space to scheduling space, which can help to optimizing the scheduling problem in a permutation space. A scatter stochastic search method is designed to carry out the search procedure for optimal permutation. This new algorithm uses a stochastic neighborhood search algorithm with memory as local search method, which enhances the local search ability. Computational results show that our method can make an average improvement of about 3.12% over the simulated anneal- ing algorithm.
出处
《宇航学报》
EI
CAS
CSCD
北大核心
2009年第6期2277-2284,共8页
Journal of Astronautics
基金
国家自然科学基金项目(60604035)
国家863高技术研究发展项目(2007AA12Z229)
国家科技支撑计划课题(2006BAG01A07)
关键词
多星成像
过度调度
置换表示
分散式搜索
随机邻域搜索
Multi-satellites imaging
Oversubscribed scheduling
Permutation-based representation
Scatter search
Stochastic neighborhood search
