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

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 99-107.

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

谷存昌^1,2,*, 张玉忠¹

1. 曲阜师范大学管理学院, 山东日照 276826; 2. 河南工业大学理学院, 郑州 450001

收稿日期:2014-04-30 出版日期:2015-03-15 发布日期:2015-03-15
通讯作者: 谷存昌 E-mail:gucunchang@163.com
基金资助:
教育部高等学校博士学科点专项基金(No. 20123705110003), 国家自然科学基金(Nos. 11071142, 11201259, 11201121), 河南省教育厅自然科学基金(Nos. 2011B110007, 2011B110008), 山东省自然科学基金(No. ZR2010AM034)

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

GU Cunchang^1,2,*, ZHANG Yuzhong¹

1. School of Management, Qufu Normal University, Rizhao 276826, Shandong, China; 2. College of Science, Henan University of Technology, Zhengzhou 450001, China

Received:2014-04-30 Online:2015-03-15 Published:2015-03-15

摘要/Abstract

摘要： 在两个竞争公司进行零和博弈过程中, 最大化两个公司收益的乘积, 在两台平行机的离线排序问题中相当于最小化两台机器完工时间的平方和. 给出了该问题修改的延缓开始\ 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$, 且界是紧的.

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

Abstract: 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)p_{2m+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+1)p_{2m+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+ (\frac{1}{2m+2} )^2$, and the bound is tight.

Key words: off-line scheduling, modified delayed-start LPT algorithm, worst case ratio

中图分类号:

O221.1

谷存昌, 张玉忠. 两台平行机完工时间平方和最小的排序问题[J]. 运筹学学报, 2015, 19(1): 99-107.

GU Cunchang, ZHANG Yuzhong. The sum of squares of the machine completion times minimization scheduling problem on two identical parallel machines[J]. Operations Research Transactions, 2015, 19(1): 99-107.