Scheduling
with Release Times and Deadlines on a Minimum Number of Machines 

Authors:  Mark Cieliebak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, and Peter Widmayer 
Reference:  Technical Report 419, ETH Zurich, Department of Computer Science, August 2003 
Download:  Postscript (.ps) or PDF (.pdf) 
Abstract: 
In this paper we investigate a scheduling problem motivated
by a variety of practical applications: We are given n jobs
with integer release times, deadlines, and processing times. The goal
is to find a nonpreemptive schedule such that all jobs meet their deadlines
and the number of machines used to process all jobs is minimum. If all
jobs have equal release times and equal deadlines, we have the classical
bin packing problem. Therefore, we are interested in solving this problem
for instances where the window (interval from release time to deadline)
is just slightly larger than the processing time. For the case that this
difference is at most 1, we present a polynomialtime algorithm, on the
other hand we show that the problem becomes NPcomplete already if differences
up to 2 are allowed. Moreover, we present two dynamic programs and several
approximation algorithms. We explain how filling machine by machine leads
to an O(log n)approximation
and develop a greedy approximation algorithm which has a constant approximation
ratio if the problem instance is restricted. For general instances we
show that its solution can differ from the optimum solution by a factor
of $\Omega(log n)$. Finally, we present constant approximation
algorithms for instances with restrictions on the release times and deadlines.

Remarks: 