by Tautenhahn, T..

**Series:** 2000-29, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**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.

**Keywords:**

scheduling