TY - JOUR

T1 - Sequencing jobs that require common resources on a single machine

T2 - A solvable case of the TSP

AU - Van Der Veen, Jack A.A.

AU - Woeginger, Gerhard J.

AU - Zhang, Shuzhong

PY - 1998/6/1

Y1 - 1998/6/1

N2 - 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.

AB - 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.

KW - Polynomial time algorithm

KW - Single machine scheduling

KW - Traveling Salesman Problem

UR - http://www.scopus.com/inward/record.url?scp=0012930632&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012930632&partnerID=8YFLogxK

U2 - 10.1007/BF01585874

DO - 10.1007/BF01585874

M3 - Article

AN - SCOPUS:0012930632

SN - 0025-5610

VL - 82

SP - 235

EP - 254

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 1-2

ER -