01-30
Approximation Schemes for Scheduling with Controllable Processing Times
by Janiak, A.; Kovalyov, M.Y.; Kubiak, W.; Werner, F.
Preprint series: 01-30, Preprints
The paper is published: European Journal of Operational Research, Vol. 165, No. 2, 2005, 416 - 422.
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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.