A relax-and-fix and fix-and-optimize algorithm for physician scheduling in emergency rooms

Balancing physician workload in emergency departments is a significant problem in practice due to its major impacts in a hospital setting, from severe cost implications to its effect on vital patients’ care. From a theoretical perspective, the problem involves simultaneously addressing several inherent and often conflicting challenges, such as ensuring a fair distribution of workload among physicians, respecting the availability of staff and minimizing costs in a rather expensive sector. In this paper, we propose a matheuristic to address this challenging problem. Based on a mixed-integer programming model from the literature, we first incorporate the modelling of least absolute deviation in a set of workload constraints. Our approach integrates relax-and-fix and fix-and-optimize heuristics that are effectively used in other domains such as production planning. We present detailed computational results that compare our approach with standard mixed-integer programming model using benchmark instances from the literature. Our approach has resulted in 1) a higher degree of satisfaction with demand requirements, 2) a more accurate estimation of working hours and a fairer distribution among physicians, and 3) shorter computational times to find feasible solutions.