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

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

作　　者：李文杰[1] 

机构地区：[1]洛阳师范学院,数学科学学院,河南 洛阳

出　　处：《应用数学进展》2022年第3期991-995,共5页Advances in Applied Mathematics

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

关 键 词：在线排序 在线算法 无延迟加工 最大完工时间 

分 类 号：O223[理学—运筹学与控制论]