A PTAS for single machine scheduling with controllable processing times

Schuur Petra and Woeginger Gerhard J.: A PTAS for single machine scheduling with controllable processing times. In: Acta cybernetica, (15) 3. pp. 369-378. (2002)

[thumbnail of cybernetica_015_numb_003_369-378.pdf]
Cikk, tanulmány, mű

Download (745kB) | Preview


We deal with a single machine scheduling problem in which each job has a release date, a delivery time and a controllable processing time. The fact that the jobs have a controllable processing time means that it is allowed to compress (a part of) the processing time of the job, in return for compression cost. The objective is to find a schedule that minimizes the total cost, that is, the latest delivery time of any job plus the total compression cost. In this note we discuss how the techniques of Hall and Shmoys [3] and Hall [1] can directly be applied to design a polynomial time approximation scheme for this problem.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2002
Volume: 15
Number: 3
ISSN: 0324-721X
Page Range: pp. 369-378
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38513/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 378. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 14. 14:55
URI: http://acta.bibl.u-szeged.hu/id/eprint/12685

Actions (login required)

View Item View Item