论文部分内容阅读
近年来，工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注．讨论了先用m台车辆将工件从等待区域运输到继列分批处理机处，再进行分批加工的协作排序问题，加工一批工件需要支付一定的费用，目标为最小化工件的总完工时间与批的加工费用之和．在工件的加工时间都相等的情况下，如果工件运输方案确定，给出了多项式时间的动态规划算法；如果工件运输方案不确定，证明了该问题是NP一难的，给出了车辆返回时间t=0时，最差性能比等于2-1/m的近似算法．