预先知道总加工时间的一类特殊的三台平行同类机在线排序  

A Special Model of on-line Scheduling on Three Related Machines with Total Processing Time Known in Advance

作　　者：蔡圣义[1] 

机构地区：[1]温州大学数学与信息科学学院,浙江温州325035

出　　处：《温州师范学院学报》2006年第5期1-4,共4页Journal of Wenzhou Teachers College(Philosophy and Social Science Edition)

摘　　要：研究三台平行同类机在线排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=1,s3=s≥1．利用“总加工时间”这一部分信息来设计算法,证明了该算法的竞争比为(s+2)/s^(1/2)．结合文献中曾有的关于此问题在线算法的下界,可以知道当S≥2时,该算法比可能有的最好的在线算法在性能上要好．We have studied a special model of scheduling permanent jobs on three related machines in an on-line fashion. Two machines have the same speed, viz. 1. And the speed of the other machine is s（≥1） . We have proved that a semi-online algorithm for this problem with the total processing time is known in advance. The competitive ratio of the semi-online algorithm is√（s＋2）/s Is and for s ≥ 2 . It is better than any online algorithm.

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

分 类 号：O223[理学—运筹学与控制论]