A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service

Cezar Antônio Rigo, Laio Oriel Seman, Eduardo Camponogara, Edemar Morsch Filho, Eduardo Augusto Bezerra and Pedro Munari

European Journal of Operational Research, 2022, vol. 303, issue 1, 168-183

Abstract: Satellite scheduling is concerned with the assignment of start and finish times for tasks while considering the mission objective, available resources, and constraints. This scheduling problem is especially critical in nanosatellites, given that resources are more scarce than in traditionally-sized spacecrafts. Despite having its own set of constraints and being increasingly deployed, nanosatellite task scheduling has received little attention in the literature. In this paper, we advance the state-of-the-art by devising an effective solution approach for a nanosatellite task scheduling problem. We resort to the Dantzig-Wolfe decomposition to explore the special structure of an existing mixed-integer linear programming (MILP) formulation, decomposing it by tasks, which results in a novel profile-based formulation for the problem. To solve the resulting formulation, we propose a branch-and-price (B&P) algorithm that is suitable for the scheduling of a large number of tasks over an expanded time horizon. Furthermore, we design a dynamic programming algorithm for generating feasible schedules instead of solving the pricing subproblem with an MILP solver, among other algorithmic strategies. Computational experiments using instances that represent realistic scenarios showed that the B&P algorithm is considerably more efficient in solving large instances when compared to commercial solvers. Overall, the proposed solution strategy empowers the decision maker to plan more complex missions, in an optimal or nearly-optimal manner and within a reasonable computation time.

Keywords: Scheduling; Dantzig-Wolfe decomposition; Branch and price; Nanosatellite; Quality of service (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722001606
Full text for ScienceDirect subscribers only

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:eee:ejores:v:303:y:2022:i:1:p:168-183

DOI: 10.1016/j.ejor.2022.02.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().