Talks and Poster Presentations (with Proceedings-Entry):
L. Kletzander, N. Musliu:
"Solving the General Employee Scheduling Problem";
Talk: PATAT - International Conference on the Practice and Theory of Automated Timetabling,
- 2018-08-31; in: "12th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2018",
n many professions the demand for work requires employees to work in diﬀerent shifts to cover varying requirements including areas like health care, protection services, transportation, manufacturing or call centers. However, there are many constraints that need to be satisﬁed in order to create feasible schedules. The demands can be speciﬁed in various ways, diﬀerent legal requirements need to be respected and employee satisfaction has to be taken into account. Therefore, automated solutions are mandatory to stay competitive. However, even then it is often hard to provide good solutions in reasonable time as many of the problems are NP-hard.
While not each problem will require the whole set of available restrictions, it is cumbersome to develop a new speciﬁcation format and corresponding solver for each problem. Often these can not be well applied to similar problems diﬀering in some requirements. On the other hand it is a challenging task to provide a general formulation and solution methods that can solve large integrated problems, as even several sub-problems on their own are known to be NP-hard.
Therefore a new framework is proposed for the general employee scheduling problem that allows the implementation of various heuristic algorithms and their application to a wide range of problems. This is realized by proposing a uniﬁed handling of constraints and the possibility to implement various moves that can be reused across diﬀerent algorithms. Further, a new search method is developed and implemented in the framework.
In order to show the applicability to a wide range of problems, we take diﬀerent problems from literature that cover diﬀerent types of demand and constraints, translate their instances to our formulation and apply our solver to those instances as well as our own instances with good results.
Rostering, Task Scheduling, Metaheuristics
Project Head Nysret Musliu:
Created from the Publication Database of the Vienna University of Technology.