A Large Neighborhood Search Algorithm for Employee Scheduling with Parallel Task Assignments
Sprache des Vortragstitels:
Sprache des Tagungstitel:
This paper considers a real world scheduling problem in which the assignment of tasks with fixed starting times to a set of employees is regarded. Each employee may perform multiple tasks in parallel, depending on the employee's skill level. In addition, planning considers restrictions regarding shift lengths, employee availabilities and complex break scheduling. Legal requirements for breaks and rests have to be taken into account, as well as break splitting possibilities. Furthermore, the problem includes mandatory tasks and consecutivity relations. The aim is to maximize the number of assigned tasks weighted by their priorities, to minimize penalties for the assignment of tasks to underskilled workers, the assignment of different types of tasks in parallel and to maximize the amount of consecutive tasks processed by the same employee.
We model the program in terms of a mixed integer program and we propose a large neighborhood search algorithm with tailored destroy and repair operators. Destroy operators are constructed to take advantage of the layout of an employee scheduling problem. Repair operators sort possible employee task assignments based on varying opportunity cost considerations. Benchmark instances used to test the algorithm are derived from real world data including over 10000 tasks, over 100 employees and time frames of up to one week.