TY - JOUR

T1 - An O(log m)-competitive algorithm for online machine minimization

AU - Chen, Lin

AU - Megow, Nicole

AU - Schewior, Kevin

N1 - Funding Information:
This work was supported by the German Science Foundation (DFG) under contract ME 3825/1. The third author's work was supported by the DFG within the research training group "Methods for Discrete Structures" (GRK 1408).
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

PY - 2018

Y1 - 2018

N2 - 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 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 O(log(pmax/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, pmax and pmin. 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 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.

AB - 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 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 O(log(pmax/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, pmax and pmin. 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 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.

KW - Competitive analysis

KW - Multiprocessor scheduling

KW - Online algorithms

UR - http://www.scopus.com/inward/record.url?scp=85060101328&partnerID=8YFLogxK

U2 - 10.1137/17M116032X

DO - 10.1137/17M116032X

M3 - Article

AN - SCOPUS:85060101328

VL - 47

SP - 2057

EP - 2077

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -