Novos algoritmos heurísticos para o problema de escalonamento de enfermeiros

Abstract

Whereas a set of activities that should be taken in each day of work, the Personnel Scheduling Problem consists in elaborating sequences of tasks over a planning period, optimizing an objective function and respecting the constraints involved. Each sequence is a journey of work that must be assigned to a person. This is a Combinatorial Optimization problem classified as NP-hard. This problem has encouraged the creation of several models and algorithms, exacts and heuristics, being the majority of them based on mathematical programming. Among the Personnel Scheduling Problems, the Nurse Scheduling Problem stands out. It consists in generating work schedules for nurses considering the shift preference, reported through the association of a cost for each shift in each day of work. The constraints involve rules imposed by labor laws and desirable characteristics on a schedule. Two new heuristic algorithms based, respectively, on the successive resolutions of the Assignment Problem and of the Bottleneck Assignment Problem are proposed in this work. The first method solves the problem as a Multilevel Assignment Problem and works in two phases. In the first phase the algorithm constructs an initial solution. In the second phase two improvement procedures are applied. The second method uses the Bottleneck Assignment Problem model and, similarly, has the constructive phase and the improvement phase. Computational tests are carried out using instances from a standard benchmark dataset. In general, the first proposed method results were better when compared to results from papers of the literature that use the same dataset. Otherwise, the second method provided a more balanced treatment of preferences. Furthermore, the computational experiments show that the proposed algorithms are robust and efficient.