论文部分内容阅读
本文考虑已知工件最大加工时间的三台同类机半在线问题。三台机器的速度分别为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）。