Premium
Better approximation ratios for the single‐vehicle scheduling problems on line‐shaped networks
Author(s) -
Karuno Yoshiyuki,
Nagamochi Hiroshi,
Ibaraki Toshihide
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10028
Subject(s) - combinatorics , vertex (graph theory) , scheduling (production processes) , approximation algorithm , vehicle routing problem , mathematics , job shop scheduling , discrete mathematics , schedule , computer science , routing (electronic design automation) , graph , mathematical optimization , computer network , operating system
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.