کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475195 699245 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Interleaved Constructive Memetic Algorithm and its application to timetabling
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 10, October 2012, Pages 2310–2322
نویسندگان
, , ,