A bilevel approach to integrated surgeon scheduling and surgery planning solved via branch-and-price
研究手术室部门中外科医生组长与个体医生之间的双层排班问题，提出分支定价算法求解纳什均衡解，确保组长目标最优且个体医生无法改进自身目标。
In this paper, we study a multi-agent scheduling problem for organising the operations within the operating room department. The head of the surgeon group and individual surgeons are together responsible for the surgeon schedule and surgical case planning. The surgeon head allocates time blocks to individual surgeons, whereas individual surgeons determine the planning of surgical cases independently, which might degrade the schedule quality envisaged by the surgeon head. The bilevel optimisation under study seeks an optimal Nash equilibrium solution – a surgeon schedule and surgical case plan that optimise the objectives of the surgeon head, while ensuring that no individual surgeon can improve their own objective within the allocated time blocks. We propose a dedicated branch-and-price that adds lazy constraints to the formulation of surgeon-specific pricing problems to ensure an optimal bilevel feasible solution is retrieved. In this way, the surgeon head respects the objective requirements of the individual surgeons and the solution space can be searched efficiently. In the computational experiments, we validate the performance of the proposed algorithm and its dedicated components and provide insights into the benefits of attaining an equilibrium solution under different scenarios by calculating the price of stability and the price of decentralisation. • Integrated Surgeon Scheduling and Surgery Planning. • Bilevel Approach with Surgeon Head as leader and Surgeons as followers. • Efficient Branch-and-Price relying on Bilevel Feasible Surgeon Schedules. • Generation of different types of Lazy Constraints. • Price of Stability/Decentralisation for different Objective-Function Scenarios.