In this paper, we consider a scheduling problem of vehicles on a path G with n vertices and n - 1 edges. There are m identical vehicles. Each vertex in G has exactly one job. Any of the n jobs must be processed by some vehicle. Each job has a release time and a handling time. With the edges, symmetric travel times are associated. The problem asks to find an optimal schedule of the m vehicles that minimizes the maximum completion time of all the jobs. The problem is known to be NP-hard for any fixed m greater than or equal to 2. In this paper, we show that the problem with a fixed m admits a polynomial time approximation scheme. Our algorithm can be extended to the case where G is a tree so that a polynomial time approximation scheme is obtained if m and the number of leaves in G are fixed. (C) 2003 Elsevier B.V. All rights reserved.