CAJ | 학술논문

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客.当工件的加工时间和尺寸无关时,Chang和Lee[4]已经证明该问题是强NP困难的.他们也给出了一个启发式算法,它的最差执行比为5/3,并且这个界是紧的.本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53/35,并提供了一个新的启发式算法,它的最差执行比是3/2,并且这个界是最好的.
재단궤배서화공건운수적최소화최대완공시간문제중,공건수선재일태궤기상가공,연후피일량유용량한제적기차운송도일개고객.당공건적가공시간화척촌무관시,Chang화Lee[4]이경증명해문제시강NP곤난적.타문야급출료일개계발식산법,타적최차집행비위5/3,병차저개계시긴적.본문고필공건적가공시간화척촌성정비적정형,증명료Chang화Lee적산법유경호적최차집행비53/35,병제공료일개신적계발식산법,타적최차집행비시3/2,병차저개계시최호적.
In the single machine scheduling and job delivery problem to minimize makespan, jobs are processed on a single machine and delivered by a capacitated vehicle to a single customer. When the processing times of jobs are independent on their sizes, Chang and Lee [4] proved that this problem is strongly NP-hard. They also provided a heuristic with the worst-case performance ratio of 5/3, and this bound is tight. In this paper, we consider that the restricted version in which the processing times of jobs are proportional to their sizes. We show that Chang-Lee's heuristic has a better worst-case performance ratio of 53/35 We also provide a new heuristic which has the worst-case performance ratio of 3/2,and this bound is best.