A branch-and-price algorithm for energy aware task scheduling of constellations of nanosatellites

This paper presents a branch-and-price algorithm for solving the Optimal Network 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, augmented with dual stabilization techniques to improve convergence. Comprehensive computational experiments on realistic instances derived from nanosatellite operations demonstrate the effectiveness of the algorithm. 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 work provides a practical framework for optimizing task scheduling in modern satellite constellations, with direct applications in Earth observation, telecommunications, and scientific missions. • Two Dantzig-Wolfe decompositions for satellite scheduling: naive vs. structured. • DP algorithm for constellation-aware pricing with cross-satellite constraints. • Branch-and-price with stabilization, strong branching, and MILP heuristics.