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 } ∈ E , and each job, which is also denoted as v and is located at vertex v ∈ V , has release time r ( v ) and handling time h ( v ). There is a single vehicle, which is initially situated at v 1 ∈ 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 ∈ 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. © 2002 Wiley Periodicals, Inc.