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

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