TY - JOUR
T1 - Real-time scheduling to minimize machine busy times
AU - Khandekar, Rohit
AU - Schieber, Baruch
AU - Shachnai, Hadas
AU - Tamir, Tami
N1 - Funding Information:
We thank Dor Arad for helpful discussions on an earlier version of the paper. We are also grateful to the two anonymous referees for valuable comments and suggestions. Work partially supported by funding for DIMACS visitors.
Publisher Copyright:
© 2014, Springer Science+Business Media New York.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - Consider the following scheduling problem. We are given a set of jobs, each having a release time, a due date, a processing time, and demand for machine capacity. The goal is to schedule all jobs non-preemptively in their release-time deadline windows on machines that can process multiple jobs simultaneously, subject to machine capacity constraints, with the objective to minimize the total busy time of the machines. Our problem naturally arises in power-aware scheduling, optical network design, and customer service systems, among others. The problem is APX-hard by a simple reduction from the subset sum problem. A main result of this paper is a 5-approximation algorithm for general instances. While the algorithm is simple, its analysis involves a non-trivial charging scheme which bounds the total busy time in terms of work and span lower bounds on the optimum. This improves and extends the results of Flammini et al. (Theor Comput Sci 411(40–42):3553–3562, 2010). We extend this approximation to the case of moldable jobs, where the algorithm also needs to choose, for each job, one of several processing-time versus demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.
AB - Consider the following scheduling problem. We are given a set of jobs, each having a release time, a due date, a processing time, and demand for machine capacity. The goal is to schedule all jobs non-preemptively in their release-time deadline windows on machines that can process multiple jobs simultaneously, subject to machine capacity constraints, with the objective to minimize the total busy time of the machines. Our problem naturally arises in power-aware scheduling, optical network design, and customer service systems, among others. The problem is APX-hard by a simple reduction from the subset sum problem. A main result of this paper is a 5-approximation algorithm for general instances. While the algorithm is simple, its analysis involves a non-trivial charging scheme which bounds the total busy time in terms of work and span lower bounds on the optimum. This improves and extends the results of Flammini et al. (Theor Comput Sci 411(40–42):3553–3562, 2010). We extend this approximation to the case of moldable jobs, where the algorithm also needs to choose, for each job, one of several processing-time versus demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.
KW - Approximation algorithms
KW - Minimum total busy time
KW - Power-aware
KW - Real-time scheduling
UR - http://www.scopus.com/inward/record.url?scp=84944153484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84944153484&partnerID=8YFLogxK
U2 - 10.1007/s10951-014-0411-z
DO - 10.1007/s10951-014-0411-z
M3 - Article
AN - SCOPUS:84944153484
SN - 1094-6136
VL - 18
SP - 561
EP - 573
JO - Journal of Scheduling
JF - Journal of Scheduling
IS - 6
ER -