Evaluation of parallel search for a large scheduling problem

Abstract

"El problema de planificar los exámenes finales de una universidad puede categorizarse naturalmente como un problema de satisfacción de restricciones. Planificar es un problema abordado extensamente por la comunidad de la programación orientada a restricciones. Sin embargo, debido al tamaño que representa el problema aplicado a los examenes finales de una universidad, las técnicas estándar resultan insatisfactorias al intentar proveer una solución, dado su tiempo de ejecución. En este documento presentamos un algoritmo de descomposición en paralelo, que extiende el solver OscaR. Evaluamos el desempeño del algoritmo y lo contrastamos con el del algoritmo existente en OscaR. Nuestro problema de clasificación involucra más de 1100 variables, sin embargo las pruebas con un conjunto de 320, ya empiezan a mostrar una mejora super lineal en la etapa de descomposición." -- Tomado del formato de documento de grado

"The final exam scheduling problem can be naturally characterized as a constraint satisfaction problem, defining the relations between exams and available resource as constraints. Such problem, has been widely studied in the constraint programming community. However, due to the increasing size of the problem, and the complexity of the relations between constraints, applying standard constraint programming solutions is unsatisfactory to provide an answer to large exam scheduling problems. In this paper we present a parallel problem decomposition algorithm, that extends the OscaR solver. We evaluate the performance of the proposed algorithm, in contrast to the existing algorithm in OscaR. Our scheduling problem considers over 1100 variables. The evaluation results for 321 variables, show a superlinear speedup on the problem decomposition phase." -- Tomado del formato de documento de grado