Chain-Splitting-Solving-Splicing Approach to Large-Scale OFISP-Modeled Satellite Range Scheduling Problem

Abstract

The dimension of the operational-fixed-interval-scheduling-problem-modeled (OFISP-modeled) $\mathcal {NP}$ -hard satellite range scheduling problem (SRSP) extends rather than expands especially in large cases. This feature inspires us with the chain-splitting-solving-splicing (CSSS) approach to this OFISP-modeled SRSP under the curse of dimension. To boost the performance for scheduling the large-scale SRSP, we introduce the tricks to the algorithmic design from the inside out. The proposed method splits the original problem to small morsels with chain-splitting (CS) procedure to feed the route-reduction-based dynamic programming (R-DP) with the introduction of a novel scheduling element, the critical resource (CR), to expedite the execution for the optimal subsolution to the subproblem. At last, the standard DP (S-DP) splices the subsolutions into a complete optimal one. We encase the CR-based subproblem solving with the chain splitting and splicing framework. We show that it stunts the exponential explosion in time expenditure greatly with the CP by the mathematical analysis. We justify the efficiency of the proposed method with an application to a large-scale real-world SRSP instance. The proposed CSSS approach outperforms in comparison with several state-of-the-art algorithms. We obtained the optimal solution with the proposed method within reasonable time for the cases up to 3000 jobs. To the best of our knowledge, besides our research, other research into the large-scale SRSP is still absent. This status quo implies the potential of our research as a benchmark case for the would-be comparison with the other future research.

Keywords

• Large-scale
• fixed interval scheduling
• combinatorial optimization
• dynamic programming