A two-phase optimization model combining Markov decision process and stochastic programming for advance surgery scheduling

Jian Zhang (Corresponding author), Mahjoub Dridi, Abdellah El Moudni

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
108 Downloads (Pure)


This paper addresses the advance scheduling of elective surgeries in an operating theater composed of operating rooms and a downstream surgical intensive care unit (SICU). The arrivals of new patients in each week, the duration of each surgery, and the length-of-stay of each patient in the SICU are subject to uncertainty. At the end of each week, the surgery planner determines the surgical blocks to open in the next week and assigns a subset of the surgeries on the waiting list to open surgical blocks. The objective is to minimize the patient-related costs incurred by performing and postponing surgeries as well as the hospital-related costs caused by utilization of surgical resources. Considering that the pure mathematical programming models commonly used in the literature mostly focus on the short-term optimization of surgery schedules, we propose a novel two-phase optimization model that combines Markov decision process (MDP) and stochastic programming to improve the long-term performance of surgery schedules. Moreover, in order to solve realistically sized problems efficiently, we develop a novel column-generation-based heuristic (CGBH) algorithm, then combine it with the sample average approximation (SAA) approach. The experimental results indicate that the SAA-CGBH algorithm is considerably more efficient than the conventional SAA approach, and that the optimal surgery schedules of the two-phase optimization model significantly outperform those of a pure stochastic programming model.
Original languageEnglish
Article number107548
Number of pages22
JournalComputers & Industrial Engineering
Publication statusPublished - 1 Oct 2021


The authors gratefully acknowledge the financial support granted by the China Scholarship Council (CSC, Grant No. 201604490106).

FundersFunder number
China Scholarship Council201604490106


    • Advance surgery scheduling
    • Column-generation-based heuristic
    • Markov decision process
    • Sample average approximation
    • Stochastic programming
    • Two-phase optimization model


    Dive into the research topics of 'A two-phase optimization model combining Markov decision process and stochastic programming for advance surgery scheduling'. Together they form a unique fingerprint.

    Cite this