单机分批加工最大迟后问题的一个多项式时间算法

A Polynomial Time Algorithm for Maximum Lateness in Single Machine Scheduling with Batching

文中考虑下述单机分批问题：对时刻零同时到达的ｎ个工件需分成若干批在同台机器上加工，同批工件加工时相邻，任一工件的完工时间为所在批中全部工件完工时的时间，机器每加工一批工件需一相同的调整时间．文中以工件的最大迟后为目标函数，对工件加工顺序预先给定和可任意时的最优分批分别给出了多项式时间算法．

N jobs arrive at same time and need to be processed in batches by the same machine. The jobs in the same batch are processed successively and the completion time of all the jobs in the same batch is defined as the completion time of the batch they belong to. There exists a set up time whenever the machine begins to process a new batch. Taking the maximum lateness as objective function, this paper develops a polynomial time algorithms for the processing sequence of the n jobs given or not given.