مقایسه اثر انواع عملگرهای الگوریتم ژنتیک بر مجموع دیرکردها در مسئله فلوشاپ

Abstract

مسئله زمانبندی فلوشاپ (FSSP) با هدف کمینه کردن مجموع دیرکردها، از جمله مسائل مشکل یا NP-hard است که تاکنون مقالات زیادی درباره آن نوشته شده است. در این خصوص به روش‌های فراابتکاری از جمله روش الگوریتم ژنتیک نیز توجه شایانی شده است. تعیین پارامترهای الگوریتم‌های فراابتکاری نیز از جمله موضوعات مهمی است که پژوهش‌های زیادی را به خود اختصاص داده است. در همین راستا، این مقاله به بررسی اثر انواع عملگرهای تقاطعی و جهشی الگوریتم ژنتیک با هدف کمینه کردن مجموع دیرکردها در مسئله فلوشاپ جایگشتی می‌پردازد تا مشخص شود که کدام یک از آن‌ها برای استفاده در این مسئله مناسب‌تر است. نتایج عددی بدست آمده حاکی از آن است که از بین عملگرهای تقاطعی متداول، عملگرهای یک نقطه‌ای و دو نقطه‌ای نوع یک و از بین عملگرهای جهشی، عملگر جابجاییِ مجاور در اغلب موارد بهترین مقدار برای مسئله مذکور هستند.