Zurück zu den Preprints des Jahres 2001


2001-30

Approximation Schemes for Scheduling with Controllable Processing Times

by Janiak, A., Kovalyov, M.Y., Kubiak, W., Werner, F..


Series: 2001-30, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
We study the single machine scheduling problem with controllable job processing times to minimze a linear combination of the total weighted job completion time and the total weighted processing time
compression. We show that this scheduling problem is NP-hard in the ordinary sense. We also present fast fully polynomial
time approximation schemes for the problem. The schmes apply to all positive
half-products that make up an interesting subclass of half-products which is introduced
in this paper.

Keywords:
Single machine scheduling, controllable processing times, pseudo-Poolean optimization, fully polynomial time approximation schme, computational complexity

This paper was published in:
European Journal of Operati