Scheduling multiple agile Earth observation satellites with multiple observations

Earth observation satellites (EOSs) are specially designed to collect images according to user requirements. Agile EOSs (AEOSs), with stronger attitude maneuverability, greatly improve the observation capability, while increasing the complexity of scheduling the observations. In this paper, we address the problem of scheduling multiple AEOSs with multiple observations where the objective function aims to maximize the entire observation profit over a fixed horizon. The profit attained by multiple observations for each target is nonlinear in the number of observations. Our model is a specific interval scheduling problem, with each satellite orbit represented as a machine. A column-generation-based framework is developed for this problem, in which the pricing problems are solved using a label-setting algorithm. Extensive computational experiments are conducted on the basis of one of China’s AEOS constellations. The results indicate that our optimality gap is less than 3% on average, which validates our framework. We also evaluate the performance of the framework for conventional EOS scheduling.