Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #98007 (March, 1998)

A 1.5-Approximation for Single-Vehicle Scheduling Problem on a Line with Release and Handling Times
by Yoshiyuki Karuno, Hiroshi Nagamochi and Toshihide Ibaraki

In this paper we consider a single-vehicle scheduling problem on a straight line. Let $L=(V,E)$ be a line, where $V=\{v_1,v_2,\ldots,v_n\}$ is a set of $n$ vertices and $E=\{\{v_i, v_{i+1}\} \mid i=1,2,\ldots,n-1\}$ is a set of edges. 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 one of the end vertices, without loss of generality say $v_{1} \in V$, and visits all the jobs on $L$ to process them before it returns back to $v_{1}$. The processing of a job $v$ cannot be started before its release time $r(v)$ (hence the vehicle has to wait if it arrives at $v$ before time $r(v)$ for processing) and requires $h(v)$ time units once it has been started (no preemption is allowed). It is known that the problem of minimizing the completion time is NP-hard, and that there exists an approximate algorithm which finds a schedule such that its completion time is at most twice of the exact minimum. In this paper we show that the problem is polynomially approximable within 1.5 of optimal, which is an improvement of the previous result.