Til hovedinnhold

Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling

Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling

Kategori
Tidsskriftspublikasjon
Sammendrag
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.
Oppdragsgiver
  • Norges forskningsråd / 219335
Språk
Engelsk
Forfatter(e)
Institusjon(er)
  • SINTEF Digital / Mathematics and Cybernetics
  • Universitetet i Oslo
År
2016
Publisert i
European Journal of Operational Research
ISSN
0377-2217
Årgang
255
Hefte nr.
3
Side(r)
719 - 728