文献类型：会议论文

英文题名：An improved approximation algorithm for single machine scheduling with job delivery

作者：Liu, Peihai[1];Lu, Xiwen[1]

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

会议论文集：3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

会议日期：JUN 10-12, 2009

会议地点：Huangshan, PEOPLES R CHINA

语种：英文

外文关键词：Scheduling; Job delivery; Approximation algorithm

摘要：In single machine scheduling with release times and job delivery, jobs are processed on single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2. (C) 2010 Elsevier B.V. All rights reserved.