Open Collections

An O(log m)-Competitive Algorithm for Online Machine Minimization

Banff International Research Station for Mathematical Innovation and Discovery

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 an O(logm)-competitive algorithm, with m being the optimal number of machines used in an optimal fine solution. This is the first improvement on an intriguing problem in nearly two decades. To date, the best known result is a O(log pmin=pmax)-competitive algorithm by Phillips et al. (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 constantcompetitive. 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. Firstly, 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. Joint work with Lin Chen and Kevin Schewior.

Mathematics; Computer science; Combinatorics; Theoretical computer science

video/mp4

Author affiliation: Technische Universität München

2016-06-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/58240

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/