Comparing the minimum completion times of two longest-first scheduling-heuristics

Rico Walter ()
Additional contact information
Rico Walter: Faculty of Economics and Business Administration, Friedrich Schiller University Jena

No 13/2010, Jena Research Papers in Business and Economics - Working and Discussion Papers (Expired!) from Friedrich Schiller University Jena, School of Economics and Business Administration

Abstract: 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.

Keywords: Scheduling; -; Identical; parallel; machines; -; Heuristics; -; Minimum; completion; time; -; Worst-case; analysis (search for similar items in EconPapers)
Date: 2010-12-09
References: Add references at CitEc
Citations:

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.

Downloads: (external link)
http://link.springer.com/content/pdf/10.1007%2Fs10100-011-0217-4 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jen:jenjbe:2010-13

Access Statistics for this paper

More papers in Jena Research Papers in Business and Economics - Working and Discussion Papers (Expired!) from Friedrich Schiller University Jena, School of Economics and Business Administration
Bibliographic data for series maintained by Markus Pasche ().