Nested branch-and-price for multi-mode nanosatellite task scheduling with interior-point regularization and GPU acceleration

Laio Oriel Seman, Cezar Antônio Rigo, Eduardo Camponogara and Pedro Munari

European Journal of Operational Research, 2025, vol. 327, issue 2, 469-490

Abstract: The capabilities of nanosatellites are constrained by their limited power availability and size, which poses challenges for mission planning and operation. This study addresses the Offline Nanosatellite Task Scheduling (ONTS) problem by introducing multi-mode capability into the scheduling process, enhancing its relevance for more realistic, adaptable, and robust mission planning. We propose a Mixed-Integer Linear Programming (MILP) model for this problem that accommodates conventional resource and temporal constraints across multiple operational modes. The MILP model is improved with valid inequalities incorporating auxiliary variables alongside multi-mode cover cuts enhanced with lifting procedures. Furthermore, we introduce a Nested Branch-and-Price (NB&P) algorithm that enhances the standard branch-and-price approach by incorporating a dual-level optimization structure for handling hierarchical scheduling. This dual framework simultaneously facilitates job allocation and mode selection, employing dynamic column generation influenced by dual prices to progressively refine task schedules towards optimality. Additionally, enhanced interior-point methods have been effectively adapted for tackling large-scale instances, aligned with a GPU-accelerated dynamic programming solution utilizing CUDA technology. Empirical evaluations show that the modified MILP approach, combined with the NB&P algorithm, significantly improves computational efficiency, demonstrating up to a 629-fold reduction in computation time and consistently achieving zero-gap solutions.

Keywords: Scheduling; Nanosatellite; Quality of service; Branch-and-price; Integer programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725003881
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:327:y:2025:i:2:p:469-490

DOI: 10.1016/j.ejor.2025.05.020

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 ().