Scheduling a Single Machine with Resource Dependent Release Times

by Tautenhahn, T.


Preprint series: 00-29, Preprints

90B35 Scheduling theory, See also {68M20}


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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster