加工时间线性递减的平行机排序问题

Parallel machine scheduling with linearly decreasing processing times

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。

This paper mainly deals with two scheduling problems with two machines, one is parallel identical machine scheduling problem, the other is parallel identical machine scheduling problem of serial batching problems with each batch contains exactly k jobs. In these two problems, the job processing time is a linear de creasing function of its starting time, the objective is to minimize the total completion time. The optimal schedule algorithm for them each is given spectively. The conclusions of the two problems can be popularized to the case of rn machines.