## Abstract

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. 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 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. [3] 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 at most 4/3 times the active time of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.

Original language | English (US) |
---|---|

Title of host publication | Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings |

Pages | 289-300 |

Number of pages | 12 |

DOIs | |

State | Published - Oct 1 2012 |

Event | 20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, Slovenia Duration: Sep 10 2012 → Sep 12 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7501 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 20th Annual European Symposium on Algorithms, ESA 2012 |
---|---|

Country | Slovenia |

City | Ljubljana |

Period | 9/10/12 → 9/12/12 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)