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 SimUSante. This center offers numerous training sessions based on simulation learning for health actors, be they professionals or students. The data and constraints of the SimUSante 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 SimUSante 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%.

Automated summary

The paper introduces the Variable Neighborhood Search (VNS) algorithm SimULS to solve a planning problem in the Health Simulation Center SimUSante. The algorithm combines different neighborhood functions and uses a diversification function when trapped in a local optimum. Experimental results show that SimULS is able to schedule all activities without violating constraints, providing solutions close to the optimum.