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:||09 Feb 2017|
|Publication status:||Published as "Comparing the minimum completion times of two longest-first scheduling-heuristics", in: Central European Journal of Operations Research 21/1 (2013), 125-139.|
|Contact details of provider:|| Web page: http://www.wiwi.uni-jena.de/|
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.