CAJ | 학술논문

本文考虑工件首先在单机上加工，完工的工件由一辆容量有限的车配送到指定客户的模型，目标是最小化makespan。对于工件物理大小相同的情况，我们考虑了常数个客户的情形，并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况，我们讨论了一类特殊的三个客户的情形，并给出了一个2-近似算法。
본문고필공건수선재단궤상가공，완공적공건유일량용량유한적차배송도지정객호적모형，목표시최소화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 .