Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477287 | European Journal of Operational Research | 2009 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Christos Koulamas, George J. Kyparisis,