IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v316y2024i1p72-84.html
   My bibliography  Save this article

Tighter bounds for the harmonic bin packing algorithm

Author

Listed:
  • Epstein, Leah

Abstract

The harmonic algorithm, defined for online bin packing, partitions items into a fixed number M of classes of similar items, and packs each class independently and greedily in constant time for every packed item. The positive integer M is a parameter of the algorithm. This algorithm had a major role in the development of the online bin packing problem. Tight bounds on its asymptotic approximation ratio were known for M≤7, and for values of M with specific properties. The parametric variant of this algorithm, where item sizes are bounded from above by a certain value, was studied as well. We find tight bounds for many additional cases that were known as open, including the case M=8 for the classic problem.

Suggested Citation

  • Epstein, Leah, 2024. "Tighter bounds for the harmonic bin packing algorithm," European Journal of Operational Research, Elsevier, vol. 316(1), pages 72-84.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:1:p:72-84
    DOI: 10.1016/j.ejor.2024.01.051
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724000912
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.01.051?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. Fleszar, Krzysztof, 2022. "A MILP model and two heuristics for the Bin Packing Problem with Conflicts and Item Fragmentation," European Journal of Operational Research, Elsevier, vol. 303(1), pages 37-53.
    2. Witteman, Max & Deng, Qichen & Santos, Bruno F., 2021. "A bin packing approach to solve the aircraft maintenance task allocation problem," European Journal of Operational Research, Elsevier, vol. 294(1), pages 365-376.
    3. Schepler, Xavier & Rossi, André & Gurevsky, Evgeny & Dolgui, Alexandre, 2022. "Solving robust bin-packing problems with a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 831-843.
    4. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    5. Békési, József & Dósa, György & Galambos, Gábor, 2022. "A first Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays," European Journal of Operational Research, Elsevier, vol. 297(3), pages 844-852.
    6. Ekici, Ali, 2023. "A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1007-1020.
    7. János Balogh & Leah Epstein & Asaf Levin, 2021. "More on ordered open end bin packing," Journal of Scheduling, Springer, vol. 24(6), pages 589-614, December.
    8. Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    9. Arbib, Claudio & Marinelli, Fabrizio & Pizzuti, Andrea, 2021. "Number of bins and maximum lateness minimization in two-dimensional bin packing," European Journal of Operational Research, Elsevier, vol. 291(1), pages 101-113.
    10. Leah Epstein, 2023. "Parallel solutions for preemptive makespan scheduling on two identical machines," Journal of Scheduling, Springer, vol. 26(1), pages 61-76, February.
    11. Haouari, Mohamed & Mhiri, Mariem, 2024. "Lower and upper bounding procedures for the bin packing problem with concave loading cost," European Journal of Operational Research, Elsevier, vol. 312(1), pages 56-69.
    12. Leah Epstein, 2023. "Parallel solutions for ordinal scheduling with a small number of machines," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-24, August.
    13. Attila Bódis & János Balogh, 2019. "Bin packing problem with scenarios," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 377-395, June.
    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. Yulle G. F. Borges & Vinícius L. Lima & Flávio K. Miyazawa & Lehilton L. C. Pedrosa & Thiago A. Queiroz & Rafael C. S. Schouery, 2024. "Algorithms for the bin packing problem with scenarios," Journal of Combinatorial Optimization, Springer, vol. 48(4), pages 1-28, November.
    2. Leah Epstein, 2023. "Parallel solutions for ordinal scheduling with a small number of machines," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-24, August.
    3. Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
    4. David Fischer & Péter Györgyi, 2023. "Approximation algorithms for coupled task scheduling minimizing the sum of completion times," Annals of Operations Research, Springer, vol. 328(2), pages 1387-1408, September.
    5. Sciau, Jean-Baptiste & Goyon, Agathe & Sarazin, Alexandre & Bascans, Jérémy & Prud’homme, Charles & Lorca, Xavier, 2024. "Using constraint programming to address the operational aircraft line maintenance scheduling problem," Journal of Air Transport Management, Elsevier, vol. 115(C).
    6. Gudmundsson, Jens & Hougaard, Jens Leth & Platz, Trine Tornøe, 2023. "Decentralized task coordination," European Journal of Operational Research, Elsevier, vol. 304(2), pages 851-864.
    7. Wang, Mengyao & Zhou, Chenhao & Wang, Aihu, 2022. "A cluster-based yard template design integrated with yard crane deployment using a placement heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    8. Tao Dai & Xiangqi Fan, 2021. "Multi-Stove Scheduling for Sustainable On-Demand Food Delivery," Sustainability, MDPI, vol. 13(23), pages 1-13, November.
    9. Jiu, Song & Wang, Dan & Ma, Zujun, 2024. "Benders decomposition for robust distribution network design and operations in online retailing," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1069-1082.
    10. Khir, Reem & Erera, Alan & Toriello, Alejandro, 2023. "Robust planning of sorting operations in express delivery systems," European Journal of Operational Research, Elsevier, vol. 306(2), pages 615-631.
    11. Mohamed Amr Sultan & Tomaž Kramberger & Mahmoud Barakat & Ahmed Hussein Ali, 2023. "Barriers to Applying Last-Mile Logistics in the Egyptian Market: An Extension of the Technology Acceptance Model," Sustainability, MDPI, vol. 15(17), pages 1-25, August.
    12. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    13. Perboli, Guido & Brotcorne, Luce & Bruni, Maria Elena & Rosano, Mariangela, 2021. "A new model for Last-Mile Delivery and Satellite Depots management: The impact of the on-demand economy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    14. De Bock, Koen W. & Coussement, Kristof & Caigny, Arno De & Słowiński, Roman & Baesens, Bart & Boute, Robert N. & Choi, Tsan-Ming & Delen, Dursun & Kraus, Mathias & Lessmann, Stefan & Maldonado, Sebast, 2024. "Explainable AI for Operational Research: A defining framework, methods, applications, and a research agenda," European Journal of Operational Research, Elsevier, vol. 317(2), pages 249-272.
    15. Koen W. de Bock & Kristof Coussement & Arno De Caigny & Roman Slowiński & Bart Baesens & Robert N Boute & Tsan-Ming Choi & Dursun Delen & Mathias Kraus & Stefan Lessmann & Sebastián Maldonado & David , 2023. "Explainable AI for Operational Research: A Defining Framework, Methods, Applications, and a Research Agenda," Post-Print hal-04219546, HAL.
    16. Yingying Wang & Feng Xu & Zhe Lin & Jianying Guo & Gang Li, 2024. "Community Group Purchasing of Next-Day Delivery: Bridging the Last Mile Delivery for Urban Residents during COVID-19," Sustainability, MDPI, vol. 16(16), pages 1-20, August.
    17. van Kessel, Paul J. & Freeman, Floris C. & Santos, Bruno F., 2023. "Airline maintenance task rescheduling in a disruptive environment," European Journal of Operational Research, Elsevier, vol. 308(2), pages 605-621.
    18. Alotaibi, Naif M. & Scarf, Philip & Cavalcante, Cristiano A.V. & Lopes, Rodrigo S. & de Oliveira e Silva, André Luiz & Rodrigues, Augusto J.S. & Alyami, Salem A., 2023. "Modified-opportunistic inspection and the case of remote, groundwater well-heads," Reliability Engineering and System Safety, Elsevier, vol. 237(C).
    19. Rohit Kumar Singh & Sachin Modgil & Padmanav Acharya, 2019. "Assessment of Supply Chain Flexibility Using System Dynamics Modeling," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 20(1), pages 39-63, December.
    20. Shibasaki, Rui S. & Rossi, André & Gurevsky, Evgeny, 2024. "A new upper bound based on Dantzig-Wolfe decomposition to maximize the stability radius of a simple assembly line under uncertainty," European Journal of Operational Research, Elsevier, vol. 313(3), pages 1015-1030.

    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:eee:ejores:v:316:y:2024:i:1:p:72-84. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.