The Interleaved Constructive Memetic Algorithm and its application to timetabling

The Interleaved Constructive Memetic Algorithm and its application to timetabling

0.00 Avg rating0 Votes
Article ID: iaor20121519
Volume: 39
Issue: 10
Start Page Number: 2310
End Page Number: 2322
Publication Date: Oct 2012
Journal: Computers and Operations Research
Authors: , ,
Keywords: combinatorial optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.