  Satellite observation scheduling plays a significant role in improving the
efficiency of Earth observation systems. To solve the large-scale
multi-satellite observation scheduling problem, this paper proposes an ensemble
of meta-heuristic and exact algorithm based on a divide-and-conquer framework
(EHE-DCF), including a task allocation phase and a task scheduling phase. In
the task allocation phase, each task is allocated to a proper orbit based on a
meta-heuristic incorporated with a probabilistic selection and a tabu mechanism
derived from ant colony optimization and tabu search respectively. In the task
scheduling phase, we construct a task scheduling model for every single orbit,
and use an exact method (i.e., branch and bound, B&B) to solve this model. The
task allocation and task scheduling phases are performed iteratively to obtain
a promising solution. To validate the performance of EHE-DCF, we compare it
with B&B, three divide-and-conquer based meta-heuristics, and a
state-of-the-art meta-heuristic. Experimental results show that EHE-DCF can
obtain higher scheduling profits and complete more tasks compared with existing
algorithms. EHE-DCF is especially efficient for large-scale satellite
observation scheduling problems.
