The Remote Sensing Data Transmission Problem in Communication Constellations: Shop Scheduling-Based Model and Algorithm

Advances in satellite miniaturisation have led to a steep rise in the number of Earth-observation platforms, turning the downlink of the resulting high-volume remote-sensing data into a critical bottleneck. Low-Earth-Orbit (LEO) communication constellations offer a high-throughput relay for these data, yet also introduce intricate scheduling requirements. We term the associated task the Remote Sensing Data Transmission in Communication Constellations (DTIC) problem, which comprises two sequential stages: inter-satellite routing, and satellite-to-ground delivery. This problem can be cast as a Hybrid Flow Shop Scheduling Problem (HFSP). Unlike the classical HFSP, every processor (e.g., ground antenna) in DTIC can simultaneously accommodate multiple jobs (data packets), subject to two-dimensional spatial constraints. This gives rise to a new variant that we call the Hybrid Flow Shop Problem with Two-Dimensional Processor Space (HFSP-2D). After an in-depth investigation of the characteristics of this HFSP-2D, we propose a constructive heuristic, denoted NEHedd-2D, and a Two-Stage Memetic Algorithm (TSMA) that integrates an Inter-Processor Job-Swapping (IPJS) operator and an Intra-Processor Job-Swapping (IAJS) operator. Computational experiments indicate that when TSMA is initialized with the solution produced by NEHedd-2D, the algorithm attains the optimal solutions for small-sized instances and consistently outperforms all benchmark algorithms across problems of every size.