A Simulated Annealing Algorithm with Tabu List for the Multi-Satellite Downlink Schedule Problem Considering Waiting Time

Abstract

In the multi-satellite and multi-ground station downlink task scheduling problem, the waiting time from the proposal of the task to the execution will affect its validity. If the satellite has multiple communicable ground stations when the downlink task is proposed, the selection problem needs to be solved first. After the selection, since the available time conflict between tasks of different satellites for the same ground station, the specific start time should be determined. To reduce the waiting time, a simulated annealing algorithm with a tabu list and start time decision (SATLD) is proposed. This method uses a two-stage scheduling strategy. In the first stage, the improved simulated annealing algorithm based on a tabu list is used to select the downlink ground station. The second stage combines downlink scheduling algorithm based on task arrival time (DSA-AT) method and downlink scheduling algorithm based on task requirement time (DSA-RT) method to determine the specific start time of each task of a single ground station. Simulation analysis prove the method has better selection efficiency of downlink task and shorter total task waiting time, and has practical value.

Keywords

• simulated annealing
• scheduling
• multi-satellite downlink