Reproducible Baselines and Execution Verification for Earth Observation Satellite Constellation Scheduling

Abstract

The Earth Observation Satellite Scheduling Problem (EOSSP) has seen significant algorithmic advances, yet the lack of standardized, open-source benchmarks has hindered fair comparison across studies. Recent large-scale benchmark suites have begun addressing this gap by providing high-fidelity simulation environments, but these frameworks typically focus on evaluating sophisticated methods, with limited systematic characterization of simple, reproducible baselines. This paper presents an open-source, modular scheduling framework that (1) provides complete implementations of FIFO (First-In-First-Out) and priority-based greedy heuristics as reproducible baselines, (2) offers a lightweight, extensible platform for rapid prototyping of scheduling algorithms, and (3) systematically characterizes the performance of these baselines across 50 synthetically generated test instances spanning five scales from 10 to 1,000 tasks. We formalize the scheduling problem incorporating rest-to-rest attitude manoeuvre dynamics, including angular velocity and acceleration limits, along with energy and storage constraints. Running the framework's own reference implementation surfaced two concrete defects worth reporting in their own right: a discontinuity in the originally specified slew-time kinematic model at the boundary between the triangular and trapezoidal velocity profiles, and a single-satellite scheduling gap that left additional constellation satellites unused in multi-satellite scenarios. Both are corrected here, and the corrected framework, including problem instance generators, evaluation metrics, and the two fixes, is released as open-source software. On the instances tested, priority-based greedy scheduling improves total scheduled priority over FIFO by 65 to 151 percent depending on scale, while achieving only 51.1 percent of the provably optimal objective value on small instances. This gap is reported transparently not to diminish the heuristic’s practical utility, but to quantify the headroom available for more sophisticated methods relative to the simplest viable baseline.