Premium
Single‐vehicle scheduling problems with release and service times on a line
Author(s) -
Yu Wei,
Liu Zhaohui
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20393
Subject(s) - job shop scheduling , scheduling (production processes) , computer science , schedule , approximation algorithm , mathematical optimization , operations research , real time computing , mathematics , algorithm , operating system
We consider the following vehicle scheduling problem. There are some customers on a line that will be served by a single vehicle. Each customer is associated with a release time and a service time. The objective is to schedule the vehicle to minimize the makespan. For the tour version, where the makespan means the time when the vehicle has served all customers and returned back to its initial location, we present a 3/2‐approximation algorithm. For the path version, where the makespan is defined as the time by which the last customer has been served completely, we present a 5/3‐approximation algorithm. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 128–134 2011