Operating theatres and surgeons are among the most expensive resources in any hospital, so it is vital that they are used efficiently. Many European hospitals implement block scheduling, where each surgeon is assigned...
详细信息
Operating theatres and surgeons are among the most expensive resources in any hospital, so it is vital that they are used efficiently. Many European hospitals implement block scheduling, where each surgeon is assigned blocks of time in specific operating theatres on a cyclic basis. This paper proposes a model that assists hospitals in creating new master theatre timetables, which take account of reducing the maximum number of beds required, surgeons' availability, surgeons' preferences, variations in types of theatre and their suitability for different types of surgery, limited equipment availability, and the ability to vary the length of the cycle over which the timetable is repeated. The weightings given to each of these factors can be altered, thereby allowing exploration of a variety of possible timetables. Novel features of the model include consideration of surgeons' preferences for slots, smoothing of bed usage during the generation of master theatre timetables and the use of operating theatres with the potential for the same theatre to be belong to multiple non-nested types. These new features are considered in combination with a range of other factors that have been considered in previous studies on the development of master theatre timetables. (C) 2017 Elsevier B.V. All rights reserved.
In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bou...
详细信息
In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound-based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes.
暂无评论