已知工件最大加工时间的三台同类机半在线问题  

Semi-online Scheduling Problem on Three Uniform Machines with the Known Largest Job

作　　者：罗润梓[1] 孙世杰[2] 何龙敏[2] 

机构地区：[1]南昌大学理学院数学系,南昌330031 [2]上海大学理学院数学系,上海200444

出　　处：《工程数学学报》2010年第1期53-64,共12页Chinese Journal of Engineering Mathematics

基　　金：江西省自然科学基金(2007GZS2126)~~

摘　　要：本文考虑已知工件最大加工时间的三台同类机半在线问题。三台机器的速度分别为s1=r,s2=1,s3=s>1,1≤r≤s,工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载。本文证明任何解此问题的算法竞争比的下界为3/2且给出Qmax3算法并证明此算法的竞争比不大于(2(r+s+s1))/(2r+s)(1<s≤2)和(r+r2+1)/(r+s)(s>2)。In this paper, we investigate a semi-online scheduling problem on three unilorm macnmes. Three speeds s1 = r, s2 = 1, s3 = s 〉 1, 1 〈 r 〈 s are associated with machine Mi（i = 1,2,3）, respectively. The jobs arrive one by one without knowledege of sucessive jobs, but the processing time of the largest job is known in advance. Our goal is to minimize the Cmax-the maximum workload of three machines. For this problem, we give a Q max 3 algorithm and prove its competitive ratio is not greater than 2（r＋s＋1）/2r＋s（1〈s≤2） and r＋2s＋1/r＋s（s〉2） while its lower bound is 3/2.

关 键 词：排序 半在线 竞争比 

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