Scheduling with release times and deadlines on a minimum number of machines

Abstract. In this paper we investigate a scheduling problem motivated by a variety of practical applications: We are given jobs with integer release times, deadlines, and processing times. The goal is to find a non-preemptive 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 , we present a polynomial-time algorithm, on the other hand we show that the problem becomes -complete already if differences up to are allowed. Moreover, we present two dynamic programs and several approximation algorithms. We explain how filling machine by machine leads to an -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 ff . Finally, we present constant approximation algorithms for instances with restrictions on the release times and deadlines