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

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