文献类型：期刊文献

英文题名：Single-Vehicle Scheduling Problems with Release and Service Times on a Line

作者：Yu, Wei[1];Liu, Zhaohui[1]

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2011

卷号：57

期号：2

起止页码：128

外文期刊名：NETWORKS

收录：;EI(收录号：20110813690692);WOS:【SCI-EXPANDED(收录号:WOS:000287930400004)】；

基金：Contract grant sponsor: National Natural Science Foundation of China; Contract grant number: 10771067

语种：英文

外文关键词：vehicle routing; vehicle scheduling; approximation algorithm

摘要：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. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 128-134 2011