摘要：研究三台平行同类机排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=s≥1,s3=1.证明了对该问题来说,经典的LS算法的竞争比为min{4s＋1/2s＋1,3s＋1/2s};同时证明当s≥3,该问题的下界为3s＋1/2s,从而说明了LS算法是可能存在的最好的在线算法.此外,对1≤s＜3时问题的下界也做了一些讨论,这时虽然不能确定LS算法仍然是可能存在的最好的在线算法,但可知道这时LS算法与可能存在的最好的在线算法在竞争比上相差少于0.4299.

关键词：在线 同类机 竞争比 

单位：温州大学数学与信息科学学院; 浙江温州325035