基于拉格朗日松弛的手术中心调度算法

Lagrangian relaxation-based scheduling algorithm for operating theatres

为了有效提高手术中心的利用率,降低医院的成本,提高病人满意度,本文提出了基于拉格朗日松弛的手术中心调度算法.首先对问题域进行了描述,以最小化手术中心相关成本和最大化病人满意度为目标,建立数学规划模型.在此基础上,建立可行调度解策略,结合手术中心特有的约束条件,提出基于拉格朗日松弛的手术中心调度方法,并用分枝定界求解子问题.最后,设计不同问题规模的实验,对算法性能进行了评价和对比分析,实验表明,该算法能在可接受的计算时间内得到较好的近优解.

To improve the efficiency of operating theatre effectively, reduce the hospital＇s costs and improve the satisfaction of patients, an operating theatre scheduling method was presented based on a Lagrangian relaxation （LR） algorithm. Firstly, a problem domain was described. Mathematical programming models were also set up with objective functions of minimizing related costs of the operating theatre and maximizing the satisfaction of patients. On the basis of the descriptions mentioned above, a solving policy of generating feasible scheduling solutions was established. Combining with the specific constraints of operating theatre, the LR-based algorithm was put forward to solve scheduling problems, and the sub-problems were solved via a branch and bound algorithm. Finally, computational experiments were performed on different scale of problems. The performance of the proposed algorithm was evaluated and compared with that of other approaches. Results demonstrated that the proposed method can obtain better near-optimal solutions in acceptable computation time.