| The vehicle scheduling problem consists of a set of $n$ jobs which are located at different vertices in a given graph. Each job is characterized by a release time, a handling time and a due date (or a deadline). There are $m$ ($1 \leq m \leq n$) identical vehicles on the graph to process the jobs. The problem asks to find a routing schedule of the $m$ vehicles that minimizes a given objective function. Graphs are restricted to paths or trees in some applications, and thus the problem on these graphs has been studied extensively. In this paper, we give a brief review of approximation algorithms to the problem on paths or trees obtained by the previous work. As a closely related topic, we also discuss the subtree cover problem where a given edge-weighted tree with $n$ weighted vertices is partitioned into a number of subtrees so as to minimize a given objective. In this paper, we propose an $O(n^{3}\log n)$ time 3-approximation algorithm to the problem of minimizing the number of subtrees, where the weight of each subtree must not exceed a specified capacity. |
|
