Minimizing Busy Time in Multiple Machine Real-time Scheduling

Rohit Khandekar, Baruch Schieber, Hadas Shachnai & Tami Tamir
We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem...