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

The sum of squares of the machine completion times minimization scheduling problem on two identical parallel machines

作　　者：谷存昌[1,2] 张玉忠[1] 

机构地区：[1]曲阜师范大学管理学院,山东日照276826 [2]河南工业大学理学院,郑州450001

出　　处：《运筹学学报》2015年第1期99-107,共9页Operations Research Transactions

基　　金：教育部高等学校博士学科点专项基金(No.20123705110003);国家自然科学基金(Nos.11071142;11201259;11201121);河南省教育厅自然科学基金(Nos.2011B110007;2011B110008);山东省自然科学基金(No.ZR2010AM034)

摘　　要：在两个竞争公司进行零和博弈过程中,最大化两个公司收益的乘积,在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和.给出了该问题修改的延缓开始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,且界是紧的.In the process of two competitive companies zero-sum game,maximize the product of the two company proceeds,equivalent to minimize the sum of the squares of the machine completion times on two identical parallel machines.We consider an off-line modified delayed-start LPT algorithm：firstly,renumber the jobs in the non-decreasing processing time order;secondly,if the total processing time P（2m） of the longest 2m jobs is less than（2m ＋ 1）p2m＋1,schedule the first 2m ＋ 1 jobs optimally followed by the remaining jobs scheduled according to the LPT rule;otherwise,P（2m） is not less than（2m ＋ l）p2m＋1,schedule the first 2m jobs optimally followed by the remaining jobs scheduled according to the LPT rule.We prove that the worst case ratio of this algorithm is not greater than 1 ＋（1/（2m＋2））2,and the bound is tight.

关 键 词：离线排序 修改的延缓开始LPT算法 最差性能比 

分 类 号：O221.1[理学—运筹学与控制论]