Single-Machine Scheduling with Release Times and Tails

    loading  Checking for direct PDF access through Ovid


We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O(n2 logn logP) algorithm for the case when the processing times of some jobs are restricted to either P or 2P.

Related Topics

    loading  Loading Related Articles