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

The On-line Scheduling Problem of Unit-length Jobs with Chains Precedence Constraints on Two Parallel Machines to Minimize the Square Sum of the Machine Makespans

作　　者：豆俊梅[1] 谷存昌[1] 慕运动[1] 

机构地区：[1]河南工业大学理学院,郑州450001

出　　处：《河南科学》2012年第10期1414-1418,共5页Henan Science

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

摘　　要：研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.In this paper,we study the on-line scheduling problem of unit-length jobs with chains precedence constraints on two parallel processors.The jobs are released at integer times.The objective is to minimize the square sum of the machine makespans.By adversary argument,we prove that the competitive ratio in an arbitrary algorithm is not less than 54,and asymptotically tends to 2 in dense algorithms.Then we give a best possible dense algorithm of the competitive ratio 2.

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

分 类 号：O223[理学—运筹学与控制论]