LP rounding and combinatorial algorithms for minimizing active and busy time

Jessica Chang*, Samir Khuller, Koyel Mukherjee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)657-680
Number of pages24
JournalJournal of Scheduling
Volume20
Issue number6
DOIs
StatePublished - Dec 1 2017

Keywords

  • Active time
  • Batch scheduling
  • Busy time

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'LP rounding and combinatorial algorithms for minimizing active and busy time'. Together they form a unique fingerprint.

Cite this