考虑多滑动窗口的中继卫星调度模型及启发式算法-《郑州大学学报(工学版)》

文章信息/Info

Title:: Scheduling Model and Heuristic Algorithm for Tracking and Data Relay Satellite Considering Multiple Slide Windows

作者:: 何敏藩; 朱燕麒; 贾学卿; 1.佛山科学技术学院数学与大数据学院,广东佛山,528000;2.北京市遥感信息研究所,北京,100085;3.国防科技大学电子科学学院,湖南长沙,410073

Author(s):: He Minfan1; Zhu Yanqi2; Jia Xueqing3; 1. School of Mathematics and Big Data, Foshan University of Science and Technology, Foshan, Guangdong, 528000; 2. Beijing Institute of Remote Sensing Information, Beijing, 100085; 3. School of Electronic Science, National University of Defense Technology, Changsha, Hunan, 410073

摘要:: 高效的调度方法是提高中继卫星系统应用效能的关键。中继卫星调度主要是要根据用户提交的任务申请信息，科学合理地分配中继卫星系统资源，最大程度满足各项任务需求，为中继卫星系统编制最优工作计划。考虑中继业务中的多滑动时间窗口需求，构建了中继卫星调度问题的数学规划模型，以最大化任务完成率和用户期望满足度为目标，以任务需求约束、资源使用约束作为约束条件。设计了基于时间自由度的启发式算法，该算法包括了任务时间自由度评价、任务资源匹配、任务插空和资源更新4个算子。最后，通过大规模仿真实验验证了算法的有效性。

Abstract:: Efficient scheduling algorithm plays a key role in improving the efficacy of tracking and data relay satellite system (TDRS). Scheduling of TDRS aims to scientifically allocate TDRS resources according to the task application information from the users, such that maximal task requirements are met and the optimal activity schedule is made for the TDRS system. The mathematical model is constructed for the TDRS scheduling problem with the consideration of multiple slide windows in real-world requirements. The objective of the model is to maximize the task completion rate and the expectation satisfaction degree of users. The involved constraints include task requirement constraints and resource using constraints. A heuristic algorithm based on time freedom degree is proposed to solve the model, which includes four operators, i.e., evaluation of the time freedom degree of each task, matching between tasks and resources, task insertion and resource update. At last, extensive experimental simulation demonstrates the effectiveness of the proposed algorithm.