IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2023i1p6-d1303246.html
   My bibliography  Save this article

Developing New Bounds for the Performance Guarantee of the Jump Neighborhood for Scheduling Jobs on Uniformly Related Machines

Author

Listed:
  • Felipe T. Muñoz

    (Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile)

  • Guillermo Latorre-Núñez

    (Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile)

  • Mario Ramos-Maldonado

    (Departamento de Ingeniería en Maderas, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4051381, Chile)

Abstract

This study investigates the worst-case performance guarantee of locally optimal solutions to minimize the total weighted completion time on uniformly related parallel machines. The investigated neighborhood structure is Jump, also called insertion or move. This research focused on establishing the local optimality condition expressed as an inequality and mapping that maps a schedule into an inner product space so that the norm of the mapping is closely related to the total weighted completion time of the schedule. We determine two new upper bounds for the performance guarantee, which take the form of an expression based on parameters that describe the family of instances: the speed of the fastest machine, the speed of the slowest machine, and the number of machines. These new bounds outperform the parametric upper bound previously established in the existing literature and enable a better understanding of the performance of the solutions obtained for the Jump neighborhood in this scheduling problem, according to parameters that describe the family of instances.

Suggested Citation

  • Felipe T. Muñoz & Guillermo Latorre-Núñez & Mario Ramos-Maldonado, 2023. "Developing New Bounds for the Performance Guarantee of the Jump Neighborhood for Scheduling Jobs on Uniformly Related Machines," Mathematics, MDPI, vol. 12(1), pages 1-16, December.
    • Handle: RePEc:gam:jmathe:v:12:y:2023:i:1:p:6-:d:1303246
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/1/6/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/1/6/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Martin Skutella & Gerhard J. Woeginger, 2000. "A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 63-75, February.
    2. Bin Ji & Xin Xiao & Samson S. Yu & Guohua Wu, 2023. "A Hybrid Large Neighborhood Search Method for Minimizing Makespan on Unrelated Parallel Batch Processing Machines with Incompatible Job Families," Sustainability, MDPI, vol. 15(5), pages 1-25, February.
    3. W. A. Horn, 1973. "Technical Note—Minimizing Average Flow Time with Parallel Machines," Operations Research, INFORMS, vol. 21(3), pages 846-847, June.
    4. Ethem Çanakoğlu & İbrahim Muter, 2021. "Identical parallel machine scheduling with discrete additional resource and an application in audit scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 59(17), pages 5321-5336, September.
    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. Cole, Richard & Correa, Jose & Gkatzelis, Vasillis & Mirrokni, Vahab & Olver, Neil, 2015. "Decentralized utilitarian mechanisms for scheduling games," LSE Research Online Documents on Economics 103081, London School of Economics and Political Science, LSE Library.
    2. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.
    3. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    4. Han Hoogeveen & Petra Schuurman & Gerhard J. Woeginger, 2001. "Non-Approximability Results for Scheduling Problems with Minsum Criteria," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 157-168, May.
    5. Nicole Megow & Marc Uetz & Tjark Vredeveld, 2006. "Models and Algorithms for Stochastic Online Scheduling," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 513-525, August.
    6. Rabia Nessah & Chengbin Chu, 2010. "Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods," Annals of Operations Research, Springer, vol. 181(1), pages 359-375, December.
    7. Alberto Caprara & Andrea Lodi & Michele Monaci, 2005. "Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 150-172, February.
    8. Jiang, Xiaojuan & Lee, Kangbok & Pinedo, Michael L., 2021. "Ideal schedules in parallel machine settings," European Journal of Operational Research, Elsevier, vol. 290(2), pages 422-434.
    9. Marcin Siepak & Jerzy Józefczyk, 2014. "Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion," Annals of Operations Research, Springer, vol. 222(1), pages 517-533, November.
    10. Tjark Vredeveld & Cor Hurkens, 2002. "Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 175-189, May.
    11. Ali Allahverdi & John Mittenthal, 1994. "Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(5), pages 677-682, August.
    12. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "An Introduction To Multiprocessor Scheduling," Econometric Institute Archives 272258, Erasmus University Rotterdam.
    13. Dušan Knop & Martin Koutecký, 2018. "Scheduling meets n-fold integer programming," Journal of Scheduling, Springer, vol. 21(5), pages 493-503, October.
    14. Jan Karel Lenstra & Franz Rendl & Frits Spieksma & Marc Uetz, 2022. "In memoriam Gerhard Woeginger," Journal of Scheduling, Springer, vol. 25(5), pages 503-505, October.
    15. Celia A. Glass & Hans Kellerer, 2007. "Parallel machine scheduling with job assignment restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(3), pages 250-257, April.
    16. Leah Epstein & Ido Yatsiv, 2017. "Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times," Journal of Scheduling, Springer, vol. 20(2), pages 115-127, April.
    17. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    18. Hongmin Li & Woonghee T. Huh & Matheus C. Sampaio & Naiping Keng, 2021. "Planning Production and Equipment Qualification under High Process Flexibility," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3369-3390, October.
    19. José R. Correa & Martin Skutella & José Verschae, 2012. "The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 379-398, May.
    20. Juntaek Hong & Kangbok Lee & Michael L. Pinedo, 2020. "Scheduling equal length jobs with eligibility restrictions," Annals of Operations Research, Springer, vol. 285(1), pages 295-314, February.

    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:gam:jmathe:v:12:y:2023:i:1:p:6-:d:1303246. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.