Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints

摘要

We consider the problem of scheduling n jobs on a single machine. Each job has a release date, when it becomes available for processing, and, after completing its processing, 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 et al. this problem is noted 1∣r_j, prec∣L_(max). We develop a polynomial time approximation scheme whose running time depends only linearly on the input size. This linear complexity bound gives a substantial improvement of the best previously known polynomial bound.