Study on Heuristic Algorithm for Dynamic Scheduling Problem of Earth Observing Satellites

Abstract

Earthserving Satellites are traditionally scheduled in a static way. It assumes that the information about the problem is complete and the environment is static. In practice, the satellites are working in a complex environment, faced with different uncertainties and perturbations such as unforeseen cloud cover, unanticipated changes in satellite resources, or arriving of new tasks. It is then necessary to schedule the Earth Observing Satellites in a dynamic way. On the basis of detailed analysis of these dynamic factors, we describe the problem with a unified form of inserting new tasks. Considering the characteristic of the dynamic scheduling problem of Earthserving Satellites in this paper, we propose a rule-based heuristic algorithm, and design a heuristic rule of max-contention for retraction and a heuristic rule of min-occupation for insertion. Finally, an example is given to validate the algorithm. Numerical results indicate that this algorithm can guarantee both efficiency and stability of the schedule.