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)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Online Busy Time Scheduling with Untrusted Prediction

  • Rick van de Bovenkamp,
  • Alison Hsiang-Hsuan Liu

摘要

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)\) .