Variable neighborhood search for a planning problem with resource constraints in a health simulation center

摘要

In this paper we propose the Variable Neighborhood Search (VNS) algorithm SimULS to solve a planning problem in the Health Simulation Center SimUSanté. This center offers numerous training sessions based on simulation learning for health actors, be they professionals or students. The data and constraints of the SimUSanté problem, close to the academic Curriculum-Based Courses Timetabling (CB-CTT) Problem, are presented in detail using a 0-1 linear program modelization. A dedicated greedy algorithm SimUG is used to generate a relevant initial solution in the VNS algorithm. SimULS combines different neighborhood functions stemmed from operators saturator, intra, extra and extra +. A diversification function is applied when the search becomes trapped by a local optimum. First, SimULS was compared to the open source KHE solver by relaxing the precedence constraints. Next, SimULS was tested on all the generated SimUSanté instances. Both experiments show that the strength of SimULS is to schedule all the activities, even for the largest instances, without violating any hard constraints. In addition, the solutions given by SimULS are close to the optimum with a gap less than 7.33%.