两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题

• 作者: 慕运动 谷存昌 豆俊梅
• 来源期刊: 河南科学
• 关键词: 平行机 在线算法 链约束 完工时间平方和 竞争比分析
• 年，卷（期）: 2012,（10）
• 所属期刊栏目: 数学研究与应用
• 页码范围: 1414-1418
• 页数: 5页
• 分类号: O223
• 语种: 中文

摘要

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法一层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	豆俊梅	河南工业大学理学院	18	8	2.0	2.0
2	谷存昌	河南工业大学理学院	26	33	4.0	4.0
3	慕运动	河南工业大学理学院	36	270	7.0	16.0