A neutrality-based iterated local search for shift scheduling optimization and interactive reoptimization

Interactive reoptimization is an approach for progressively adjusting a candidate solution in order to introduce aspects of a problem that have not been entirely captured by the optimization model. In this paper, a reoptimization problem is investigated in the context of staff scheduling. The proposed reoptimization problem is derived from a shift scheduling problem. For solving the initial optimization problem and its reoptimization extension a neutrality-based iterated local search method is proposed. The conducted computational experiments first compare the proposed method against results from the literature on the initial shift scheduling problem. For this first part of the computational experiments, the datasets of the first International Nurse Rostering Competition (INRC2010) are used. The results indicate that the neutrality-based local search method provides on average significantly better solutions than the compared methods on small instances of the benchmark and has similar performance to the best known method for larger instances. In a second part of the experiments, the proposed method is evaluated on the reoptimization problem variant. The results on this second analysis reveal the practical difficulty of adjusting a candidate solution and the need of a global optimization approach, such as the proposed one, for the reoptimization problem. The results also support the fact that the proposed neutrality-based iterated local search metaheuristic is efficient for reoptimizing solutions in a very short time.