有新任务插入的多星动态调度模型与算法研究

Research on Model and Algorithm of Multi-satellites Dynamic Scheduling with New Tasks Insertion

对地观测卫星动态调度问题是一类复杂的调度问题。在对动态调度的要求进行分析的基础上,针对有新任务插入的多星动态调度问题的特点,建立了多星动态调度模型,提出了一种基于自由度规则的动态启发式求解算法。分别设计了基于最大自由度的退出启发式规则和基于自由度比例的退出启发式规则,采用深度有限搜索策略进行迭代搜索。仿真实例分析表明,基于自由度规则的动态启发式求解算法能够较好地解决有新任务插入的多星动态调度问题。

The problem of multi-satellites dynamic scheduling concerning earth observing is very complex. Considering the characteristic of the problem of multi-satellites dynamic scheduling with new tasks insertion, a dynamic scheduling model was established based on detailed analysis of the demands for dynamic scheduling and a flexibility-based dynamic heuristic algorithm was proposed. The max-flexibility based heuristic rule and the flexibility proportion based heuristic rule for retraction were designed while the depth-bounded iterative search strategy was adopted. Simulation results show that the flexibility-based dynamic heuristic algorithm performs well for the problem of multi-satellites dynamic scheduling with new tasks insertion.