2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times

In this paper, given a path G with n vertices v(1), v(2),...,v(n) and m identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex v(j) in G has exactly one job j. Any of the n jobs must be served by some vehicle. Each job j has a release time r(j) and a handling time h(j). A travel time w(e) is associated with each edge e. The problem asks to find an optimal schedule of the m vehicles that minimizes the maximum completion time of all jobs. It is already known that the problem is NP-hard for any fixed m greater than or equal to 2. In this paper, we first present an O(mn(2)) time 2-approximation algorithm to the problem, by using properties of optimal gapless schedules. We then give a nearly linear time algorithm that delivers a (2 + epsilon)-approximation solution for any fixed epsilon > 0. (C) 2003 Elsevier B.V. All rights reserved.