数据驱动的多星任务网络预测调度算法

多星任务调度是具有NP-hard特性的优化问题,随着卫星资源规模和任务需求规模的双重增长,传统调度方法求解效率不高.在轨卫星在常年运行过程中积累了丰富的调度数据.针对大规模多星任务调度场景,建立多星多波束任务调度模型,并提出数据驱动的多星任务网络预测调度算法对其求解.以分割的思想,实现多星场景下任务可调度性预测.从历史调度数据中,提取设定的3个静态特征和5个动态特征,构建并训练预测网络,预测任务被不同卫星完成的概率,并以冲突避免、负载均衡等为原则,得到初始任务和资源卫星的分配方案.进一步设计双链结构的进化算法,以双链编码形式表征上述关系,配合设计的交叉、修复等进化算子,优化初始方案中的任务序列与资源分配关系,输出最终任务调度方案.仿真结果表明,与改进蚁群算法、混合遗传算法和数据驱动并行调度算法相比,所提出算法在运行时间、方案收益和卫星负载均衡3方面均有较好的表现.

Data-driven based network predictive scheduling algorithm for multi-satellite tasks

The multi-satellite task scheduling problem is an optimization problem with NP-hard characteristics. Facing the growth of satellite resource scale and task demand scale, the traditional scheduling method is not efficient. In-orbit satellites have accumulated rich scheduling data during their perennial operation. Considering the large-scale multi-satellite task scheduling scenario, a multi-satellite multi-beam task scheduling model is established, and a data-driven based network predictive scheduling algorithm for multi-satellite tasks is proposed. With the idea of segmentation, task schedulability prediction in multi-satellite scenarios is realized. The designed 3 static features and 5 dynamic features are extracted from the historical scheduling data to build and train the prediction network that can be used to predict the probability of tasks being completed by different satellites, and the initial allocation scheme for tasks and resource satellites is obtained based on the principles of conflict avoidance and load balancing. We further design an evolutionary algorithm with a double-chain structure, which characterizes the above relationship. The algorithm contains evolutionary operators such as designed crossover and repair, optimizes the tasks sequence and resources allocation relationship in the initial scheme, and outputs the final task scheduling scheme. The simulation results show that, compared with the improved ant colony optimization algorithm, hybrid genetic algorithm and data-driven parallel scheduling approach, the proposed algorithm has better performance in three aspects: running time, scheme revenue and satellite load balancing.