Personnel rostering : models and algorithms for scheduling, rescheduling and ensuring robustness

Abstract

Existing academic literature contains a significant number of publications which address personnel rostering problems. Providing a variety of combinatorial optimization techniques such as metaheuristics, integer linear programming and hybrid algorithms developed to approach such problems. Despite this progress in recent decades, a considerable number of institutions continue to prepare and organize their rosters manually. There are many advantages in automating the generation of rosters using these techniques. These include (i) cost-saving: reduction of both the overtime and time needed to prepare and organize rosters, thereby enabling planners to work on other tasks, (ii) fairness: decisions follow rules based on some predefined parameters, improving employees satisfaction concerning their working schedule with a better balance of unpopular shifts, (iii) possibility of rerostering: disruptions are very hard for humans to solve due to time pressure and the constraints incurred by both the initial scheduling and rescheduling problem. The present thesis addresses four primary shortcomings in academic literature by providing: (i) an integer programming model based on a real-world scenario and a matheuristic to generate results in short computation times to replace manual rostering, (ii) an effective integer programming model for cyclic rostering considering both academic and realworld scenarios which generates state-of-the-art results, (iii) new rerostering strategies for repairing disruptions in complex multi-skilled employee scenarios, and (iv) a metric for quantifying the robustness of rosters. In addition to these contributions, this thesis also focuses on additional issues which should be considered by researches in the future development of solving methods to maximize the chances of their application in practice.

literatura acadêmica possui um número significativo de publicações que abordam problemas de escala de pessoal. Além disso, uma variedade de técnicas de otimização combinatória, como metaheurísticas, programação linear inteira e algoritmos híbridos foram desenvolvidas para abordar tais problemas. Apesar deste progresso nas últimas décadas, um número considerável de instituições continua preparando e organizando suas escalas manualmente. Existem diversas vantagens em automatizar a geração de escalas usando essas técnicas. Isso inclui (i) redução de custos: diminuição tanto de horas-extras quanto do tempo necessário para preparar e organizar as escalas, permitindo que os escalonadores trabalhem em outras tarefas, (ii) justiça: as decisões seguem regras baseadas em alguns parâmetros pré-definidos, melhorando a satisfação dos funcionários em relação ao seu horário de trabalho, com um melhor equilíbrio entre os turnos impopulares, (iii) reescalonamento: as infactibilidades das escalas são muito difíceis para os humanos resolverem devido à pressão do tempo e às restrições incorridas tanto pelo problema de escalonamento inicial quanto pelo de reescalonamento. Esta tese aborda quatro ausências primárias na literatura acadêmica, fornecendo: (i) um modelo de programação inteira baseado em um cenário do mundo real e uma matheurística para gerar resultados em tempos computacionais curtos para substituir o escalonamento manual, (ii) um modelo de programação inteira eficaz para escalonamento cíclico, considerando cenários acadêmicos e do mundo real que geram resultados estado da arte, (iii) novas estratégias de reescalonamento para reparar infactibilidade em escalas considerando cenários complexos de funcionários multi-qualificados, (iv) uma métrica para quantificar a robustez das escalas. Além dessas contribuições, esta tese também foca em questões adicionais que devem ser consideradas no futuro desenvolvimento de métodos de solução para maximizar as chances de sua aplicação na prática.