Sequencing jobs that require common resources on a single machine : a solvable case of the TSP

J.A.A. Veen, van der, G.J. Woeginger, S. Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)

    Abstract

    In this paper a one-machine scheduling model is analyzed wheren different jobs are classified intoK groups depending on which additional resource they require. The change-over time from one job to another consists of the removal time or of the set-up time of the two jobs. It is sequence-dependent in the sense that the change-over time is determined by whether or not the two jobs belong to the same group. The objective is to minimize the makespan. This problem can be modeled as an asymmetric Traveling Salesman Problem (TSP) with a specially structured distance matrix. For this problem we give a polynomial time solution algorithm that runs in O(n logn) time.
    Original languageEnglish
    Pages (from-to)235-254
    Number of pages20
    JournalMathematical Programming
    Volume82
    Issue number1-2
    DOIs
    Publication statusPublished - 1998

    Fingerprint Dive into the research topics of 'Sequencing jobs that require common resources on a single machine : a solvable case of the TSP'. Together they form a unique fingerprint.

    Cite this