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

作者：罗润梓; 孙世杰; 何龙敏

来源：工程数学学报, 2010, 27(01): 53-64.

• 排序
• 半在线
• 竞争比

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

• 单位
  南昌大学理学院; 上海大学