An Efficient Large Neighborhood Search Algorithm for Multi-level Constellation Scheduling Problem.

In this paper, we investigate the multilevel constellation scheduling problem (MLCSP). The MLCSP asks for scheduling time intervals within three different agents, the user satellite, the control satellites, and the ground station. Specifically, the user satellites transfer data to the control satellites, the control satellites then transmit it to the ground stations, and the objective is to schedule all the time intervals so that the number of completed tasks required by the user satellites is maximized. Compared with the setting of existing constellation scheduling problems, the problem is distinguished by its multiple scheduling role and multilevel architecture. Clearly, MLCSP is an important optimization problem in large-scale heterogeneous constellation scheduling. To solve this problem, we build both integer linear programming and constraint programming models to obtain the exact solution to MLCSP. Due to the computation limitation of exact approaches in the real-world environment, we further propose a large neighborhood search algorithm (LNSA) to practically solve the problem. Our experimental results indicate that our algorithms are very effective in benchmarks. Specifically, the LNSA can also obtain optimal solutions for large instances in practice. [ABSTRACT FROM AUTHOR]