加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．

Single Machine Scheduling and Job Delivery to Minimize Makespan with the Processing Times of Jobs being Proportional to Their Sizes

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.