论文部分内容阅读
本文考虑已知工件最大加工时间的三台同类机半在线问题。三台机器的速度分别为s1=r,s2=1,s3=s〉1,1≤r≤s,工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是己知的,目标函数为极小化最大机器负载。本文证明任何解此问题的算法竞争比的下界为3/2且给出Qmax3算法并证明此算法的竞争比不大于2(r+s+1)/2r+s(1〈s≤2)和r+2s+1/r+s(s〉2)。