Un algoritmo basado en la descomposición combinatoria de Benders para un problema de programación de tareas

  • Santina Bardengo
  • Javier Marenco
Palabras clave: programación de tareas, programación entera, descomposición de Benders

Resumen

En este trabajo consideramos un problema de programación de tareas para una institución deportiva. Se debe programar un conjunto de tareas a lo largo de varios días, y se tiene un conjunto de empleados que pueden realizar estas tareas. Se supone que todos los empleados realizan el mismo horario de trabajo. Cada tarea tiene su duración y una cantidad requerida de empleados. Si una tarea debe ser realizada por dos o más empleados, entonces los dos empleados deben estar trabajando en la tarea al mismo tiempo. Un empleado no puede trabajar en dos tareas al mismo tiempo, y las tareas no se pueden interrumpir una vez comenzadas. El objetivo es maximizar la importancia de las tareas programadas, respetando las restricciones mencionadas. Presentamos dos modelos de programación lineal entera para este problema, junto con un enfoque basado en la descomposición combinatoria de Benders. Los experimentos computacionales muestran que este último algoritmo es efectivo para resolver instancias reales del problema.

Publicado
2024-08-29
Cómo citar
Bardengo, S., & Marenco, J. (2024). Un algoritmo basado en la descomposición combinatoria de Benders para un problema de programación de tareas. Memorias De Las JAIIO, 10(14), 387-390. Recuperado a partir de https://publicaciones.sadio.org.ar/index.php/JAIIO/article/view/908
Sección
SIIIO - Simposio Argentino de Informática Industrial e Investigación Operat