Satellite Resource Scheduling: Compaction Strategies for Genetic Algorithm Schedulers

The United States Naval Research Laboratory is currently using permutation-based genetic algorithms for large-scale satellite resource scheduling. This is a real-world, deployed application. The permutations must be mapped to a Gantt chart representing the final schedule. How this mapping is done can have a significant impact on the ability of the search algorithm to discover high-quality solutions. We present new work that uses compaction strategies in combination with genetic algorithms to construct less fragmented schedules. A schedule with “fewer holes” should also translate into better resource utilization. We show that this is indeed the case. This work is impactful because this strategy can be used to improve all genetic algorithm schedulers.