考虑已知工件最大加工时间的两台同类机半在线问题．机器M1,M2的速度分别为s1=1,s2=s(s≥1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载．此...考虑已知工件最大加工时间的两台同类机半在线问题．机器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.展开更多
文摘考虑已知工件最大加工时间的两台同类机半在线问题．机器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.
