Busy Time Scheduling on a Bounded Number of Machines (Extended Abstract)

In this paper we consider a basic scheduling problem called the busy time scheduling problem - given n jobs, with release times r(j), deadlines d(j) and processing times p(j), and m machines, where each machine can run up to g jobs concurrently, our goal is to find a schedule to minimize the sum of the "on" times for the machines. We develop the first correct constant factor online competitive algorithm for the case when g is unbounded, and give a O(log P) approximation for general g, where P is the ratio of maximum to minimum processing time. When g is bounded, all prior busy time approximation algorithms use an unbounded number of machines; note it is NP-hard just to test feasibility on fixed m machines. For this problem we give both offline and online (requiring "lookahead") algorithms, which are O(1) competitive in busy time and O(log P) competitive in number of machines used.