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

✍ Scribed by Yoshiyuki Karuno; Hiroshi Nagamochi

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 180 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00596-6

✦ Synopsis

In this paper, given a path G with n vertices v1; v2; : : : ; vn and m identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex vj 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 rj and a handling time hj. A travel time we is associated with each edge e. The problem asks to ÿnd 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 ÿxed m ¿ 2. In this paper, we ÿrst 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 + )-approximation solution for any ÿxed ¿ 0.