Dynamic Scheduling for the Satellite Range Scheduling Problem Using Heuristic, Optimization, and AI-Based Methods

This paper presents a unified dynamic scheduling framework for the Satellite Range Scheduling Problem (SRSP), evaluating whether deep reinforcement learning can learn fair scheduling policies without explicit fairness constraints, alongside optimization and heuristic baselines. Four algorithms are compared: a priority-based greedy heuristic, Mixed-Integer Linear Programming (MILP), a Deep Q-Network (DQN), and a Genetic Algorithm (GA), applied to the same problem under identical conditions. The framework is grounded in real Two-Line Element orbital data for operational spacecraft and globally distributed ground stations using SGP4 propagation, with synthetic communication requests spanning six task types generated across three controlled contention levels. All schedulers are evaluated using five metrics: success rate, priority efficiency, task-type breakdown, runtime, and DQN cumulative reward. Results show the greedy scheduler matches the provably optimal MILP in both success rate (83.2%) and priority efficiency (1565) across all contention levels while requiring over 500 times less computation (0.04s vs. 21.2s), demonstrating that the SRSP structure naturally rewards a well-designed heuristic. The DQN matches greedy and MILP success rate but implicitly learns a fairer scheduling policy through reward shaping, outperforming greedy on lower-urgency categories including routine maintenance (80.5% vs. 68.4%) and uplink (81.3% vs. 73.4%) without any explicit fairness constraints. The GA underperformed across all conditions with runtime growing from 1,238s to 3,059s as contention increased. These results establish practical performance bounds for AI and optimization-based schedulers under varying resource contention, supporting a tiered strategy: greedy for real-time decisions, MILP where provable optimality is required, and DQN where equitable task-type coverage is an operational priority. Critically, performance differences are most pronounced under high contention, confirming that meaningful AI/ML algorithm evaluation requires datasets with genuine resource competition. The proposed framework provides a reproducible benchmark extensible to novel scheduling algorithms, alternative reward formulations, and larger constellation deployments.