A rotation-based branch-and-price approach for the nurse scheduling problemReportar como inadecuado

A rotation-based branch-and-price approach for the nurse scheduling problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 CIRRELT - Centre Interuniversitaire de Recherche sur les Réseaux d-Entreprise, la Logistique et le Transport 2 Polytechnique Montréal 3 INSA Rennes - Institut National des Sciences Appliquées - Rennes 4 IRMAR - Institut de Recherche Mathématique de Rennes 5 GERAD - Groupe d-Etudes et de Recherche en Analyse des Décisions

Abstract : In this paper, we describe an algorithm for the personalized nurse scheduling problem. We focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition. One specificity of this version of the problem is that most constraints are soft, meaning that they can be violated at the price of a penalty. The feasible space is thus much larger, which involves much more difficulty to find the optimal solution. We model the problem as a an integer program IP that we solve using a branch-and-price procedure. This model is, to the best of our knowledge, comparable to no other from the literature, since each column of the IP corresponds to a rotation, i.e., a sequence of consecutive worked days for a nurse, and not to a complete individual roster. We tackle instances involving up to 120 nurses and 4 shifts over an 8-weeks horizon by embedding the branch-and-price in a large-neighborhood-search framework. Initial solutions of the large-neighborhood search are found by a rolling-horizon algorithm, well-suited to the rotation model.

Keywords : nurse scheduling problem column-generation decomposition branch-and-price large-neighborhood search rolling horizon

Autor: Antoine Legrain - Jérémy Omer - Samuel Rosat -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados