Scheduling operating theatres: Mixed integer programming vs. constraint programming

Tao Wang

doi:10.1016/j.ejor.2015.06.008

2015-12-01

PRE

王涛 (Tao Wang) *

Nadine Meskens

David Duvivier

DOI：10.1016/j.ejor.2015.06.008

原文链接

原文求助

摘要

En 中文

The daily scheduling of an operating theatre is a highly constrained problem. In addition to standard scheduling constraints, many additional constraints on human and material resources encountered in real life should be taken into account. These constraints concern the priority of operations, the affinities between surgical team members, renewable and non-renewable resources, various sizes in the block scheduling strategy, and the surgical team's preferences/availabilities. We developed two models in our research work, using mixed-integer and constraint programming respectively. These were compared using a real-life case in order to determine which one coped better with a highly constrained problem. A cross-comparison of the experimental results shows that the mixed-integer programming model provides a better performance using the weighted sum objective function than using the makespan minimization objective function. Conversely, the constraint programming model is better suited to the makespan minimization objective function than to the weighted sum objective function. The originality of this research lies on three levels: (1) two models are presented in detail and compared using real data; (2) constraint programming is used to schedule the operating theatre; (3) some new constraints are taken into account, such as the affinities between team members in the composition of surgical teams, and the priorities of patients such as diabetics. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

Keyword:

Combinatorial optimization

Constraints satisfaction

Linear programming

OR in health services

Models comparison