Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
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.
approximate algorithms routing and scheduling performance guarantee worst-case analysis