Resolución de problemas de planificación horaria usando computacion cuántica adiabática

Abstract

El objetivo de este proyecto es la utilización del computador cuántico adiabático de DWave para ejecutar el problema de programación lineal que la empresa Plannam ha cedido a la Facultad de Informática de San Sebastián para la elaboración de este proyecto. Concretamente, el problema que nos ataña trata sobre la asignación de tareas de un año a un conjunto de trabajadores teniendo en cuenta restricciones de tiempo y habilidad de cada trabajador.

Para ello, se hace un estudio de los pasos necesarios para resolver este tipo de problemas en el computador de DWave. En particular, se estudia el modelo de computación cuántica adiabática, los problemas de programación lineal (y algunas propiedades útiles para el caso que nos ocupa) y se explica el modelo Quadratic Unconstrained Binary Optimization (QUBO) que estas máquinas son capaces de ejecutar.

El análisis de los resultados muestran como el modelo desarrollado puede obtener resultados del problema de optimización si la configuración de la máquina de DWave es la correcta. También se muestran formas de como ir mejorando los modelos una vez conseguidos los primeros resultados e ir puliendo los valores clave para la ejecución correcta del problema. Por último, se proponen distintas líneas de investigación que aportarían nuevas formas de mejorar el modelo y conseguir que converja en una solución mejor con menor tiempo y esfuerzo.