两阶段供应链下极小化最大完工时间的单机系列批排序

Single Machine with Serial Batching in a Two-Stage Supply Chain to Minimize the Makespan

【目的】考虑单机情况下的加工和运输两阶段的供应链排序问题。【方法】在生产阶段,将所有工件在加工之前划分成批,在一台有限批容量的机器上加工,工件的实际加工时间是关于该工件退化率和加工位置的函数;在运输阶段,有一辆运输车,且每次只能运输一批工件,即车的容量等于批的容量。通过分析用运输车的车容量限制与工件个数的关系。【结果】由最优算法得到了一个最优排序和最小化最大完工时间。【结论】首先给出最大完工时间问题的一个下界,然后指出在当工件个数小于等于运输车的容量限制时,提供出来一个最优算法。对于当工件个数大于运输车的容量限制时,证明了当工件满足一定条件时,该问题也存在最优算法。

[Purposes]The scheduling problem of a two-stage supply chain is investigated,where the job is first processed on a machine,and then the finished job is delivered into batches.[Methods]During the production stage the job is first divided into serial batches and process on a machine where the actual job processing time is a function of its deterioration rate and position.During the stage of transportation,the batches are delivered to a customer by a single vehicle and the vehicle can only deliver one batch at one time.[Findings]The relations between capacity of vehicle and the number of jobs are analyzed.[Conclusions]A lower bound of the maximum completion time problem is given,then the problem can be easily solved when n≤c.it is proved that the problem also has an optimal algorithm when the jobs satisfies certain conditions when n>c.