Exploring the solution of course timetabling problems through heuristic segmentation Chapter in Scopus uri icon

Abstract

  • The aim of hyper-heuristics is to solve a wide range of problem instances with a set of heuristics, each chosen according to the specific characteristics of the problem. In this paper, our intention is to explore two different heuristics to segment the Course Timetabling Problem (CTT) into subproblems with the objective of solving them efficiently. Each subproblem is resolved as a Constraint Satisfaction Problem (CSP). Once the CTT is partitioned and each part solved separately, we also propose two different strategies to integrate the solutions and get a complete assignment. Both integration strategies use a Min-Conflicts algorithm to reduce the inconsistencies that might arise during this integration. Each problem instance was solved with and without segmentation. The results show that simple problems do not benefit with the use of segmentation heuristics, whilst harder problems have a better behavior when we use these heuristics. © 2013 Springer-Verlag.

Publication date

  • April 10, 2013