.png){kind=icon}
.png){kind=icon}
Return
The Interleaved Constructive Memetic Algorithm and its application to timetabling
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2011.11.020.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Genetic algorithms
Timetabling
Scheduling
Metaheuristics
Memetic algorithms
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W