A GRASP-based algorithm for solving the emergency room physician scheduling problem
Fecha
2021Versión
Acceso abierto / Sarbide irekia
Tipo
Artículo / Artikulua
Versión
Versión publicada / Argitaratu den bertsioa
Identificador del proyecto
AEI//MTM2016-77015-R
Impacto
|
10.1016/j.asoc.2021.107151
Resumen
This paper addresses a physician scheduling problem in an Emergency Room (ER) requiring a long-term work calendar to allocate work days and types of shift among all the doctors. The mathematical model is created without simplifications, using the real calendar, including holidays. This precludes the possibility of cyclic-type solutions, and involves numerous and varied constraints (demand, worklo ...
[++]
This paper addresses a physician scheduling problem in an Emergency Room (ER) requiring a long-term work calendar to allocate work days and types of shift among all the doctors. The mathematical model is created without simplifications, using the real calendar, including holidays. This precludes the possibility of cyclic-type solutions, and involves numerous and varied constraints (demand, workload, ergonomics, fairness, etc.). An effective solution to this very difficult practical problem cannot be obtained, for large instances, with exact solution methods. We formulate a mathematical representation of a real-world ER physician scheduling problem featuring a hybrid algorithm combining continuous linear programming with a greedy randomized adaptive search procedure (GRASP). Linear programming is used to model a general physician-demand covering problem, where the solution is used to guide the construction phase of the GRASP, to obtain initial full schedules for subsequent improvement by iterative application of Variable Neighborhood Descent Search (VNDS) and Network Flow Optimization (NFO). A computational study shows the superiority of our approach over the Integer Linear Programming method in a set of instances of varying size and difficulty inspired by a real setting. The methodology is embedded in a software tool for generating one-year-ahead physician schedules for a local ER. These solutions, which are now in use, outperform the manually-created schedules used previously. © 2021 Elsevier B.V. [--]
Materias
OR in health services,
GRASP,
Network flow optimization,
Physician scheduling,
Emergency room
Editor
Elsevier
Publicado en
Applied Soft Computing 103 (2021) 107151
Departamento
Universidad Pública de Navarra/Nafarroako Unibertsitate Publikoa. Institute of Smart Cities - ISC
Versión del editor
Entidades Financiadoras
This research has been supported by grant MTM2016-77015-R (AEI, Spain, FEDER UE)