Paper Info
Title
LP rounding and combinatorial algorithms for minimizing active and busy time
Abstract
We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with release time, deadline and required processing length. The jobs need to be scheduled so that at most g jobs can be running on a machine at any given time. The duration for which a machine is active (i.e., \"on\") is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that is a $3$-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, that is, where g is unbounded. For arbitrary g, this yields an algorithm that is 2$-approximate.
Year
DOI
Venue
2014
10.1007/s10951-017-0531-3
J. Scheduling
Keywords
Field
DocType
Active time,Busy time,Batch scheduling
Integer,Preemption,Mathematical optimization,Virtual machine,Scheduling (computing),Computer science,Combinatorial algorithms,Greedy algorithm,Rounding,Job scheduler
Conference
Volume
Issue
ISSN
20
6
1094-6136
Citations 
PageRank 
References 
3
0.43
16
Authors
3
Name
Order
Citations
PageRank
Jessica Chang151.46
Samir Khuller24053368.49
Koyel Mukherjee3315.45