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

Jack A.A. Van Der Veen, Gerhard J. Woeginger, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

In this paper a one-machine scheduling model is analyzed where n different jobs are classified into K 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(nlogn) time.

Original languageEnglish (US)
Pages (from-to)235-254
Number of pages20
JournalMathematical Programming, Series B
Volume82
Issue number1-2
DOIs
StatePublished - Jun 1 1998

Keywords

  • Polynomial time algorithm
  • Single machine scheduling
  • Traveling Salesman Problem

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