EURO 2025 Leeds
Abstract Submission

508. A combinatorial Benders decomposition approach for a scheduling problem arising in a sports institution

Invited abstract in session MA-12: Mathematical Programming in Project Scheduling , stream Scheduling and Project Management.

Monday, 8:30-10:00
Room: Clarendon SR 1.02

Authors (first author is the speaker)

1. Javier Marenco
Business School, Universidad Torcuato Di Tella
2. Ivo Koch
BASF
3. Luciana Skakovsky
Departamento de Computación, Universidad de Buenos Aires

Abstract

In this work we consider the following scheduling problem. We are given a set of tasks, a set of employees, and a set of days. Each task has a priority, a length in hours, and a number of needed employees who must be scheduled to perform the task simultaneously. We also have a compatibility matrix between tasks and employees, specifying which employees can perform each task. The problem consists in determining which tasks are to be scheduled and determining a day, a starting time, and a set of employees for each scheduled task in such a way that (a) no employee performs two tasks at the same time, (b) task constraints are obeyed, and (c) the total priority of the scheduled tasks is optimized. We present a computational approach for this problem based on the combinatorial Benders decomposition. We show that this approach is effective, outperforming a commercial integer programming solver over a natural formulation for real instances coming from a sports institution. As part of this decomposition, we consider the problem of explaining the compatibility task-employee matrix in terms of skills. We seek to assign a minimum-sized set of skills to tasks and employees, in such a way that an employee is compatible with a task if and only if the skills set of the employee is included in the skills set of the task. The resulting explanation of the compatibility matrix is used as a means to strengthening the primary subproblem in the combinatorial Benders decomposition described above.

Keywords

Status: accepted

Back to the list of papers