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

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