Zurück zu den Preprints des Jahres 2000


Scheduling a Single Machine with Resource Dependent Release Times

by Tautenhahn, T..

Series: 2000-29, Preprints

90B35 Scheduling theory, deterministic

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.