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.