Comparing the minimum completion times of two longest-first scheduling-heuristics
AbstractFor the basic problem of non-preemptively scheduling n independent jobs on m identical parallel machines so that the minimum (or earliest) machine completion time is maximized, we compare the performance relationship between two well-known longest-first heuristics - the LPT- (longest processing time) and the RLPT-heuristic (restricted LPT). We provide insights into the solution structure of these two sequencing heuristics and prove that the minimum completion time of the LPT-schedule is at least as long as the minimum completion time of the RLPT-schedule. Furthermore, we show that the minimum completion time of the RLPT-heuristic always remains within a factor of 1/m of the optimal minimum completion time. The paper finishes with a comprehensive experimental study of the probabilistic behavior of RLPT-schedules compared to LPT-schedules in the two-machine case.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Friedrich-Schiller-University Jena, School of Economics and Business Administration in its series Jena Research Papers in Business and Economics - Working and Discussion Papers with number 13/2010.
Date of creation: 11 Jul 2010
Date of revision:
Publication status: Published in: Central European Journal of Operations Research 21/1 (2013), 125-139.
Postal: If a paper is not downloadable, please contact the author(s) or the library of University of Jena, not the archive maintainer.
This paper has been announced in the following NEP Reports:
- NEP-ALL-2010-11-20 (All new papers)
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ().
If references are entirely missing, you can add them using this form.