IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v112y2008i1p96-108.html
   My bibliography  Save this article

Solving surgical cases assignment problem by a branch-and-price approach

Author

Listed:
  • Fei, H.
  • Chu, C.
  • Meskens, N.
  • Artiba, A.

Abstract

In this paper, we study a surgical cases assignment problem (SCAP) of assigning a set of surgical cases to several multifunctional operating rooms with an objective of minimizing total operating cost. Firstly, we formulate this problem as an integer problem and then reformulate the integer program by using Dantzig-Wolf decomposition as a set partitioning problem. Based on this set partitioning formulation, a so-called branch-and-price exact solution algorithm, combining Branch-and-Bound procedure with column generation (CG) method, is designed for the proposed problem where each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a CG approach in which each column represents a plan for one operating room and is generated by solving a sub-problem (SP) of single operating room planning problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.

Suggested Citation

  • Fei, H. & Chu, C. & Meskens, N. & Artiba, A., 2008. "Solving surgical cases assignment problem by a branch-and-price approach," International Journal of Production Economics, Elsevier, vol. 112(1), pages 96-108, March.
    • Handle: RePEc:eee:proeco:v:112:y:2008:i:1:p:96-108
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(07)00129-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Vissers, Jan M. H., 1998. "Patient flow-based allocation of inpatient resources: A case study," European Journal of Operational Research, Elsevier, vol. 105(2), pages 356-370, March.
    2. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    3. Hifi, M. & Zissimopoulos, V., 1996. "A recursive exact algorithm for weighted two-dimensional cutting," European Journal of Operational Research, Elsevier, vol. 91(3), pages 553-564, June.
    4. Chen, Zhi-Long & Powell, Warren B., 1999. "A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 220-232, July.
    5. John T. Blake & Joan Donald, 2002. "Mount Sinai Hospital Uses Integer Programming to Allocate Operating Room Time," Interfaces, INFORMS, vol. 32(2), pages 63-73, April.
    6. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    7. William S. Lovejoy & Ying Li, 2002. "Hospital Operating Room Capacity Expansion," Management Science, INFORMS, vol. 48(11), pages 1369-1387, November.
    8. Guinet, Alain & Chaabane, Sondes, 2003. "Operating theatre planning," International Journal of Production Economics, Elsevier, vol. 85(1), pages 69-81, July.
    9. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, 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. H. Fei & C. Chu & N. Meskens, 2009. "Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria," Annals of Operations Research, Springer, vol. 166(1), pages 91-108, February.
    2. Pereira Lopes, Manuel J. & de Carvalho, J.M. Valerio, 2007. "A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1508-1527, February.
    3. Zhi‐Long Chen & Warren B. Powell, 2003. "Exact algorithms for scheduling multiple families of jobs on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 823-840, October.
    4. 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.
    5. 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.
    6. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, August.
    8. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.
    9. 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.
    10. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    11. Kerem Bülbül & Philip Kaminsky & Candace Yano, 2004. "Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 407-445, April.
    12. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    13. Wang, Ting & Baldacci, Roberto & Lim, Andrew & Hu, Qian, 2018. "A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine," European Journal of Operational Research, Elsevier, vol. 271(3), pages 826-838.
    14. repec:ipg:wpaper:2013-014 is not listed on IDEAS
    15. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    16. Pablo Santibáñez & Mehmet Begen & Derek Atkins, 2007. "Surgical block scheduling in a system of hospitals: an application to resource and wait list management in a British Columbia health authority," Health Care Management Science, Springer, vol. 10(3), pages 269-282, September.
    17. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.
    18. repec:ipg:wpaper:14 is not listed on IDEAS
    19. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    20. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.
    21. Fırat, M. & Briskorn, D. & Laugier, A., 2016. "A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills," European Journal of Operational Research, Elsevier, vol. 251(2), pages 676-685.
    22. Bani, Abderrahman & El Hallaoui, Issmail & Corréa, Ayoub Insa & Tahir, Adil, 2023. "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints," European Journal of Operational Research, Elsevier, vol. 311(1), pages 154-172.

    More about this item

    Statistics

    Access and download statistics

    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:proeco:v:112:y:2008:i:1:p:96-108. 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/ijpe .

    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.