运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2015年
1期
99-107
,共9页
离线排序%修改的延缓开始LPT算法%最差性能比
離線排序%脩改的延緩開始LPT算法%最差性能比
리선배서%수개적연완개시LPT산법%최차성능비
off-line scheduling%modified delayed-start LPT algorithm%worst case ratio
在两个竞争公司进行零和博弈过程中,最大化两个公司收益的乘积,在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和.给出了该问题修改的延缓开始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,且界是紧的.
在兩箇競爭公司進行零和博弈過程中,最大化兩箇公司收益的乘積,在兩檯平行機的離線排序問題中相噹于最小化兩檯機器完工時間的平方和.給齣瞭該問題脩改的延緩開始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,且界是緊的.
재량개경쟁공사진행령화박혁과정중,최대화량개공사수익적승적,재량태평행궤적리선배서문제중상당우최소화량태궤기완공시간적평방화.급출료해문제수개적연완개시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,차계시긴적.
