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

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