An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization
Lin Chen, Nicole Megow, Kevin Schewior · SIAM Journal on Computing · 2018
We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general $\mathcal{O}(\log {m})$-competitive algorithm for the online problem, where $m$ is the optimal number of machines used in an offline solution. This is the first improvement to an intriguing problem in nearly two decades. To date, the best known result is a $\mathcal{O}(\log (p_{\max}/p_{\min}))$-competitive algorithm by Phillips et al. [ Optimal time-critical scheduling via resource augmentation, STOC, 1997] that depends on the ratio of maximum and minimum job sizes, $p_{\max}$ and $p_{\min}$. Even for $m=2$ no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of $\mathcal{O}(1)$ even independently of $m$. The following two key components lead to our new result. First, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.