无延迟加工约束下在线LPT算法关于平行机在线排序问题的性能

摘要

本文在无延迟加工约束下研究最小化最大完工时间m台平行机在线排序问题。这里的“无延迟加工”是指当工件到达时,如果有机器空闲则必须选择工件加工,即工件不能被延迟加工。当m ≥ 2时,证明无延迟加工约束下在线LPT算法是3/2–竞争的最好可能在线算法。如果所有工件都具有友好到达时间,首先给出无延迟加工约束下排序问题的下界分别为5/4 (当m = 2时)和4/3 (当m ≥ 3时),其次证明在线LPT算法是5/4–竞争的最好可能在线算法对两台平行机情形。