论文部分内容阅读
本文研究一类具有特殊工件的平行机在线排序问题，目标是最小化最大完工时间．此模型有两种工件：正常工件和特殊工件．正常工件能够在m台平行机的任何一台机器上加工，而特殊工件仅能够在它唯一被指定的机器上加工．文中所有特殊工件的指定机器为M1．我们提供了竞争比为（2m^2-2m＋1）／（m^2-m＋1）的在线近似算法．当m=2时，算法是最好可能的．当m=3时，算法的竞争比为13／7≈1．857，并且提供了竞争比的下界（1＋√33）／4≈1．686．