بکارگیری الگوریتم ترکیبی بهینه سازی دسته ذرات برای حل مساله سنتی زمانبندی کار کارگاهی

مساله زمانبندی کار کارگاهی سنتی یک مساله NP-Complete از نوع قوی است و به همین دلیل در تحقیقات صورت گرفته ، الگوریتم های فراابتکاری زیادی برای حل آن ارایه شده است ، اما تنها در تعداد معدودی از آنها الگوریتم بهینه سازی دسته ذرات (PSO) مورد توجه قرار گرفته است که یکی از دلایل آن می تواند جدید بودن این روش باشد . در الگوریتم ارایه شده در این مقاله ابتدا بمنظور حفظ موجه بودن جوابها در هر تکرار الگوریتم شیوه نمایش برمبنای فهرست اولویت برای جوابها انتخاب شده است . همچنین برای ایجاد رابطه یک به یک بین جواب مساله که ماهیت گسسته دارد و جواب مورد پذیرش الگوریتم که اعداد پیوسته هستند و همچنین حفظ قانونی بودن جوابها در هر تکرار ، یک شیوه جدید براساس تبدیل مبنای اعداد وبا استفاده از نمایش اعداد در مبنای فاکتوریل توسعه داده شده است . با توجه به تکاملی بودن PSO ، به منظور شروع از جواباهای نسبتا خوب از یک الگوریتم ابتکاری جستجوی تصادفی حریصانه به عنوان مولد جوابهای اولیه استفاده شده است . هرجواب به دست آمده توسط PSO بوسیله یک الگوریتم جستجوی محلی بهبود داده می شود . برای فرار از دام بهینه های محلی یک رابطه جدید بهنگام سازی سرعت در الگوریتم PSO توسعه داده شده است . به همین منظور و همچنین برای بهبود نهایی جواب به دست آمده توسط PSO از یک الگوریتم آنیلینگ شبیه سازی شده استفاده شده است . الگوریتم بر روی تعدادی از مسایل نمونه آزمایش شده و نتایج حاصل بیانگر دقت و کارایی جوابها نسبت به سایر الگوریتم های موجود برای حل مساله مورد بحث است.

Keywords:

مساله زمانبندی کار کارگاهی , بهینه سازی دسته ذرات , فاکتورادیک , آنیلینگ شبیه سازی شده , جستجوی تصادفی حریصانه