Exact and inexact scheduling algorithms for multiple earth observation satellites under uncertainties of clouds

Jianjiang Wang, Erik Demeulemeester, Dishan Qiu and Jin Liu

No 501840, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: Most earth observation satellites (EOSs) are equipped with optical sensors, which cannot see through clouds. Hence, many observations will be useless due to the presence of clouds. In this work, in order to improve the possibility of completing the tasks under uncertainties of clouds, we take the scheduling of each task to multiple resources into account and establish a novel non-linear mathematical model. To solve the problem efficiently under different scenarios, we propose an exact algorithm and some heuristic algorithms. With respect to the exact algorithm, we divide the complicated problem into a master problem and multiple subproblems, with a subproblem for each resource. A labeling-based dynamic programming algorithm is proposed to solve each subproblem. Afterwards, based on the solutions of the subproblems, we develop an enumeration algorithm to solve the master problem. Furthermore, we design five heuristics to solve the large-scale problems that generally fail to be solved by the exact algorithm due to the large space complexity. Experimental results show that the solutions of our model perform better than those of previous studies, and we also reveal the strengths and weaknesses of the proposed algorithms while solving different size instances.

Keywords: Earth observation satellites; Uncertainties of clouds; Model decomposition; Enumeration; Dynamic programming; Heuristic (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1514

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/325798 Exact and inexact scheduling algorithms for multiple earth observation satellites under uncertainties of clouds (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ete:kbiper:501840

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB (ebib@kuleuven.be).