  Efficient scheduling is of great significance to rationally make use of
scarce satellite resources. Task clustering has been demonstrated to realize an
effective strategy to improve the efficiency of satellite scheduling. However,
the previous task clustering strategy is static. That is, it is integrated into
the scheduling in a two-phase manner rather than in a dynamic fashion, without
expressing its full potential in improving the satellite scheduling
performance. In this study, we present an adaptive Simulated Annealing based
scheduling algorithm aggregated with a dynamic task clustering strategy (or
ASA-DTC for short) for satellite observation scheduling problems (SOSPs).
First, we develop a formal model for the scheduling of Earth observing
satellites. Second, we analyze the related constraints involved in the
observation task clustering process. Thirdly, we detail an implementation of
the dynamic task clustering strategy and the adaptive Simulated Annealing
algorithm. The adaptive Simulated Annealing algorithm is efficient, with the
endowment of some sophisticated mechanisms, i.e. adaptive temperature control,
tabu-list based revisiting avoidance mechanism, and intelligent combination of
neighborhood structures. Finally, we report on experimental simulation studies
to demonstrate the competitive performance of ASA-DTC. Moreover, we show that
ASA-DTC is especially effective when SOSPs contain a large number of targets or
these targets are densely distributed in a certain area.

Artificial Intelligence;Computational Engineering, Finance, and Science