An efficient computational method for large scale surgery scheduling problems with chance constraints

Mahdi Noorizadegan, Abbas Seifi

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

We propose an efficient solution method based on a decomposition of set-partitioning formulation of an integrated surgery planning and scheduling problem with chance constraints. The studied problem is characterized by a set of identical operating rooms (ORs), a set of surgeries with uncertain durations, a set of surgeons, and surgery dependent turnover times. The decision variables include the number of ORs to open, assignments of surgeries and surgeons to ORs in admissible periods, and the sequence of surgeries to be performed in a period. The objective is to minimize the cost of opening ORs and the penalties associated with turnover times.In the proposed formulation, the column generation subproblem is decomposed over ORs and time periods. The structure of the subproblem is further exploited and transformed to a shortest path problem. A search algorithm has been devised to efficiently solve the resulting subproblem, subject to some optimality and feasibility conditions. The proposed computational method outperforms the standard chance constrained model and reduces the solution time significantly. Furthermore, extensive simulation experiments have been carried out to compare the performance of three variants of the underlying formulations and evaluate the sensitivity of the decisions to the probability of exceeding a session length.
Original languageEnglish
Pages (from-to)535-561
Number of pages27
JournalComputational Optimization and Applications
Volume69
Early online date4 Oct 2017
DOIs
Publication statusPublished - 2018
Externally publishedYes

Keywords

  • Integer programming
  • Integer chance constrained programming
  • Set-partitioning formulation
  • Surgery planning and scheduling

Fingerprint

Dive into the research topics of 'An efficient computational method for large scale surgery scheduling problems with chance constraints'. Together they form a unique fingerprint.

Cite this