一特殊情形的二、三台同类机上排序问题的最好在线算法

该文首先给出两台同类机在线排序问题 Q2 ∥ Cmax之 L S算法的参数性能比 ,并证明 LS算法对于其已是最好的在线算法。然后进一步给出 LS算法对于特殊情形 s1=s≥ 1,s2 =s3 =1的 Q3 ∥ Cmax问题的参数紧界 ,并证明当 s≥ 2时 ,LS算法亦是最好的在线算法。

In this paper the author studies the classical on-line sche-duling on two or three uniform processors and analyses the parametric bound for famous LS (list scheduling) algorithm. When Q2∥C max is given the tight bound, it proves best possible. Q3∥C max is given tight parametric bound of LS algorithm in a special version s1=s≥1, s2=s 3=1. When s≥2, it is also best possible.\;