Abstract: Considering the surgical system that shares the bed resource for intake and recovery, this paper focuses.on re-entrant surgery scheduling problems with minimising the average completion time of recovery for all patients. To deal with uncertain service times, the triangular fuzzy number is employed to describe the duration of intake, surgery and recovery. Considering the NP-hardness of the studied problem, an adaptive hybrid meta-heuristic (HGA-AVNS), hybridising genetic algorithm (GA) and variable neighborhood search (VNS),are designed to generate surgery schedules. To improve the local search ability, HGA-AVNS applies several block-based neigh bourhood structures (NS) and determines their search order using a roulette-based NS changing scheme. Computation results on randomly generated test instances indicate the superiority of HGA-AVNS.

Key words: surgery scheduling, uncertain service time, re-entrant patient flow, genetic algorithm, variable neighborhood search

摘要： 对于术前准备和术后恢复阶段共用床位资源的手术系统,本文建立了可重入手术调度问题的数学模型,以降低病人术后恢复的平均完成时间。该模型考虑了病人手术流程中服务时间的不确定性,采用三角模糊数对术前准备、手术和术后恢复的服务时间进行描述。结合该调度问题的可重入特点,本文提出了一种基于遗传算法（Ge-neticAlgorithm,GA）和变邻域搜索(V ariable Neighborhood Search, GA)的混合优化算法（HGA-AVNS）。HGA-AVNS通过块邻域和基于轮盘赌的邻域变换策略来增强算法的局部搜索性能。数值实验的最终结果表明了所提算法的优越性。

关键词: 手术调度, 服务时间变动, 可重入, 遗传算法, 变邻域搜索