ارائه الگوریتم تبادل جفتی اصلاح شده در مسأله زمانبندی ماشین‌های موازی یکسان

Abstract

مساله حداقل سازی دامنه عملیات روی ماشین های موازی یکسان جزء مسائل کلاسیک حوزه ی مسائل زمانبندی محسوب می شود. این مساله به لحاظ پیچیدگی در دسته مسائل شدیدا پیچیده طبقه بندی می گردد. به طوری که روش های بهینه جهت حل این مساله، با افزایش ابعاد مساله به سرعت کارایی خود را از دست می دهند. به همین دلیل و با توجه به کاربردهای عملی فراوان این مساله، گرایش ها به سمت استفاده از روشهای تقریبی معطوف شده است. در این راستا الگوریتم های ابتکاری فراوانی برای این مساله ارائه شده است. الگوریتم تبادل جفتی یکی از کاراترین الگوریتم های ابتکاری ارائه شده برای این مساله است. در این مقاله با اعمال تغییراتی روی این الگوریتم، نسخه ویرایش شده این الگوریتم معرفی شده است. نتایج محاسباتی نشان داد که نسخه ویرایش شده تبادل جفتی بدون تغییر محسوس در زمان حل، جواب های به مراتب مطلوب تری را به دست می آورد.