Paper Info
Title
Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
Abstract
We consider two variants of the single-vehicle scheduling problem on line-shaped networks. Let L = (V, E) be a line, where V = {v(1), v(2),..., v(n)} is a set of n vertices and E = {{v(i), v(i+1)]\i = 1, 2,..., n - 1) is a set of edges. The travel times w(u, v) and w(v, u) are associated with each edge {u, v) is an element of E, and each job, which is also denoted as v and is located at vertex v is an element of V, has release time r(v) and handling time h(v). There is a single vehicle, which is initially situated at v(1) is an element of V, and visits all vertices to process the jobs before it returns back to v(1). The first problem asks to find an optimal routing schedule of the vehicle that minimizes the completion time. This is NP-hard [21], and there exists an approximate algorithm with the approximation ratio of 2 [12]. In this paper, we improve this ratio to 1.5. On the other hand, the second problem minimizes the maximum lateness, under the assumption that all release times r(v) are zero, but there are due times d(v) for v is an element of V and d(v(n+1)) for the vehicle. This problem is also NP-hard [13]. We improve the previous best-known approximation ratio of 2, which was obtained in [11], to 1.5. (C) 2002 Wiley Periodicals, Inc.
Year
DOI
Venue
2002
10.1002/net.10028
NETWORKS
Keywords
Field
DocType
routing and scheduling,approximate algorithms,performance guarantee,worst-case analysis
Approximation algorithm,Combinatorics,Vehicle routing problem,Job shop scheduling,Vertex (geometry),Scheduling (computing),Travelling salesman problem,Minimum time,Mathematics,Network structure
Journal
Volume
Issue
ISSN
39
4
0028-3045
Citations 
PageRank 
References 
13
0.99
12
Authors
3
Name
Order
Citations
PageRank
Yoshiyuki Karuno110813.47
Hiroshi Nagamochi21513174.40
Toshihide Ibaraki32593385.64