Ensemble of meta-heuristic and exact algorithm based on the divide and conquer framework for multi-satellite observation scheduling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912091412103168 |
|---|---|
| author | Wu, Guohua Luo, Qizhang Du, Xiao Wang, Xinwei Chen, Yinguo Suganthan, Ponnuthurai Nagaratnam |
| author_facet | Wu, Guohua Luo, Qizhang Du, Xiao Wang, Xinwei Chen, Yinguo Suganthan, Ponnuthurai Nagaratnam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_03644 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Ensemble of meta-heuristic and exact algorithm based on the divide and conquer framework for multi-satellite observation scheduling Wu, Guohua Luo, Qizhang Du, Xiao Wang, Xinwei Chen, Yinguo Suganthan, Ponnuthurai Nagaratnam Instrumentation and Methods for Astrophysics 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. |
| title | Ensemble of meta-heuristic and exact algorithm based on the divide and conquer framework for multi-satellite observation scheduling |
| topic | Instrumentation and Methods for Astrophysics |
| url | https://arxiv.org/abs/2007.03644 |