A dedicated branch-price-and-cut algorithm for advance patient planning and surgeon scheduling

Babak Akbarzadeh and Broos Maenhout

European Journal of Operational Research, 2025, vol. 322, issue 2, 448-466

Abstract: In this paper, we study the patient planning and surgeon scheduling in the operating room theatre. The problem considers the simultaneous planning of patients and the assignment of time blocks to surgeons so that they can perform the surgery of their patients. The timing and length of the allotted time blocks depend on the patient characteristics on the surgeons’ waiting lists. Solving this problem in an exact manner is challenging due to the large number of rooms, surgeons, and patients involved. To overcome this challenge, we propose an efficient branch-price-and-cut algorithm to find an optimal solution in an acceptable time span. For that purpose, we include different dedicated mechanisms to accelerate the solution-finding process. In this regard, the branch-price-and-cut tree is set up using an intelligent branching scheme, the nodes are searched in order of the lowest number of fractional variables, and improved bounds are computed to prune nodes earlier. To tighten the convex hull of the linear programming relaxation in each node, the algorithm relies on a row generation mechanism for adding valid inequalities. We conducted various computational experiments to demonstrate the performance of our algorithm and validate for each component the contribution of the implemented optimisation principles. Additionally, we show the superior performance of the proposed algorithm to alternative optimisation procedures.

Keywords: OR in health services; Operating room scheduling; Surgeon scheduling; Patient planning; Branch-price-and-cut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724008452
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:322:y:2025:i:2:p:448-466

DOI: 10.1016/j.ejor.2024.10.042

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().