原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

两台平行机完工时间平方和最小的排序问题

在两个竞争公司进行零和博弈过程中, 最大化两个公司收益的乘积, 在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和. 给出了该问题修改的延缓开始\ LPT\ 算法: 首先, 将工件按照加工时间$\p_j\ $的\ LPT\ 序重新标记; 若加工时间最长的前\ $2m$\ 个工件的总加工时间\ $P(2m)< (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m+1$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+2$\ 个工件安排加工; 否则,\ $P(2m)\geq (2m+1)p_{2m+1}$, 最优的安排加工前\ $2m$\ 个工件, 一旦有机器空闲, 依次从第\ $2m+1$\ 个工件安排加工. 证明了该算法的最差性能比不超过\ $1+ ( \frac{1}{2m+2} )^2$, 且界是紧的.     

工件的运输和继列分批加工协作排序问题

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