Ensemble of meta-heuristic and exact algorithm based on the divide and conquer framework for multi-satellite observation scheduling

• Main Authors: Wu, Guohua, Luo, Qizhang, Du, Xiao, Chen, Yingguo, Suganthan, Ponnuthurai Nagaratnam, Wang, Xinwei
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2022
• Subjects: Engineering::Electrical and electronic engineering; Ensemble Algorithms; Meta-Heuristics Algorithms
• Online Access: https://hdl.handle.net/10356/162516
• Institution: Nanyang Technological University

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.