A multistage approach for an employee timetabling problem with a high diversity of shifts as a solution for a strongly varying workforce demand

This work deals with the employee rostering problem at the airport. Such problems, related to the time varying demand of the transport services, use many (e.g., about a hundred) diverse shifts to cover the workforce demand during the day. Together with the strict constraints, given by the collective agreement, the problem becomes difficult to solve. Algorithms commonly used for solving the usual employee rostering problems produce poor quality rosters, which are unusable in practice. This paper suggests a three stage approach allowing one to solve the employee rostering problems where a huge set of different shifts is used to satisfy the coverage requirements. The solution is based on the problem transformation to a simpler problem, thereupon, an evolutionary algorithm is used to determine a rough position of the shifts in the roster. Afterwards, the maximal weighted matching in the bipartite graph is applied as the inverse transformation of the problem and the final roster is obtained by the optimization based on a Tabu Search algorithm. This multistage approach is compared to other approaches. Furthermore, an evaluation methodology was proposed in order to make a complex and fair comparison. Its objective is to verify the contribution of the particular stages used in the different approaches applied on the different personnel scheduling problems.