Scheduling operating theatres: Mixed integer programming vs. constraint programming

作者：Wang Tao^*; Meskens Nadine; Duvivier David

来源：European Journal of Operational Research, 2015, 247(2): 401-413.

DOI：10.1016/j.ejor.2015.06.008

• Combinatorial optimization
• Constraints satisfaction
• Linear programming
• OR in health services
• Models comparison

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.

• 出版日期2015-12-1