文献类型：期刊文献

中文题名：考虑常数客户批运输的单机排序问题

英文题名：Single Machine Scheduling with Batch Delivery to Multiple Customers

作者：汪磊扬[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2013

卷号：22

期号：5

起止页码：29

中文期刊名：运筹与管理

外文期刊名：Operations Research and Management Science

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;北大核心:【北大核心2011】；CSSCI:【CSSCI_E2012_2013】；CSCD:【CSCD_E2013_2014】；

基金：国家自然科学基金资助资助项目(10771067)

语种：中文

中文关键词：组合最优化;排序;近似算法;批运输;常数客户

外文关键词：combinatorial optimization ; scheduling; approximation algorithm ; batch delivery; multiple customers

摘要：本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。
In this paper, we consider the scheduling problem in which the jobs are first processed by one single machine and then delivered in batches by a single vehicle with limited capacity to the respective customers. The goal is to minimize the makespan. For the identical job size case, we present a polynomial time algorithm when the number of customers is fixed. For the non-identical job sizes case, we consider a special case with three cus- tomers and develop a 2-approximation algorithm.