A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
复制标题
DOI：
10.1016/j.ejor.2008.02.008
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
Christos Koulamas;George J. Kyparisis
中科院分区：
文献类型：
--
作者：
Christos Koulamas;George J. Kyparisis
针对两台均匀机器最小化完工时间问题，提出了一种改进的最长加工时间启发式算法。MLPT算法首先最优地调度三个最长的作业，然后是根据LPT规则排序的剩余作业。我们证明了MLPT算法的严格最坏情况比率界为1.5=1.2247，这是对LPT算法的严格最坏情况比率界1.28的改进。
We propose a modified longest processing time (MLPT) heuristic algorithm for the two uniform machine makespan minimization problem. The MLPT algorithm schedules the three longest jobs optimally first, followed by the remaining jobs sequenced according to the LPT rule. We prove the tight worst-case ratio bound of 1.5=1.2247 for the MLPT algorithm which is an improvement over the tight worst-case ratio bound of 1.28 for the LPT algorithm.