单机分批加工最大迟后问题的一个快速算法

A Quick Algorithm for the Maximum Lateness in Single Machine Scheduling with Batching

本文考虑下述单机分批加工问题：在时刻零同时到达的ｎ个工件需分成若干批在同台机器上加工，同批中的工件相邻，任一工件的完工时间为所在批中全部工件完工时的时间，机器每加工一批工件需一相同的调整时间．文中以工件的最大迟后为目标函数，对上述分批问题用动态规划技术给出了一多项式时间算法．

his paper deals with the following single machine scheduling with batching: n jobs arrive at time zero and need to be processed in batches on the same machine. The jobs in the same batch are processed successively and the completion times of the jobs in the same batch are equal to the completion time of the batch to which they belong. There exists a setup time for a machine whenever the machine begins to process a new batch. Taking the minimization of the maximum lateness of the jobs as the objective function, this paper develops a dynamic programming for this batching problem.