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

摘要

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