A Lagrangian relaxation-based heuristic algorithm for multiple agile earth observation satellite scheduling with time-dependent constraint

The Multi-Agile Earth Observation Satellite Scheduling Problem (MAEOSSP) is a complex NP-hard optimization problem, characterized by resource constraints and highly nonlinear, time-dependent constraints. To address this challenge, we propose a Lagrangian Relaxation-based Heuristic (LRD-H) algorithm, a hybrid approach that integrates mathematical decomposition with tailored heuristics. The framework first employs Lagrangian Relaxation to decompose the MAEOSSP into independent single-satellite subproblems, which are solved by an efficient heuristic. Subsequently, it leverages dual information to construct high-quality feasible solutions, which are then enhanced by an iterative improvement procedure. Additionally, we provide a theoretical analysis demonstrating that the expected quality of our algorithm’s solutions monotonically improves with the computational effort allocated to the subproblem solver. Finally, extensive computational experiments show that LRD-H provides strong dual values for quality estimation and achieves significantly better solution quality compared to state-of-the-art benchmarks, especially on large-scale scenarios. Detailed ablation study empirically validates the critical role of our dual-information-guided solution construction and priority-aware improvement heuristics.