IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v23y2020i2d10.1007_s10951-018-0597-6.html
   My bibliography  Save this article

The Longest Processing Time rule for identical parallel machines revisited

Author

Listed:
  • Federico Della Croce

    (Politecnico di Torino
    CNR, IEIIT)

  • Rosario Scatamacchia

    (Politecnico di Torino)

Abstract

We consider the $$P_m || C_{\max }$$Pm||Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines $$(m

Suggested Citation

  • Federico Della Croce & Rosario Scatamacchia, 2020. "The Longest Processing Time rule for identical parallel machines revisited," Journal of Scheduling, Springer, vol. 23(2), pages 163-176, April.
    • Handle: RePEc:spr:jsched:v:23:y:2020:i:2:d:10.1007_s10951-018-0597-6
    DOI: 10.1007/s10951-018-0597-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0597-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0597-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wil Michiels & Jan Korst & Emile Aarts & Jan van Leeuwen, 2007. "Performance ratios of the Karmarkar-Karp differencing method," Journal of Combinatorial Optimization, Springer, vol. 13(1), pages 19-32, January.
    2. Yong He & Hans Kellerer & Vladimir Kotov, 2000. "Linear compound algorithms for the partitioning problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(7), pages 593-601, October.
    3. Paul Mireault & James B. Orlin & Rakesh V. Vohra, 1997. "A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines," Operations Research, INFORMS, vol. 45(1), pages 116-125, February.
    4. Antonio Frangioni & Emiliano Necciari & Maria Grazia Scutellà, 2004. "A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 8(2), pages 195-220, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Myungho Lee & Kangbok Lee & Michael Pinedo, 2022. "Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs," Journal of Scheduling, Springer, vol. 25(6), pages 721-740, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Federico Della Croce & Rosario Scatamacchia & Vincent T’kindt, 2019. "A tight linear time $$\frac{13}{12}$$ 13 12 -approximation algorithm for the $$P2 || C_{\max }$$ P 2 | | C max problem," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 608-617, August.
    2. Petra Schuurman & Tjark Vredeveld, 2007. "Performance Guarantees of Local Search for Multiprocessor Scheduling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 52-63, February.
    3. Koulamas, Christos & Kyparisis, George J., 2009. "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 61-68, July.
    4. Tobias Brueggemann & Johann L. Hurink & Tjark Vredeveld & Gerhard J. Woeginger, 2011. "Exponential size neighborhoods for makespan minimization scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 795-803, December.
    5. Alan J. Soper & Vitaly A. Strusevich, 2021. "Parametric analysis of the quality of single preemption schedules on three uniform parallel machines," Annals of Operations Research, Springer, vol. 298(1), pages 469-495, March.
    6. Christos Koulamas & George J. Kyparisis, 2006. "A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(6), pages 568-575, September.
    7. Ivar Massabò & Giuseppe Paletta & Alex J. Ruiz-Torres, 2016. "A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem," Journal of Scheduling, Springer, vol. 19(2), pages 207-211, April.
    8. Rico Walter & Martin Wirth & Alexander Lawrinenko, 2017. "Improved approaches to the exact solution of the machine covering problem," Journal of Scheduling, Springer, vol. 20(2), pages 147-164, April.
    9. Qian Cao & Zhaohui Liu, 2010. "Semi-online scheduling with known maximum job size on two uniform machines," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 369-384, November.
    10. Olawale James, GBADEYAN, & Jamiu Ola, IDRIS & Kayode Olawale, KUMOYE, & Tayo Akindele, ZUBAIR,, 2016. "Assessing The Security Of Learning Spaces In Selected Primary Schools Within Ilorin Metropolis," Ilorin Journal of Business and Social Sciences, Faculty of Social Sciences, University of Ilorin, vol. 18(2), pages 179-198, October.
    11. Kris Boudt & Edgars Jakobsons & Steven Vanduffel, 2018. "Block rearranging elements within matrix columns to minimize the variability of the row sums," 4OR, Springer, vol. 16(1), pages 31-50, March.
    12. Liao, Ching-Jong & Lin, Chien-Hung, 2003. "Makespan minimization for two uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 84(2), pages 205-213, May.
    13. Daniel Kowalczyk & Roel Leus, 2017. "An exact algorithm for parallel machine scheduling with conflicts," Journal of Scheduling, Springer, vol. 20(4), pages 355-372, August.
    14. Rohde, K.I.M., 2005. "A reason for sophisticated investors not to seize arbitrage opportunities in markets without frictions," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    15. Leah Epstein, 2018. "A survey on makespan minimization in semi-online environments," Journal of Scheduling, Springer, vol. 21(3), pages 269-284, June.
    16. Cheang, Brenda & Gao, Xiang & Lim, Andrew & Qin, Hu & Zhu, Wenbin, 2012. "Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints," European Journal of Operational Research, Elsevier, vol. 223(1), pages 60-75.
    17. Rico Walter & Alexander Lawrinenko, 2020. "A characterization of optimal multiprocessor schedules and new dominance rules," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 876-900, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:23:y:2020:i:2:d:10.1007_s10951-018-0597-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.