Comparing the minimum completion times of two longest-first scheduling-heuristics
For 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.
|Date of creation:||11 Jul 2010|
|Date of revision:|
|Publication status:||Published in: Central European Journal of Operations Research 21/1 (2013), 125-139.|
|Contact details of provider:|| Postal: |
Phone: +049 3641/ 9 43000
Fax: +049 3641/ 9 43000
Web page: http://www.wiwi.uni-jena.de/
More information through EDIRC
|Order Information:|| Postal: If a paper is not downloadable, please contact the author(s) or the library of University of Jena, not the archive maintainer.|
When requesting a correction, please mention this item's handle: RePEc:jen:jenjbe:2010-13. See general information about how to correct material in RePEc.
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.