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

21 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