Institute of Information Science, Academia Sinica

In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time r_j, a processing time p_j, and a deadline d_j. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller, where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access predictions, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1 + 4/(1+λ) )-consistent and (1 + 4/(1−λ) )-robust with a trust parameter $[@BackSlash]lambda [@BackSlash]in [0, 1)$.
This is a joint work with Rick van de Bovenkamp, published in SOFSEM 2025.