A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds

Most earth observation satellites (EOSs) are equipped with optical sensors, which cannot see through clouds. Hence, observations are significantly affected and blocked by clouds. In this work, with the inspiration of the notion of a forbidden sequence, we propose a novel assignment formulation for EOS scheduling. Considering the uncertainties of clouds, we formulate the cloud coverage for observations as stochastic events, and extend the assignment formulation to a chance constraint programming (CCP) model. To solve the problem, we suggest a sample approximation (SA) method, which transforms the CCP model into an integer linear programming (ILP) model. Subsequently, a branch and cut (B&C) algorithm based on lazy constraint generation is developed to solve the ILP model. Finally, we conduct a lot of simulation experiments to verify the effectiveness and efficiency of our proposed formulation and algorithm.