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

摘要：

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

关键词：平行机、在线算法、链约束、完工时间平方和、竞争比分析

所属期刊栏目：30

分类号：O223(运筹学)

资助基金：河南省基础与前沿技术研究计划资助项目082300410070;河南省教育厅自然科学研究项目2011B110007,2011B110008;河南工业大学校级科研基金项目09XJC008,10XZR010

在线出版日期：2013-01-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1414-1418