Advertisement
Published in:
2010 | OriginalPaper | Chapter
Approximation Algorithms for the Multi-Vehicle Scheduling Problem
Authors : Binay Bhattacharya, Yuzhuang Hu
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we investigate approximation algorithms for the multi-vehicle scheduling problem (MVSP). In MVSP we are given a graph
G
= (
V
,
E
), where each vertex
u
of
V
is associated with a job
j
(
u
), and each edge
e
has a non-negative weight
w
(
e
). There are
m
identical vehicles available to service the jobs. Each job
j
(
u
) has its own release time
r
(
u
) and handling time
h
(
u
). A job
j
(
u
) can only be serviced by one vehicle after its release time
r
(
u
), and the handling time
h
(
u
) represents the time needed to finish processing
j
(
u
). The objective is to find a schedule in which the maximum completion time of the jobs, i.e. the makespan, is minimized. In this paper we present a 3-approximation algorithm for MVSP on trees, and a (
$5-\frac{2}{m}$
)-approximation algorithm for MVSP on general graphs.