2023/02/09 by Martin Gutjahr, Gutjahr, Martin, Sophie N. Parragh +3
Decision Sciences · Engineering · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Scheduling and Optimization Algorithms #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2302.04494
openalex publication_date 2023/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Motivated by a real-world application, we model and solve a complex staff scheduling problem. Tasks are to be assigned to workers for supervision. Multiple tasks can be covered in parallel by a single worker, with worker shifts being flexible within availabilities. Each worker has a different skill set, enabling them to cover different tasks. Tasks require assignment according to priority and skill requirements. The objective is to maximize the number of assigned tasks weighted by their priorities, while minimizing assignment penalties. We develop an adaptive large neighborhood search (ALNS) algorithm, relying on tailored destroy and repair operators. It is tested on benchmark instances derived from real-world data and compared to optimal results obtained by means of a commercial MIP-solver. Furthermore, we analyze the impact of considering three additional alternative objective functions. When applied to large-scale company data, the developed ALNS outperforms the previously applied solution approach.