A modified LPT algorithm for the two uniform parallel machine makespan minimization problem

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 for the MLPT algorithm which is an improvement over the tight worst-case ratio bound of 1.28 for the LPT algorithm.

MoreLess

Year of publication:	2009
Authors:	Koulamas, Christos ; Kyparisis, George J.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 196.2009, 1, p. 61-68
Publisher:	Elsevier
Keywords:	Scheduling Uniform parallel machines LPT Approximation algorithms

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005337204