A robust algorithm for deadline-constrained task scheduling in small satellite clusters
Jin Wu, Lixiang Liu, Xiaohui Hu · 2016
Task scheduling is one of the core steps to efficiently complete space missions with limited resources in small satellite clusters. This problem becomes more complicated when taking various uncertainties into consideration. In this paper, a heuristic robust task scheduling algorithm (RTSA) that handles performance variations of small satellites and task failures has been proposed. An initial solution is obtained by grouping tasks into partial critical paths (PCPs). Then three heuristic strategies and an evaluation function are introduced to improve the schedule iteratively. During this process, the robustness of RTSA is achieved by adding slack time and duplicating critical tasks judiciously. By simulating the Small Satellite Cluster environment and building task failure model, experimental results show that RTSA provides robust and fault-tolerant schedule while minimizing the makespan.