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

LPT Online Strategy for Parallel-Machine Scheduling of Jobs with Non-Delayed Processing Constraint

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

Abstract: This paper studies the m parallel-machines online schedule under the non-delayed processing constraint to minimize the maximum completion times of jobs. Here “non-delayed processing” means that the available jobs cannot be delayed for processing when some machine is idle. When m ≥ 2, this paper shows that the online LPT algorithm is a 3/2-competitive best possible online algorithm. For the restricted version in which the jobs have kind release times, this paper first shows that the online LPT algorithm is a best possible online algorithm with a competitive ratio of 5/4 for the case m = 2, and then presents a lower bound of 4/3 for the case m ≥ 3.