两个带有分批费用的单机平行分批排序问题

摘要

假定工件和批处理机都在零时刻到达,工件被成批进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用。第1个问题对目标函数为任意的正则函数与分批费用之和的情形,利用动态规划方法给出了拟多项式时间算法;第2个问题对目标函数为误工工件数与分批费用之和的极小化问题,同样利用动态规划方法给出了O(n4)的算法。