Exact and inexact scheduling algorithms 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, many observations will be useless due to the presence of clouds. In this work, in order to improve the possibility of completing the tasks under uncertainties of clouds, we take the scheduling of each task to multiple resources into account and establish a novel non-linear mathematical model. To solve the problem efficiently under different scenarios, we propose an exact algorithm and some heuristic algorithms. With respect to the exact algorithm, we divide the complicated problem into a master problem and multiple subproblems, with a subproblem for each resource. A labeling-based dynamic programming algorithm is proposed to solve each subproblem. Afterwards, based on the solutions of the subproblems, we develop an enumeration algorithm to solve the master problem. Furthermore, we design five heuristics to solve the large-scale problems that generally fail to be solved by the exact algorithm due to the large space complexity. Experimental results show that the solutions of our model perform better than those of previous studies, and we also reveal the strengths and weaknesses of the proposed algorithms while solving different size instances.