Template-Type: ReDIF-Paper 1.0
Author-Name: van der Veen, J.A.A.
Author-Name-Last: van der Veen
Author-Name-First: Jack A.
Author-Name: Woeginger, G.J.
Author-Name-Last: Woeginger
Author-Name-First: Gerhard
Author-Name: Zhang, S.
Author-Name-Last: Zhang
Author-Name-First: Shuzhong
Title: An O(n log n) Algorithm for the K-Template Travelling Salesman Problem
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.
Creation-Date: 1995-01-01
Series: RePEc:ems:eureir
Number: EI 9555-/A
Keywords: polynomial time algorithm, single machine scheduling, travelling salesman problem
Handle: RePEc:ems:eureir:1365