Abstract
Efficient outpatient scheduling is becoming increasingly important for the overall cost effectiveness and treatment efficiency of a hospital. We consider a class of multi-mode appointment scheduling problems, with variable resource availability and resource setup times. These problems are frequently found in hospital outpatient clinics, and they are typically hard to solve.
We present an exact method based on a recursive logic-based Benders’ decomposition, where each subproblem is formulated as an integer linear program. We show how such a decomposition can be designed to fully exploit the daily structure of these problems, while at the same time addressing the symmetry issues that arise from having many appointments with similar resource and time requirements. Novel valid inequalities are also added to strengthen each master problem.
We demonstrate the efficiency of the overall approach through a case study from a gastroenterology clinic at the University Hospital of Northern Norway, using real life data. The computational results show that the recursive, three-level, decomposition solves the most complex real life test instances to optimality in less than 5 minutes. The method drastically outperforms the corresponding two-level decomposition, which fails to solve all but one of these test instances within the one hour time limit.
We present an exact method based on a recursive logic-based Benders’ decomposition, where each subproblem is formulated as an integer linear program. We show how such a decomposition can be designed to fully exploit the daily structure of these problems, while at the same time addressing the symmetry issues that arise from having many appointments with similar resource and time requirements. Novel valid inequalities are also added to strengthen each master problem.
We demonstrate the efficiency of the overall approach through a case study from a gastroenterology clinic at the University Hospital of Northern Norway, using real life data. The computational results show that the recursive, three-level, decomposition solves the most complex real life test instances to optimality in less than 5 minutes. The method drastically outperforms the corresponding two-level decomposition, which fails to solve all but one of these test instances within the one hour time limit.