We consider the following scheduling problem: each of n jobs is to be scheduled without interruption on a single machine. Each job has a release date, when it first becomes available for processing, and, after completing its processing on the machine, requires an additional delivery time. Feasible schedules are further restricted by job precedence constraints, and the objective is to minimize the time by which all jobs are delivered. In the notation of Graham, Lawler, Lenstra and Rinnooy Kan, this problem is denoted 1|r_j, prec| L_max. We show that, for each positive relative error epsilon, we can construct a polynomial-time algorithm that is guaranteed to deliver a feasible schedule no longer than (1+epsilon) times the length of the optimal schedule.
Appeared in the Proc. of the Mathematical Programming Soc. Conference on Integer Programming and Combinatorial Optimization (IPCO) , May 1990.
If you would like a copy of this paper, you can email me at leslie@jhu.edu.