Artifical Intelligence in Employee Scheduling

Work schedules influence the lives of each of us. On the one hand an unsuitable timetable can have a tremendous negative impact on one`s health, social life, and motivation at work. On the other hand, organizations in the commercial and public sector must meet their workforce requirements and ensure the quality of their services and operations. Therefore, the task of finding appropriate staff schedules is of great importance for society. However, this is a tremendously complex task due to the huge number of constraints that have to be fulfilled (e.g. labor rules, individual employee preferences, and requirements of companies) and the enormous search space of possible solutions. Such complex problems appear especially in companies where the required number of employees throughout the time periods fluctuates, which operate 24 hours per day, and deal with critical tasks (e.g., air traffic control, personnel working in emergency services, call centers, etc.). Traditionally, the general employee scheduling problems have been solved in separated phases which include several sub-problems, each of which are NP-hard (e.g., shift scheduling, break scheduling, workforce scheduling, etc.). Such an approach reduces the complexity for solving the problem, but requires the use of a human expert. Furthermore, the sub-problems are strongly interleaved between each other, and solutions which are optimal overall can not be guaranteed due to the early decisions made in the sub-problem solutions. One of the main open challenging questions in general employee scheduling is: Can we fully automate the general employee scheduling problem and obtain high quality solutions without the help of human expert? In this project we will tackle exactly this challenge. We aim to make significant progress in solving employee scheduling in general and propose methods that can be used for a broad range of such problems. Our ambitious aims require fundamental research on developing of new intelligent search methods that can deal with such complex tasks. We aim to provide new search methods that use machine learning in search, and exploit structural decomposition techniques in search techniques. A breakthrough in this project will bring a significant contribution in the area of employee scheduling as well as in problem solving and search.

The task of finding appropriate staff schedules is of great importance for society. However, this is a tremendously complex task due to the huge number of constraints that have to be fulfilled (e.g. labor rules, individual employee preferences, and requirements of companies) and the enormous search space of possible solutions. Such complex problems appear especially in companies where the required number of employees throughout the time periods fluctuates, which operate 24 hours per day, and deal with critical tasks (e.g., air traffic control, personnel working in emergency services, call centers, etc.). The main aim of this project was to make significant progress in solving employee scheduling in general and propose methods that can be used for a broad range of such problems. This required fundamental research on developing of new methods that can deal with such complex tasks. In this project we developed state-of-the-art algorithms for employee scheduling problems including shift design, break scheduling, rotating workforce scheduling, nurse rostering, and general employee scheduling problem. The proposed algorithms provide currently the best existing results for several problems in these areas. We developed innovative solution methods based on complete methods (Constraint Programming, Integer Programming, Answer Set Programming, SAT Solving, and SMT-solving), metaheuristics, and hybrid techniques. We provided a general modeling format for employee scheduling and developed a new framework for the general employee scheduling problem that allows the implementation of various heuristic algorithms and their application to a wide range of problems. We investigated the algorithm selection problem for several problems including graph coloring, traveling salesman problem, rotating workforce scheduling, and tree decomposition. We could identify new features that characterise well instances of these problems. We have used these features for automated algorithm selection in these domains and investigated deeply the application of machine learning techniques for algorithm performance prediction. In this project we also considered solving of related problems including high school timetabling, torpedo scheduling, tree decomposition, and sudoku, and could provide state-of-the-art algorithms for these problems. The project gave important contributions in the area of employee scheduling as well as in problem solving and search. The results of this project and new developed algorithms can be used to solve real-world staff scheduling and timetabling problems in industry and public institutions.