A Mutation-Based algorithm for deadline-constrained task scheduling in micro-satellite clusters

Task scheduling is one of the core steps to effectively utilize the resources of distributed systems. The complexity of the problem increases when task scheduling is to be done in micro-satellite clusters, where tasks should be completed punctually to meet user-defined deadlines and satisfy various resource constraints. In this paper, a novel Mutation-Based Scheduling Algorithm, namely MBSA, is proposed. An initial solution of MBSA is obtained by an improved priority-based greedy algorithm. Then iterative mutation operations are introduced to make the schedule effectively converge to the optimal solution or approximate optimal solution. Additionally, a hierarchical task scheduling model is designed for micro-satellite clusters, and our MBSA is applied to the global-scheduling level. The performance of our algorithm is illustrated by comparing with classic EDF and LLF scheduling algorithms. According to the simulation results, our algorithm outperforms the traditional algorithms with higher task completion rate and also provides a tradeoff between the schedule length and load balance.