A branch-and-price algorithm for task scheduling of nanosatellite constellations

Abstract

Esta dissertação apresenta um algoritmo branch-and-price para a resolução do problema de Offline Nanosatellite Task Scheduling (ONTS) em constelações de nanossatélites. O algoritmo gerencia de forma eficiente tanto as tarefas de constelação, que podem ser executadas por qualquer satélite, quanto as tarefas específicas de satélite, que devem ser realizadas por satélites designados, considerando simultaneamente restrições críticas de energia. O problema é formulado como um modelo de Programação Linear Inteira Mista (Mixed-Integer Linear Programming, MILP), e uma decomposição de Dantzig-Wolfe é desenvolvida para tratar as restrições de gerenciamento de bateria dos satélites no problema mestre, enquanto as restrições relativas às tarefas e à coordenação da constelação são delegadas aos subproblemas. Um novo algoritmo de programação dinâmica é proposto para resolver o subproblema de precificação das tarefas de constelação, juntamente com técnicas de estabilização dual para melhorar a convergência do processo de geração de colunas. Experimentos computacionais abrangentes, realizados com instâncias realistas derivadas de operações com nanossatélites, demonstram a eficácia do algoritmo. Os resultados mostram que a formulação proposta apresenta desempenho superior quando comparada a uma abordagem naive e a um solver comercial, especialmente em instâncias de grande porte, ao equilibrar de forma eficaz a distribuição da carga de trabalho e o gerenciamento de energia na constelação. Este trabalho fornece uma estrutura prática para a otimização da programação de tarefas em constelações de nanossatélites, com aplicações diretas em observação da Terra, telecomunicações e missões científicas.

Abstract: This dissertation presents a branch-and-price algorithm for solving the Offline Nanosatellite Task Scheduling (ONTS) problem in satellite constellations. The algorithm efficiently manages both constellation tasks that can be performed by any satellite and satellite-specific tasks that must be executed by designated satellites, while considering critical energy constraints. We formulate the problem as a Mixed-Integer Linear Programming (MILP) model and develop a Dantzig-Wolfe decomposition that handles battery management constraints for the satellites at the master level, while addressing constellation-wide coordination requirements in the subproblems. A novel dynamic programming algorithm is proposed to solve the pricing subproblem for constellation tasks, and dual stabilization techniques are used to improve algorithm convergence. Comprehensive computational experiments on realistic instances derived from nanosatellite operations demonstrate the algorithm?s effectiveness. Results show that our structured formulation significantly outperforms a naive approach, particularly for large instances, while effectively balancing workload distribution and energy management across the constellation. This dissertation provides a practical framework for optimizing task scheduling in modern satellite constellations, with direct applications in Earth observation, telecommunications, and scientific missions