Search

Abstract System disturbances, such as the change of required service durations, the failure of resources, and temporary tasks during the scheduling process of data relay satellite network (DRSN), are difficult to be predicted, which may lead to unsuccessful scheduling of tasks. A high-efficiency and robust DRSN calls for smarter and more flexible disturbances elimination strategies. Here, we unify the above three system disturbances as temporary task arrival and extend the static scheduling model of DRSN. Specifically, we derive and define a scheduling model that unifies the static scheduling and dynamic scheduling processes. Meanwhile, we propose a k-step dynamic scheduling algorithm considering breakpoint transmission (k-steps-BT) to solve the above model. Based on the principle of backtracking algorithm and search tree, k-steps-BT can eliminate disturbances quickly by rescheduling tasks and can determine the rescheduling scheme when temporary tasks arrive. Finally, extensive experiments are carried out to verify the proposed model and algorithm. The results show that the proposed model and algorithm can significantly improve the task completion rate of dynamic scheduling without drastic adjustments to the static scheduling scheme.