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

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

研究了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题,要求在整数时刻到达工件,整数时刻开始加工工件,当然也会在整数时刻完工工件.利用对手法证明任一实例在任意算法下竞争比不小于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.