Exact and Heuristic Scheduling Algorithms for Multiple Earth Observation Satellites Under Uncertainties of Clouds

Most earth observation satellites are equipped with optical sensors, which cannot see through clouds. Hence, many observations will be useless due to the presence of clouds. In this paper, we study the scheduling problem of multiple EOSs under uncertainties of clouds. In order to improve the possibility of completing tasks, we take the scheduling of each task to multiple resources (orbits) into account and establish a novel nonlinear mathematical model. To solve the problem efficiently, an exact algorithm based on enumeration is proposed, in which each subproblem is solved by path programming, and all the feasible solutions of subproblems are combined to solve the master problem. Furthermore, three heuristics are designed to solve the large-scale problems. From the experimental results on random samples, it is observed that the solutions of our model perform better than those of the previous studies. Besides, both our exact algorithm and a mixed-integer nonlinear programming solver-Couenne can solve our model optimally for small problems, but our algorithm is more efficient than Couenne. For large-scale problems, we reveal the strengths and weaknesses of the proposed heuristic algorithms while solving different instances of various sizes.

I. Introduction

Earth observation satellite (EOS) scheduling means to allocate the tasks submitted by users to satellites, making the schedule satisfy the operational constraints. Because of some special advantages, e.g., an expansive coverage area, long-term surveillance, a high frequency of repeated observations, accurate and effective information access and unlimited airspace borders, EOSs have been extensively employed in earth resources exploration, nature disaster surveillance, urban planning, crop monitoring, etc. Due to the explosively increased number of applications, the number of satellites, in spite of having increased quickly, is still too limited. Hence, it is nontrivial for EOS scheduling to achieve high observation effectiveness and efficiency.