A PTAS for single machine scheduling with controllable processing times

P. Schuurman, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    Abstract: 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 [?] and Hall [?] can directly be applied to design a polynomial time approximation scheme for this problem. Keywords. Scheduling, worst case analysis, approximation algorithm, approximation scheme, controllable processing time.
    Original languageEnglish
    Pages (from-to)369-378
    JournalActa Cybernetica
    Volume15
    Issue number3
    Publication statusPublished - 2002

    Fingerprint

    Dive into the research topics of 'A PTAS for single machine scheduling with controllable processing times'. Together they form a unique fingerprint.

    Cite this