Diz 48 en
Advanced Methods and Models for Employee Timetabling Problems
Autor: Bäumelt Zdeněk
This thesis is focused on the design of efficient models and algorithms for employee timetabling problems (ETPs). From our point of view, there are two significant gaps in the current state of the art.
The first one, also important in practice, concerns the ETP with strongly varying workforce demand. Unlike the classical Nurse Rostering Problem (NRP) this problem considers dozens of shift types that can cover the demand more precisely than early, late and night shift type used in NRP. In this work we call this problem the Employee Timetabling Problem with a High Diversity of shifts (ETPHD). It comes as no surprise that the exact methods like Integer Linear Programming are not able to find its solution in reasonable time. Therefore, a transformation of ETPHD based on mapping of shift types to shift kinds was proposed. The transformation allows one to design a multistage approach (MSA). The aim of the first two stages is to find an initial ETPHD solution, where a rough position of assigned shifts is determined. This proved to be substantial for the last stage of MSA, where the solution is consequently improved in terms of its quality. In order to verify the MSA performance, a cross evaluation methodology was proposed. It is based on the comparison of the performance provided by more approaches on more combinatorial problems. Therefore, real life ETPHD instances from an airport ground company and also standard benchmark NRP instances were considered. The experiments confirmed the better or equal performance of our approach in the most of the cases.
The second gap in the literature is an absence of parallel algorithms for ETPs. We focused on the Nurse Rerostering Problem (NRRP) that appears when a disruption in the roster occurs, e.g., when one of the employees becomes sick. For this purpose, the parallel algorithm solving NRRP was proposed in order to shorten needed computational time. This algorithm was designed for a Graphics Processing Unit (GPU) offering a massive parallelization. To the best of our knowledge, this is the first usage of GPU for ETPs. The performance of the GPU parallel algorithm was tested on the real life NRRP benchmark instances and evaluated from two points of view. Firstly, the quality of the results was compared to the known results from the state of the art. Secondly, the speedup achieved by the parallel algorithm related to the sequential one was verified. In average, the parallel algorithm is able to provide the results of the same quality 15 times faster than the sequential one.
- Zdeněk Bäumelt, mailto:firstname.lastname@example.org