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

针对多卫星成像和多地面站数传并存的对地成像调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种数传时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆随机邻域搜索,在置换空间上进行搜索.仿真计算表明,随机邻域搜索可以增强遗传算法的局部搜索能力,搜索结果平均获得了4.64%的改进.

On permutation-based integrated scheduling for earth observing system

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%.