A column-generation-based heuristic algorithm for solving operating theater planning problem under stochastic demand and surgery cancellation risk

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

32 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)28-36
Journal / PublicationInternational Journal of Production Economics
Volume158
Online published23 Jul 2014
Publication statusPublished - Dec 2014

Abstract

This paper investigated an operating theater allocation problem with uncertain surgery duration and emergency demand. Under the consideration of surgery cancellation, a stochastic model was developed to minimize the total expected operating cost. A trade-off was sought between the total cost of opening operating rooms and the total overtime due to the overbooking of an operating theater. The sample average approximation method was used to transform the stochastic model into a deterministic one. A column-generation-based heuristic (CGBH) algorithm was developed to solve the integer programming problem. The performance of the CGBH algorithm was tested by solving randomly generated instances with given distributions. Multiple heuristic rules for branching were developed and compared from the perspectives of solution quality and efficiency. Numerical results indicated that high surgery cancellation risk helps to reduce the operating costs of hospitals and improve the OR efficiency but results in patients' dissatisfaction, and vice versa. This provides management insights for hospital manager to balance the operating costs and patients' satisfaction. The CGBH algorithm performed as well as the CPLEX in the solution quality for small-scale problems. This algorithm can obtain solutions within a 5% gap of the lower bound obtained by the linear problem for large-scale problems that cannot be solved by CPLEX.

Research Area(s)

  • Column generation, Emergency, Operating theater planning, Stochastic model, Surgery cancellation

Citation Format(s)

A column-generation-based heuristic algorithm for solving operating theater planning problem under stochastic demand and surgery cancellation risk. / Wang, Yu; Tang, Jiafu; Fung, Richard Y. K.

In: International Journal of Production Economics, Vol. 158, 12.2014, p. 28-36.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal