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.