by Janiak, A., Kovalyov, M.Y., Kubiak, W., Werner, F..
Series: 2001-30, Preprints
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.
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