罗润梓;孙世杰
≤考虑已知工件最大加工时间的两台同类机半在线问题. 机器M1, M2的速度分别为
s1=1, s2=s(s≥1),工件是一个一个独立地到来, 工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的, 目标函数为极小化最大机器负载.此模型简记为Q2/known largest job/Cmax.作者给出了Qmax 2算法并证明此算法的竞争比为(2(s+1))/(s+2)(1≤ s≤2)和(s+1)(s)(s>2), 且是紧的.同时给出Q2/known largest job/Cmax问题的一个下界, 并且证明Qmax 2算法的竞争比与最优算法竞争比之差不大于1/4.