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 -