TY - JOUR
T1 - A model for minimizing active processor time
AU - Chang, Jessica
AU - Gabow, Harold N.
AU - Khuller, Samir
N1 - Funding Information:
Research of Samir Khuller supported by NSF CCF-0728839, NSF CCF-0937865 and a Google Research Award.
Funding Information:
Research done while Jessica Chang was visiting the University of Maryland and was supported by an NSF Graduate Research Fellowship, NSF CCF-1016509, and NSF CCF-0937865.
PY - 2014/11
Y1 - 2014/11
N2 - We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J i has an integer length ℓ i as well as a set T i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is "active" at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ℓ i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T i is a single interval, assuming that jobs are given in sorted order. For general T i, we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120-129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an O(√Lm) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ i ℓ i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.
AB - We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J i has an integer length ℓ i as well as a set T i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is "active" at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ℓ i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T i is a single interval, assuming that jobs are given in sorted order. For general T i, we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120-129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an O(√Lm) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ i ℓ i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.
KW - Active time
KW - Algorithms
KW - Matchings
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=84879869007&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84879869007&partnerID=8YFLogxK
U2 - 10.1007/s00453-013-9807-y
DO - 10.1007/s00453-013-9807-y
M3 - Article
AN - SCOPUS:84879869007
VL - 70
SP - 368
EP - 405
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
IS - 3
ER -