Online Busy Time Scheduling with Untrusted Prediction
摘要
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 [20], where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, 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+\frac{4}{1+\lambda })\) -consistent and \((1+\frac{4}{1-\lambda })\) -robust with a trust parameter \(\lambda \in [0, 1)\) .