Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #97008 (October, 1997)

Single-Vehicle Scheduling Problem on a Tree with Depth-First Routing
by Hiroshi Nagamochi, Koji Mochizuki and Toshihide Ibaraki

We consider a single-vehicle scheduling problem on a tree. Let $T=(V,E)$ be a tree. The travel times $d(u,v)$ and $d(v,u)$ are associated with each edge $\{u,v\}\in E$, and a job, which is also denoted as $v$, is located at each vertex $v\in V$. Each job $v$ has release time $r(v)$ and handling time $h(v)$. There is a single vehicle, which is initially situated at the start vertex $s\in V$, and visits all the jobs in $T$ for processing, before reaching the goal vertex $g\in V$. The start vertex $s$ is called the home location if it is also the goal vertex $g$. The processing of a job $v$ cannot be started before its release time $t=r(v)$ and takes $h(v)$ time units once its processing has started. We also add the depth-first routing constraints; i.e., the vehicle has to complete all jobs in the subtree rooted at every vertex $v$ before returning to its parent vertex. The resulting problem of minimizing the completion time under the depth-first routing constraint is denoted by TREE-VSP/DF.
In this paper, we first show that the TREE-VSP/DF with a home location $s$ has an optimal schedule that is independent of its start time, and that such schedule can be found in $O(n\log \Delta)$ time, where $\Delta$ is the maximum degree of tree $T$ and $n$ is the number of vertices. We then show that the minimum completion times $C(s')$ for all home locations $s'\in V$ can be simultaneously computed in $O(n)$ time, once the problem with a specified home location has been solved. We also consider the TREE-VSP/DF with a start vertex $s$ and a goal vertex $g$, and show that, once the TREE-VSP/DF with a specified home location $s$ has been solved, the minimum completion times $C(s,g)$ for all goal vertices $g\in V$ can be computed in $O(n)$ time.