中文摘要：

针对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.