Premium
Timetabling through Constrained Heuristic Search and Genetic Algorithms
Author(s) -
MONFROGLIO ANGELO
Publication year - 1996
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(199603)26:3<251::aid-spe9>3.0.co;2-e
Subject(s) - backtracking , genetic algorithm , computer science , mathematical optimization , heuristics , heuristic , population , algorithm , mathematics , demography , sociology
Hybrid genetic algorithms are presented that use constrained heuristic search and genetic techniques for the timetabling problem (TP). The TP is an NP‐hard problem for which a general polynomial time deterministic algorithm is not known. The paper describes the classification of constraints and the constraint ordering to obtain the minimization of backtracking and the maximization of parallelism. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited to this kind of problem, since there exists an easy way to assess a good timetable, but not a well structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solution. The evaluation function and the genetic operators are well separated from the domain‐specific parts, such as the knowledge of the problem and the heuristics, i.e. from the timetable builder. The present paper illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favourably with known programs to solve decision problems under logic constraints. The cost of the new algorithm and the quality of the solutions obtained in significant experiments are reported.