论文部分内容阅读
本文研究两个带有分批费用的平行分批排序问题.平行分批是将工件集分割成若干批在机器上成批加工,机器可同时加工在一批的多个工件,每批的加工时间等于该批中最大的加工时间.假设每分一批都产生一个固定的分批费用,本文目标是将工件分成若干批且排出各批的加工顺序,使目标值最优.这里假定工件和批处理机都在零时刻到达,一旦开始加工就不允许中断.本文利用动态规划方法分别给出下面两个问题的多项式时间算法：一是最小化总加权完工时间与分批费用之和;二是最小化最大延迟与分批费用之和.