The Interleaved Constructive Memetic Algorithm and its application to timetabling

Timetabling problems are well known NP-hard constraint satisfaction problems, and real-world cases often have complicated and challenging structures. For such problems, we present a new hybrid method, "Interleaved Constructive Memetic Algorithm" (ICMA) that interleaves memetic algorithms with constructive methods. ICMA works using an active subset of all the events. Starting with a few events, in multiple construction stages ICMA increases the active set to eventually include all of them. At each stage, a memetic algorithm (MA) is applied to improve the current partial solution before the next construction step. We also describe a real-world course timetabling problem, the "Preparation School Timetabling Problem" (PSTP), which is of particular interest because it has a highly hierarchical structure arising from various organisational requirements. An important advantage of ICMA is that both the constructive heuristics and MA can be tailored to exploit such hierarchical structures. We give empirical results showing that ICMA performs better than the corresponding conventional MA on the PSTP. (C) 2011 Elsevier Ltd. All rights reserved.