中文摘要：

本文研究一类并行工件平行机在线排序问题。给定2台平行机和一组按列表到达的并行工件,对每一到达的工件进行机器指派和确定开工时间,使得机器完工时间的lp范数最小。本文首先分析了LS算法的竞争比,其值为2;其次证明了任何在线算法的竞争比不小于4/3。

英文摘要：

We study the online scheduling problem of parallel jobs. Parallel jobs means it may require a number of ma-chines at the same time. Given two identical machines and a job sequence arrive over list,we need to assign the arrival jobs to some machines and determine its starting time such that the lp norm of the machine completion time vector is minimized. We ifrst proof that the performance ratio of the classic LS algorithm is two,then we show that the competitive ratio is at least 4/3 for any online scheduling algorithm.