A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

    Research output: Contribution to journalArticleAcademicpeer-review

    22 Citations (Scopus)
    4 Downloads (Pure)

    Abstract

    We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of the job next to come and hence is sequence independent. The objective to to find a sequence of jobs that minimizes the time by which all jobs are delivered. The best polynomial-time approximation algorithm that was previously known for this problem is due to Zdrzalka and has a worst-case guarantee of 3 2. In this paper, we demonstrate the existence of a polynomial time approximation scheme for the problem.
    Original languageEnglish
    Pages (from-to)79-87
    Number of pages9
    JournalJournal of Scheduling
    Volume1
    Issue number2
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times'. Together they form a unique fingerprint.

    Cite this