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.

中文翻译：

---

用于多模式纳米卫星任务调度的嵌套 branch-and-price 具有内点正则化和 GPU 加速

纳米卫星的能力受到其有限的功率可用性和尺寸的限制，这给任务规划和作带来了挑战。本研究通过在调度过程中引入多模式功能来解决离线纳米卫星任务调度 （ONTS） 问题，增强了其与更现实、适应性更强和更稳健的任务规划的相关性。我们为这个问题提出了一个混合整数线性规划 （MILP） 模型，该模型可以适应多种作模式中的常规资源和时间限制。MILP 模型得到了改进，有效不等式结合了辅助变量以及通过提升程序增强的多模式覆盖切割。此外，我们引入了一种嵌套分支和价格 （NB&P） 算法，该算法通过结合用于处理分层调度的双级优化结构来增强标准的分支和价格方法。这种双重框架同时促进了任务分配和模式选择，采用受双重价格影响的动态列生成，逐步优化任务计划以实现最优。此外，增强的内点方法已有效地适应处理大规模实例，与利用 CUDA 技术的 GPU 加速动态编程解决方案保持一致。实证评估表明，改进的 MILP 方法与 NB&P 算法相结合，显著提高了计算效率，计算时间缩短了 629 倍，并始终如一地实现了零间隙解决方案。