Task selection with complex personnel restrictions in a timetabling environment

Description

The paper considers a complex real-world scheduling problem proposed by a company, in which tasks are to be picked and assigned to a set of differently skilled employees. Employees are able to perform multiple tasks in parallel. All tasks belong to specific task families. Assignments are limited regarding the overlap of tasks of different families. Furthermore, there can be precedence relations between tasks. Some tasks are classified as mandatory and have to be assigned. Each employee requires the construction of shifts inside given availability periods. In addition, legal break and rest requirements as well as possible break splitting with preparation time have to be considered. We maximize the weighted sum of the number of assigned tasks while minimizing penalties. Each task is weighted by its priority. Assignments of tasks to underskilled employees incur a penalty. A large neighbourhood search algorithm has been developed to tackle the described problem and tailored to company needs. The algorithm includes repair and destroy operators that consider opportunity cost. It has since been used in practice. For a more general variant of the problem, we propose a mixed integer programming formulation that is solved using CPLEX. All approaches are tested and compared on a set of test instances derived from real world data. Alternative objectives derived from company goals are considered and tested using the proposed LNS implementation.

Period	24 Aug 2021
Event title	IFORS 2021
Event type	Conference
Location	AustriaShow on map