Abstract: 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 customers and develop a 2-approximation algorithm.

Key words: combinatorial optimization, scheduling, approximation algorithm, batch delivery, multiple customers

摘要： 本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。

关键词: 组合最优化, 排序, 近似算法, 批运输, 常数客户