TY - GEN

T1 - LP rounding and combinatorial algorithms for minimizing active and busy time

AU - Chang, Jessica

AU - Khuller, Samir

AU - Mukherjee, Koyel

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Busy time

KW - Packing

KW - Scheduling

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

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

U2 - 10.1145/2612669.2612689

DO - 10.1145/2612669.2612689

M3 - Conference contribution

AN - SCOPUS:84904510507

SN - 9781450328210

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 118

EP - 127

BT - SPAA 2014 - Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014

Y2 - 23 June 2014 through 25 June 2014

ER -