Q-learning Based Meta-Heuristics for Scheduling Bi-Objective Surgery Problems with Setup Time

Since the increasing demand for surgeries in hospitals, the surgery scheduling problems have attracted extensive attention. This study focuses on solving a surgery scheduling problem with setup time. First, a mathematical model is created to minimize the maximum completion time (makespan) of all surgeries and patient waiting time, simultaneously. The time by the fatigue effect is included in the surgery time, which is caused by doctors’ long working time. Second, four mate-heuristics are optimized to address the relevant problems. Three novel strategies are designed to improve the quality of the initial solutions. To improve the convergence of the algorithms, seven local search operators are proposed based on the characteristics of the surgery scheduling problems. Third, Q-learning is used to dynamically choose the optimal local search operator for the current state in each iteration. Finally, by comparing the experimental results of 30 instances, the Q-learning based local search strategy’s effectiveness is verified. Among all the compared algorithms, the improved artificial bee colony (ABC) with Q-learning based local search has the best competitiveness.