Employee scheduling with parallel task assignments and complex break time requirements
Sprache des Vortragstitels:
Sprache des Tagungstitel:
The real-world scheduling problem considered in this paper concerns the assignment of different types of tasks with fixed starting times to a set of employees, whereas multiple tasks may be carried out in parallel, depending on the type of task and the skills of the employee. It also involves shift planning with minimum and maximum shift length constraints, employee dependent availability periods, and complex break scheduling. In addition to legal requirements for total break length and rest time between shifts, problem specific constraints like splitting breaks and preparation time have to be considered. Further constraints include mandatory tasks, consecutive tasks, and limitations for concurrent tasks. The aim is to maximize a weighted sum of the number of assigned tasks weighted by their priorities and negative penalties for assignments to underskilled employees.
We propose a large neighborhood search algorithm to solve this problem which relies on a set of tailored destroy and repair operators. Repair operators rank possible insertions of matches into availabilities based on different opportunity cost considerations. Benchmark instances derived from real-world data with over 10000 tasks, over 100 employees, and up to 7 days are solved with the proposed method.