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.
Article PDF
Avoid common mistakes on your manuscript.
References
Arnold BC, Balakrishnan N, Nagaraja HN (1992) A first course in order statistics. Wiley, New York
Azar Y, Epstein L (1997) On-line machine covering. Lect Notes Comput Sci 1284: 23–36
Coffman EG Jr, Langston MA (1984) A performance guarantee for the greedy set-partitioning algorithm. Acta Informatica 21: 409–415
Coffman EG Jr, Sethi R (1976) Algorithms minimizing mean flow time: schedule-length properties. Acta Informatica 6: 1–14
Csirik J, Kellerer H, Woeginger G (1992) The exact LPT-bound for maximizing the minimum completion time. Oper Res Lett 11: 281–287
Deuermeyer BL, Friesen DK, Langston MA (1982) Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J Algebraic Discret Methods 3: 190–196
Friesen DK, Deuermeyer BL (1981) Analysis of greedy solutions for a replacement part sequencing problem. Math Oper Res 6: 74–87
Haouari M, Jemmali M (2008) Maximizing the minimum completion time on parallel machines. 4OR Q J Oper Res 6: 375–392
He Y, Tan ZY (2002) Ordinal on-line scheduling for maximizing the minimum machine completion time. J Comb Optim 6: 199–206
Tsai L-H (1992) Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM J Comput 21: 59–64
Woeginger GJ (1997) A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper Res Lett 20: 149–154
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Walter, R. Comparing the minimum completion times of two longest-first scheduling-heuristics. Cent Eur J Oper Res 21, 125–139 (2013). https://doi.org/10.1007/s10100-011-0217-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-011-0217-4