کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4962999 1447000 2017 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Effective local search algorithms for high school timetabling problems
ترجمه فارسی عنوان
الگوریتم های جستجوی محلی موثر برای مشکلات زمانبندی دبیرستان
کلمات کلیدی
زمانبندی کلاس معلم، جستجوی محلی اصطلاح جستجوی محدوده متغیر حداقل هزینه تخصیص مشکلی، نمودار اختلاف،
ترجمه چکیده
این مقاله به مشکل زمانبندی دبیرستان می پردازد. این مشکل شامل ایجاد جدول زمانی هفتگی برای جلسات بین کلاس ها و معلمان با هدف به حداقل رساندن نقض موارد خاص است. در دهه های گذشته چندین برنامه صحیح مخلوط برای این خانواده از مشکلات پیش بینی شده است. با این حال، نمونه های متوسط ​​و بزرگ هنوز با این برنامه ها با استفاده از حل کننده های پیشرفته ای حل نمی شوند و جامعه علمی به طراحی الگوریتم های محاسبات نرم جایگزین توجه خاصی داده است. در این مقاله، ما یک رویکرد محاسباتی نرم افزاری را بر مبنای چارچوب های متاگیریستی جستجوی جستجو محلی و متغیر محور جستجو ارائه می کنیم. الگوریتم های ما ساختارهای محله جدید و روش های جستجو محلی را برای انجام جستجو موثر ترکیب می کنند. ما الگوریتم های پیشنهاد شده بر روی انواع مشکلات را با استفاده از هفت نمونه عمومی و یک مجموعه داده جدید با 34 نمونه واقعی از جمله موارد بزرگ تأیید کردیم. نتایج نشان می دهد که الگوریتم های پیشنهادی در هر دو حالت، پیشرفته ترین روش ها را پیدا کرده و بهترین راه حل ها را در 38 مورد از 41 مورد آزمایش شده پیدا کرده اند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
پیش نمایش مقاله
الگوریتم های جستجوی محلی موثر برای مشکلات زمانبندی دبیرستان
چکیده انگلیسی
This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Soft Computing - Volume 60, November 2017, Pages 363-373
نویسندگان
, ,