Computational complexity of radio-astronomical observation scheduling

Overview & Synopsis

This work tackles the scheduling of radio-astronomical observations. As an observer from the Earth, one sees celestial bodies move around in the sky over time. The main factor being the Earth revolving around itself, plotting the angle of altitude of a celestial body over time yields a near-sinusoidal signal on a twenty-four hour period. In order to mitigate the impact of the atmosphere of Earth on observation quality, a global altitude lower bound is set - typically 20°, at least above the horizon line (0°). Setting such an altitude threshold leads to a daily availability window for each celestial body, which could overlap part of two consecutive days. Consequently, this setting can be modeled as the makespan minimization of a single machine scheduling non-preemptive instance with a set of n jobs J = {1,...,n}, a day length L and, for each job j in J, a processing time p_j, a daily release date r_j and a daily deadline d_j. Surprisingly, to the best of our knowledge, this does not seem to correspond to any previously studied scheduling problem. As such, in this contribution, we propose to investigate the (parameterized) complexity of this scheduling problem, and unveil connections to more established scheduling settings. This work is done in the context of the Square-Kilometre Array Observatory project (SKAO) and in partnership with the ECLAT laboratory.