三台同类机在线排序问题一种特殊情形的研究  

Special Model of On-line Scheduling on Three Related Machines

作　　者：蔡圣义[1] 

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

出　　处：《系统工程理论与实践》2006年第7期41-46,共6页Systems Engineering-Theory & Practice

摘　　要：研究三台平行同类机排序问题的一种特殊情形,即三台同类机的加工速度分别为s1=s2=s≥1,s3=1.证明了对该问题来说,经典的LS算法的竞争比为min42ss++11,3s2+s1;同时证明当s≥3,该问题的下界为3s2+s1,从而说明了LS算法是可能存在的最好的在线算法.此外,对1≤s<3时问题的下界也做了一些讨论,这时虽然不能确定LS算法仍然是可能存在的最好的在线算法,但可知道这时LS算法与可能存在的最好的在线算法在竞争比上相差少于0.4299.Abstract： We consider a special model of scheduling permanent jobs on three related machines in an on-line fashion. Two machines have the same speed, viz. s （ ≥ 1）. And the speed of the other machine is 1. We prove the classic on-line algorithm LS achieves the competitive ratio of min {4s＋1/2s＋1,3s＋1/2s}. When s is no less than 3, we 3s＋l prove low bound is 3s＋1/2s for this problem. Therefore, LS is the best possible on-line algorithm for this problem. When s is less than 3 and no less than 1, We also give low bound for this problem, we show that the biggest gap between LS and the best possible on-line algorithm is less than 0.4299.

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

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