Proactive Scheduling Algorithms for Multiple Earth Observation Satellites Under Uncertainties of Clouds

This paper investigates the scheduling of multiple earth observation satellites (EOSs) under uncertainties of clouds. Firstly, we formulate the presence of clouds as stochastic events, transforming the problem into a stochastic programming problem. Based on different perspectives, we model the problem mathematically using both an expectation model and a chance constrained programming (CCP) model. Afterwards, for the first time, we employ a Dantzig-Wolfe decomposition and a column generation technique for the uncertain scheduling of EOSs. With respect to the expectation model, we devise a branch-and-price algorithm to solve the model optimally and efficiently. On the other hand, we first reformulate the CCP model as a mixed integer programming (MIP) model using sample approximation. Subsequently, considering the difficulties and the infeasibility of the branch-and-price algorithm for this MIP model, we suggest a column generation based heuristic algorithm to get “good” feasible solutions. By numerous simulation experiments, we verify the effectiveness and test the performance of our proposed formulations and approaches.