TY - JOUR

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

AU - Chang, Jessica

AU - Khuller, Samir

AU - Mukherjee, Koyel

N1 - Funding Information:
This work has been supported by NSF Grants CCF-1217890 and CCF-0937865. A preliminary version of this paper appeared in ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014).
Funding Information:
Acknowledgements Funding was provided by National Science Foundation (Grant No. CCF-1217890) and Funding was provided by National Science Foundation (Grant No. CCF-0937865).
Funding Information:
Funding was provided by National Science Foundation (Grant No. CCF-1217890) and Funding was provided by National Science Foundation (Grant No. CCF-0937865). This work has been supported by NSF Grants CCF-1217890 and CCF-0937865. A preliminary version of this paper appeared in ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014).

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active 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 techniques. 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 gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., 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 a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active 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 techniques. 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 gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2-approximate.

KW - Active time

KW - Batch scheduling

KW - Busy time

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

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

U2 - 10.1007/s10951-017-0531-3

DO - 10.1007/s10951-017-0531-3

M3 - Article

AN - SCOPUS:85020648952

VL - 20

SP - 657

EP - 680

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 6

ER -