中文摘要：

这份报纸认为在两个问题的目的是最小化 makespan 的地方，安排问题的二台平行机器，和这些工作随着时间的过去到达，在有速度的二台一致机器上 1 并且 s (s 1 ) ，并且在 m 上相同机器分别地。为第一个问题，作者证明联机并行口算法有竞争比率(1 +\(\sqrt 5 \))/2 1.6180 并且界限是紧张的。而且，作者证明联机并行口算法有最好的可能的竞争比率如果 s 1.8020。为第二个问题，在场的作者更低的界限(15 \(\sqrt { 17 }\))/8 1.3596 在任何确定的联机算法的竞争比率上。这改进 1.3473 的以前的结果。

英文摘要：

This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.