Column-generation-based heuristic approaches to stochastic surgery scheduling with downstream capacity constraints

Jian Zhang, Mahjoub Dridi and Abdellah El Moudni

International Journal of Production Economics, 2020, vol. 229, issue C

Abstract: This paper addresses an advance surgery scheduling problem in an operating theater composed of multiple operating rooms (ORs) and a downstream surgical intensive care unit (SICU). Uncertainties in surgery durations and postoperative length-of-stays are taken into consideration. The decisions are made on a weekly basis and consist of three parts: determining the surgical blocks to open, selecting the surgeries to be performed from a waiting list, and assigning the selected surgeries to available surgical blocks. The objective is to minimize the patient-related cost as well as the hospital-related cost while respecting the SICU capacity constraints. We propose a two-stage stochastic programming model with recourse to address the studied problem. Sample average approximation is employed to translate the stochastic programming model into a deterministic integer linear programming (DILP) model, which is then solved by column-generation-based heuristic (CGBH) approaches. The CGBH approaches developed in this paper reformulate the DILP model in a column-oriented way and adopt multiple column-generation strategies and heuristic rules to improve computational efficiency. The experimental results illustrate that the proposed CGBH approaches require significantly less computation time than the conventional algorithm, and that the gaps between the resulting near-optimal solutions and the exact ones are below 1%. Moreover, numerical experiments carried out with large test problems validate the capability of the CGBH approaches in solving realistically sized cases.

Keywords: Surgery scheduling; Operating theater planning; Stochastic programming; Sample average approximation; Column-generation-based heuristic (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527320301468
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:proeco:v:229:y:2020:i:c:s0925527320301468

DOI: 10.1016/j.ijpe.2020.107764

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().