Generic and Efficient Personnel Scheduling Approaches Based on State-Expanded Network Formulations

• Applicant: Professor Dr. Michael Römer
• Subject Area: Accounting and Finance
• Term: from 2018 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 398911053

In many industries, particularly in the service sector, employees incur a major part of the direct costs and heavily impact the quality of the products and services delivered by an organization. While making effective use of the workforce is thus a critical success factor for many organizations, constructing efficient personnel schedules is a very complex problem: The schedules need to comply with a multitude of often intricate legality rules governing, for example, the number of allowed work hours per day, the placement of breaks and rest periods, and the allowed patterns of different shift types in a work week. Moreover, the rules and objectives involve the consideration of employee preferences such as requests for days of and fairness issues. Given this complexity, even state-of-the-art approaches are often unable to solve industrial-scale personnel scheduling problems to (near-)optimality. In addition, many approaches involve complex and difficult-to-implement solution approaches such as branch-and-price in which rule handling is deeply embedded in the solution algorithm making it hard to adapt a single implementation to other cases. Furthermore, very complex rules and cost structures cannot easily be expressed using certain modeling and solution approaches: For example, pattern rules governing the legality of activity sequences are typically difficult to model in classical mixed-integer linear programming formulations.A promising new approach to address the described challenges is to formulate personnel scheduling problems as mixed-integer linear programming models on the basis of flows in state-expanded networks. An important advantage of this approach is that the resulting models can be solved by standard software. The central research hypothesis addressed in the project is that this approach has the potential to form the basis of a novel efficient generic approach applicable to a broad range of personnel scheduling problems and yielding better results than other state-of-the art approaches. In order to evaluate this hypothesis, the specific objectives of this project are (i) to investigate and develop generic approaches for expressing various personnel scheduling problem variants and for handling complex scheduling rules in models based on state-expanded networks, (ii) to improve the state-expanded network formulations by exploiting hierarchical structure of personnel scheduling problems and reducing network size, (iii) to develop generic and efficient heuristic approaches exploiting the model structure allowing to handle large-scale instances and (iv) to explore decomposition-based solution approaches exploiting the structure of the state-expanded network formulations.

• DFG Programme: Research Fellowships
• International Connection: Canada
• Host: Professor Andre Cire, Ph.D.