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

The circular balancing problem

Author

Listed:
  • Lee, Myungho
  • Lee, Kangbok
  • Pinedo, Michael

Abstract

We propose a balancing problem with a minmax objective in a circular setting. This balancing problem involves the arrangement of an even number of items with different weights on a circle while minimizing the maximum total weight of items arranged on any half circle. Due to its generic structure, it may have applications in fair resource allocation schemes. We show the NP-hardness of the problem and develop polynomial-time algorithms when the number of distinct weights is a fixed constant. We propose for the general case a tight 7/6-approximation algorithm and show that it performs better than two existing algorithms designed for an equivalent problem in the literature. The worst-case performance ratio is derived through a linear combination of valid inequalities that are obtained from the problem definition, the properties of the proposed algorithm, and the optimal circular permutation structure. Furthermore, we formulate a more general problem of minimizing the maximum total weight of items on equally divided circular sectors and present its computational complexity and a tight approximation algorithm.

Suggested Citation

  • Lee, Myungho & Lee, Kangbok & Pinedo, Michael, 2025. "The circular balancing problem," European Journal of Operational Research, Elsevier, vol. 321(1), pages 41-56.
    • Handle: RePEc:eee:ejores:v:321:y:2025:i:1:p:41-56
    DOI: 10.1016/j.ejor.2024.08.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172400643X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.08.020?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. Hermelin, Danny & Pinedo, Michael & Shabtay, Dvir & Talmon, Nimrod, 2019. "On the parameterized tractability of single machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 273(1), pages 67-73.
    2. Choi, Wonjoon & Kang, Haeyong & Baek, Taehyun, 1999. "A turbine-blade balancing problem," International Journal of Production Economics, Elsevier, vol. 60(1), pages 405-410, April.
    3. Xiaotie Deng & Qi Qi & Amin Saberi, 2012. "Algorithmic Solutions for Envy-Free Cake Cutting," Operations Research, INFORMS, vol. 60(6), pages 1461-1476, December.
    4. Cambazard, Hadrien & Catusse, Nicolas, 2018. "Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane," European Journal of Operational Research, Elsevier, vol. 270(2), pages 419-429.
    5. Pitsoulis, Leonidas S. & Pardalos, Panos M. & Hearn, Donald W., 2001. "Approximate solutions to the turbine balancing problem," European Journal of Operational Research, Elsevier, vol. 130(1), pages 147-155, April.
    6. Dorit S. Hochbaum & Xu Rao, 2019. "The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem," Operations Research, INFORMS, vol. 67(5), pages 1345-1361, September.
    7. Hanen, Claire & Hanzalek, Zdenek, 2020. "Grouping tasks to save energy in a cyclic scheduling problem: A complexity study," European Journal of Operational Research, Elsevier, vol. 284(2), pages 445-459.
    8. Samir V. Amiouny & John J. Bartholdi & John H. Vande Vate, 2000. "Heuristics for Balancing Turbine Fans," Operations Research, INFORMS, vol. 48(4), pages 591-602, August.
    9. Laporte, Gilbert & Mercure, Helene, 1988. "Balancing hydraulic turbine runners: A quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 35(3), pages 378-381, June.
    10. Hamilton Emmons & Richard N. Burns, 1991. "Off-Day Scheduling with Hierarchical Worker Categories," Operations Research, INFORMS, vol. 39(3), pages 484-495, June.
    11. Munier, A., 1996. "The complexity of a cyclic scheduling problem with identical machines and precedence constraints," European Journal of Operational Research, Elsevier, vol. 91(3), pages 471-480, 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. Lingfa Lu & Liqi Zhang, 2023. "Scheduling problems with rejection to minimize the k-th power of the makespan plus the total rejection cost," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-17, August.
    2. Ma, Ran & Guo, Sainan & Miao, Cuixia, 2021. "A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection," Applied Mathematics and Computation, Elsevier, vol. 392(C).
    3. George Polak, 2005. "On A Special Case of the Quadratic Assignment Problem with an Application to Storage-and-Retrieval Devices," Annals of Operations Research, Springer, vol. 138(1), pages 223-233, September.
    4. Dmitry Kruchinin & Vladimir Kruchinin & Yuriy Shablya, 2021. "Method for Obtaining Coefficients of Powers of Bivariate Generating Functions," Mathematics, MDPI, vol. 9(4), pages 1-17, February.
    5. AERTS, Babiche & CORNELISSENS, Trijntje & SÖRENSEN, Kenneth, 2020. "Solving the joint order batching and picker routing problem, as a clustered vehicle routing problem," Working Papers 2020003, University of Antwerp, Faculty of Business and Economics.
    6. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    7. Danny Hermelin & Matthias Mnich & Simon Omlor, 2024. "Serial batching to minimize the weighted number of tardy jobs," Journal of Scheduling, Springer, vol. 27(6), pages 545-556, December.
    8. Hertz, Alain & Lahrichi, Nadia & Widmer, Marino, 2010. "A flexible MILP model for multiple-shift workforce planning under annualized hours," European Journal of Operational Research, Elsevier, vol. 200(3), pages 860-873, February.
    9. Imed Kacem & Hans Kellerer, 2024. "Minimizing the maximum lateness for scheduling with release times and job rejection," Journal of Combinatorial Optimization, Springer, vol. 48(3), pages 1-22, October.
    10. Rajabighamchi, Farzaneh & van Hoesel, Stan & Defryn, Christof, 2023. "Graph reduction for the planar Travelling Salesman Problem," Research Memorandum 004, Maastricht University, Graduate School of Business and Economics (GSBE).
    11. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.
    12. Osman Kazan & Milind Dawande & Chelliah Sriskandarajah & Kathryn E. Stecke, 2012. "Balancing perfectly periodic service schedules: An application from recycling and waste management," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(2), pages 160-171, March.
    13. Michael J. Brusco & Larry W. Jacobs, 1998. "Personnel Tour Scheduling When Starting-Time Restrictions Are Present," Management Science, INFORMS, vol. 44(4), pages 534-547, April.
    14. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    15. Bilò, Vittorio & Caragiannis, Ioannis & Flammini, Michele & Igarashi, Ayumi & Monaco, Gianpiero & Peters, Dominik & Vinci, Cosimo & Zwicker, William S., 2022. "Almost envy-free allocations with connected bundles," Games and Economic Behavior, Elsevier, vol. 131(C), pages 197-221.
    16. Zvi Drezner & Peter Hahn & Éeric Taillard, 2005. "Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods," Annals of Operations Research, Springer, vol. 139(1), pages 65-94, October.
    17. Vittorio Bil`o & Ioannis Caragiannis & Michele Flammini & Ayumi Igarashi & Gianpiero Monaco & Dominik Peters & Cosimo Vinci & William S. Zwicker, 2018. "Almost Envy-Free Allocations with Connected Bundles," Papers 1808.09406, arXiv.org, revised May 2022.
    18. Pitsoulis, Leonidas S. & Pardalos, Panos M. & Hearn, Donald W., 2001. "Approximate solutions to the turbine balancing problem," European Journal of Operational Research, Elsevier, vol. 130(1), pages 147-155, April.
    19. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    20. Erel Segal-Halevi & Shmuel Nitzan & Avinatan Hassidim & Yonatan Aumann, 2020. "Envy-Free Division of Land," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 896-922, August.

    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:321:y:2025:i:1:p:41-56. 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.