IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v17y2019i1d10.1007_s10288-018-0381-7.html
   My bibliography  Save this article

A note on posterior tight worst-case bounds for longest processing time schedules

Author

Listed:
  • Johnny C. Ho

    (Columbus State University)

  • Ivar Massabò

    (Università della Calabria)

  • Giuseppe Paletta

    (Università della Calabria)

  • Alex J. Ruiz-Torres

    (Universidad de Puerto Rico - Rio Piedras)

Abstract

This note proposes and analyzes a posterior tight worst-case bound for the longest processing time (LPT) heuristic for scheduling independent jobs on identical parallel machines with the objective of minimizing the makespan. It makes natural remarks on the well-known posterior worst-case bounds, and shows that the proposed bound can complement the well-known posterior bounds to synergistically achieve a better posterior worst-case bound for the LPT heuristic. Moreover, it gives some insight on LPT asymptotical optimality.

Suggested Citation

  • Johnny C. Ho & Ivar Massabò & Giuseppe Paletta & Alex J. Ruiz-Torres, 2019. "A note on posterior tight worst-case bounds for longest processing time schedules," 4OR, Springer, vol. 17(1), pages 97-107, March.
    • Handle: RePEc:spr:aqjoor:v:17:y:2019:i:1:d:10.1007_s10288-018-0381-7
    DOI: 10.1007/s10288-018-0381-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-018-0381-7
    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/s10288-018-0381-7?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. Frenk, J.B.G. & Rinnooy Kan, A.H.G., 1986. "The rate of convergence to optimality of the LPT rule," Econometric Institute Research Papers 11698, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. E. G. Coffman, Jr. & G. S. Lueker & A. H. G. Rinnooy Kan, 1988. "Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics," Management Science, INFORMS, vol. 34(3), pages 266-290, March.
    3. 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.
    4. Mauro Dell’Amico & Silvano Martello, 1995. "Optimal Scheduling of Tasks on Identical Parallel Processors," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 191-200, May.
    5. James D. Blocher & Suresh Chand, 1991. "Scheduling of parallel processors: A posterior bound on LPT sequencing and a two‐step algorithm," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 273-287, April.
    6. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    Full references (including those not matched with items on IDEAS)

    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. Bassem Jarboui & Saber Ibrahim & Abdelwaheb Rebai, 2010. "A new destructive bounding scheme for the bin packing problem," Annals of Operations Research, Springer, vol. 179(1), pages 187-202, September.
    2. Absalom E Ezugwu & Olawale J Adeleke & Serestina Viriri, 2018. "Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times," PLOS ONE, Public Library of Science, vol. 13(7), pages 1-23, July.
    3. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    4. 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.
    5. Dell'Amico, Mauro & Iori, Manuel & Martello, Silvano & Monaci, Michele, 2006. "Lower bounds and heuristic algorithms for the ki-partitioning problem," European Journal of Operational Research, Elsevier, vol. 171(3), pages 725-742, June.
    6. Alexander Lawrinenko & Stefan Schwerdfeger & Rico Walter, 2018. "Reduction criteria, upper bounds, and a dynamic programming based heuristic for the max–min $$k_i$$ k i -partitioning problem," Journal of Heuristics, Springer, vol. 24(2), pages 173-203, April.
    7. Fröhlich von Elmbach, Alexander & Scholl, Armin & Walter, Rico, 2019. "Minimizing the maximal ergonomic burden in intra-hospital patient transportation," European Journal of Operational Research, Elsevier, vol. 276(3), pages 840-854.
    8. 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.
    9. Mauro Dell'Amico & Silvano Martello, 1999. "Reduction of the Three-Partition Problem," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 17-30, July.
    10. Guopeng Song & Roel Leus, 2022. "Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3059-3079, November.
    11. Michael Brusco & Hans Köhn & Douglas Steinley, 2013. "Exact and approximate methods for a one-dimensional minimax bin-packing problem," Annals of Operations Research, Springer, vol. 206(1), pages 611-626, July.
    12. Silvano Martello & David Pisinger & Daniele Vigo, 2000. "The Three-Dimensional Bin Packing Problem," Operations Research, INFORMS, vol. 48(2), pages 256-267, April.
    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. Mauro Dell'Amico & Manuel Iori & Silvano Martello & Michele Monaci, 2008. "Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 333-344, August.
    15. Oluf Faroe & David Pisinger & Martin Zachariasen, 2003. "Guided Local Search for the Three-Dimensional Bin-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 267-283, August.
    16. 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.
    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.
    18. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    19. Lin, Hung-Tso & Liao, Ching-Jong, 2003. "A case study in a two-stage hybrid flow shop with setup time and dedicated machines," International Journal of Production Economics, Elsevier, vol. 86(2), pages 133-143, November.
    20. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.

    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:aqjoor:v:17:y:2019:i:1:d:10.1007_s10288-018-0381-7. 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.