Expectation and SAA Models and Algorithms for Scheduling of Multiple Earth Observation Satellites Under the Impact of Clouds

In the explosively increased number of applications of earth observation satellites (EOSs), scheduling is a significative issue to satisfy more requests and obtain a high observation efficiency. This article investigates the scheduling of multiple EOSs under the impact of clouds. First, we formulate the presences of clouds as stochastic events, and propose an expectation model. Afterwards, for the first time, a branch-and-price algorithm based on Dantzig-Wolfe decomposition is devised to solve the model optimally and efficiently. In order to obtain initial columns for column generation, a dynamic programming algorithm and a heuristic algorithm are suggested, respectively. Furthermore, we discuss the impact of clouds in the case of joint probabilities, and establish a sample average approximation (SAA) model accordingly. With respect to the expectation model, numerical experiment results demonstrate the relative dominance of the proposed branch-and-price algorithm in terms of solution time compared to CPLEX. In addition, the solution of the proposed SAA model is proven to be more robust than that of the expectation model.