An O(n log n) Algorithm for the K-Template Travelling Salesman Problem

Jack A. van der Veen, Gerhard Woeginger and Shuzhong Zhang

No EI 9555-/A, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: In this paper a one-machine scheduling model is analyzed where [TeX: $n$] different jobs are classified into [TeX: $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 with a specially structured distance matrix. For this problem we give a polynomial time solution algorithm that runs in [TeX: $O(n\\log n)$] time.

Keywords: polynomial time algorithm; single machine scheduling; travelling salesman problem (search for similar items in EconPapers)
Date: 1995-01-01
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:1365

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).