Scheduling a Single Machine with Resource Dependent Release Times
Preprint series: 00-29, Preprints
Abstract: We consider the problem of scheduling n jobs on a single machine to minimize makespan under release times and precedence constraints. The given release times are not fixed but can be decreased linearly to a resource expenditure. The total amount of resource available is restricted. It is shown that even very special cases of this problem are NP-hard. For the general case of our problem, we give a heuristic with performance guarantee 2. For the problem with tree-like precedence constraints a (3/2 + epsilon)-algorithm is given and we develop a polynomial approximation scheme for the problem without precedence constraints. We show that these results can be extended to the case of nonlinear resource expenditures.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.