Most earth observation satellites (EOSs) are equipped with optical sensors, which cannot see through the 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.