IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i5d10.1007_s10878-023-01061-2.html
   My bibliography  Save this article

The balanced maximally diverse grouping problem with integer attribute values

Author

Listed:
  • Arne Schulz

    (Universität Hamburg)

Abstract

The paper considers the assignment of items to groups according to their attribute values such that the groups are as balanced as possible. Although the problem is in general NP-hard, we prove that it can be solved in pseudo-polynomial time if attribute values are integer. We point out a relation to partition and more general to multi-way number partitioning. Furthermore, we introduce a mixed-integer programming (MIP) formulation, a variable reduction technique, and an efficient lower bound for the objective value. Our computational results show that the lower bound meets the optimal objective value in the most of our instances of realistic size. Hence, the MIP solves instances with several thousand items within seconds to optimality.

Suggested Citation

  • Arne Schulz, 2023. "The balanced maximally diverse grouping problem with integer attribute values," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-27, July.
    • Handle: RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01061-2
    DOI: 10.1007/s10878-023-01061-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-023-01061-2
    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/s10878-023-01061-2?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. B Zhang & P Murali & M M Dessouky & D Belson, 2009. "A mixed integer programming approach for allocating operating room capacity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(5), pages 663-673, May.
    2. Adan, Ivo & Bekkers, Jos & Dellaert, Nico & Jeunet, Jully & Vissers, Jan, 2011. "Improving operational effectiveness of tactical master plans for emergency and elective patients under stochastic demand and capacitated resources," European Journal of Operational Research, Elsevier, vol. 213(1), pages 290-308, August.
    3. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    4. Lai, Xiangjing & Hao, Jin-Kao, 2016. "Iterated maxima search for the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 254(3), pages 780-800.
    5. Michael Samudra & Erik Demeulemeester & Brecht Cardoen & Nancy Vansteenkiste & Frank E. Rademakers, 2017. "Due time driven surgery scheduling," Health Care Management Science, Springer, vol. 20(3), pages 326-352, September.
    6. Rex Cutshall & Srinagesh Gavirneni & Kenneth Schultz, 2007. "Indiana University’s Kelley School of Business Uses Integer Programming to Form Equitable, Cohesive Student Teams," Interfaces, INFORMS, vol. 37(3), pages 265-276, June.
    7. B M Baker & C Benn, 2001. "Assigning pupils to tutor groups in a comprehensive school," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(6), pages 623-629, June.
    8. Dmitry Krass & Anton Ovchinnikov, 2006. "The University of Toronto’s Rotman School of Management Uses Management Science to Create MBA Study Groups," Interfaces, INFORMS, vol. 36(2), pages 126-137, April.
    9. Astaraky, Davood & Patrick, Jonathan, 2015. "A simulation based approximate dynamic programming approach to multi-class, multi-resource surgical scheduling," European Journal of Operational Research, Elsevier, vol. 245(1), pages 309-319.
    10. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    11. Schulz, Arne, 2021. "The balanced maximally diverse grouping problem with block constraints," European Journal of Operational Research, Elsevier, vol. 294(1), pages 42-53.
    12. Cardoen, Brecht & Demeulemeester, Erik & Beliën, Jeroen, 2010. "Operating room planning and scheduling: A literature review," European Journal of Operational Research, Elsevier, vol. 201(3), pages 921-932, March.
    13. Arne Schulz & Malte Fliedner, 2023. "Minimizing the expected waiting time of emergency jobs," Journal of Scheduling, Springer, vol. 26(2), pages 147-167, April.
    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. Arne Schulz, 2024. "Efficient neighborhood evaluation for the maximally diverse grouping problem," Annals of Operations Research, Springer, vol. 341(2), pages 1247-1265, October.

    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. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    2. Arne Schulz, 2024. "Efficient neighborhood evaluation for the maximally diverse grouping problem," Annals of Operations Research, Springer, vol. 341(2), pages 1247-1265, October.
    3. Michael Samudra & Carla Van Riet & Erik Demeulemeester & Brecht Cardoen & Nancy Vansteenkiste & Frank E. Rademakers, 2016. "Scheduling operating rooms: achievements, challenges and pitfalls," Journal of Scheduling, Springer, vol. 19(5), pages 493-525, October.
    4. Thomas Schneider, A.J. & Theresia van Essen, J. & Carlier, Mijke & Hans, Erwin W., 2020. "Scheduling surgery groups considering multiple downstream resources," European Journal of Operational Research, Elsevier, vol. 282(2), pages 741-752.
    5. Zhang, Jian & Dridi, Mahjoub & El Moudni, Abdellah, 2019. "A two-level optimization model for elective surgery scheduling with downstream capacity constraints," European Journal of Operational Research, Elsevier, vol. 276(2), pages 602-613.
    6. Shuwan Zhu & Wenjuan Fan & Shanlin Yang & Jun Pei & Panos M. Pardalos, 2019. "Operating room planning and surgical case scheduling: a review of literature," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 757-805, April.
    7. Sean Harris & David Claudio, 2022. "Current Trends in Operating Room Scheduling 2015 to 2020: a Literature Review," SN Operations Research Forum, Springer, vol. 3(1), pages 1-42, March.
    8. Schulz, Arne, 2021. "The balanced maximally diverse grouping problem with block constraints," European Journal of Operational Research, Elsevier, vol. 294(1), pages 42-53.
    9. Michael R. Miller & Robert J. Alexander & Vincent A. Arbige & Robert F. Dell & Steven R. Kremer & Brian P. McClune & Jane E. Oppenlander & Joshua P. Tomlin, 2017. "Optimal Allocation of Students to Naval Nuclear-Power Training Units," Interfaces, INFORMS, vol. 47(4), pages 320-335, August.
    10. Nahid Rezaeinia & Julio César Góez & Mario Guajardo, 2022. "Efficiency and fairness criteria in the assignment of students to projects," Annals of Operations Research, Springer, vol. 319(2), pages 1717-1735, December.
    11. Sebastian Rachuba & Brigitte Werners, 2017. "A fuzzy multi-criteria approach for robust operating room schedules," Annals of Operations Research, Springer, vol. 251(1), pages 325-350, April.
    12. Aisha Tayyab & Saif Ullah & Mohammed Fazle Baki, 2023. "An Outer Approximation Method for Scheduling Elective Surgeries with Sequence Dependent Setup Times to Multiple Operating Rooms," Mathematics, MDPI, vol. 11(11), pages 1-15, May.
    13. Duma, Davide & Aringhieri, Roberto, 2019. "The management of non-elective patients: shared vs. dedicated policies," Omega, Elsevier, vol. 83(C), pages 199-212.
    14. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    15. Binyamin Krauss & Jon Lee & Daniel Newman, 2013. "Optimizing the Assignment of Students to Classes in an Elementary School," INFORMS Transactions on Education, INFORMS, vol. 14(1), pages 39-44, September.
    16. Gökalp, E. & Gülpınar, N. & Doan, X.V., 2023. "Dynamic surgery management under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(2), pages 832-844.
    17. Silva, Thiago A.O. & de Souza, Mauricio C., 2020. "Surgical scheduling under uncertainty by approximate dynamic programming," Omega, Elsevier, vol. 95(C).
    18. Javiera Barrera & Rodrigo A. Carrasco & Susana Mondschein & Gianpiero Canessa & David Rojas-Zalazar, 2020. "Operating room scheduling under waiting time constraints: the Chilean GES plan," Annals of Operations Research, Springer, vol. 286(1), pages 501-527, March.
    19. Mahdi Noorizadegan & Abbas Seifi, 2018. "An efficient computational method for large scale surgery scheduling problems with chance constraints," Computational Optimization and Applications, Springer, vol. 69(2), pages 535-561, March.
    20. Brecht Cardoen & Jeroen Beliën & Mario Vanhoucke, 2015. "On the design of custom packs: grouping of medical disposable items for surgeries," International Journal of Production Research, Taylor & Francis Journals, vol. 53(24), pages 7343-7359, December.

    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:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01061-2. 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.