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

SEMI ON-LINE SCHEDULING PROBLEM WITH THE LARGEST PROCESSING TIME OF JOBS ON TWO UNIFORM MACHINES KNOWN

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

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

出　　处：《系统科学与数学》2006年第6期729-736,共8页Journal of Systems Science and Mathematical Sciences

摘　　要：考虑已知工件最大加工时间的两台同类机半在线问题．机器M1,M2的速度分别为s1=1,s2=s(s≥1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载．此模型简记为Q2／known largest job／Cmax．作者给出了Qmax2算法并证明此算法的竞争比为2(s+1)/s+2(1≤s≤2)和(s+1)/s(s>2),且是紧的．同时给出Q2／known largest job／Cmax问题的一个下界,并且证明Qmax2算法的竞争比与最优算法竞争比之差不大于1/4.In this paper, we investigate a semi on-line scheduling problem on two uniform machines M1, M2. Speeds s1 = 1 and s2 = s（s ≥ 1） are associated with machine M1 and machine M2, respectively. The jobs arrive one by one as they appear in a list. The existence of a job is not known until all its predecessors in the list have already been scheduled, but the largest processing time of these jobs is knownin advance. Our goal is to minimize Cmax -the maximum workload of two machines. We denote this problem as Q2/known largest job/Cmax. We give a Q max 2 algorithm and prove its competitive ratio is 2（s＋1）/s＋2 （1 ≤ s ≤ 2） and s＋1/s （s 〉 2）, and this competitive ratio is tight. We also provide a lower bound of the competitive ratio for problemQ2/known largest job/Cmax and claim that the gap between the competitive ratio of Q max 2 algorithm and the optimal value is not greater than 1/4.

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

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