ارایه الگوریتمی کارا برای حل مساله فلوشاپ ترکیبی با محدودیت انباره های میانی

مساله فلوشاپ ترکیبی با هدف کمینه کردن زمان کل انجام کارها و با محدودیت ظرفیت انباره های میانی از جمله مسایل بهینـه سـازی ترکیبی در خانواده مسایل NP-Hard به شمار می رود . در این مقاله، بین هر دو ایستگاه متوالی محلی برای نگهداری کارهای نیمه تمـام بـا ظرفیت محدود در نظر گرفته شده که این محدودیت بحث مسدود شدن ماشین ها را پیش مـی کـش اند و بـر پیچیـدگی مـساله بطـ ور قابـل ملاحظه ای می افزاید . جواب مساله برداری با طول ) N تعداد کارها ) می باشد که توالی انجام کارها در ایستگاه اول را مـشخص مـی کنـد . بـه موازات هر جواب برداری یک فرایند تکمیلی بر اساس اصول شبیه سازی گسسته - پیشامد و تعریف قوانین تقدم - تاخری خاص با هدف ارا یـ ه کاراترین برنامه زمانبندی عملیات توسعه داده شده است . در این مقاله بعد از تشریح مدل به منظور یافتن کاراترین الگوریتم حـل بـرای ایـن مساله از دو الگوریتم فرا ابتکاری با تاکید بر روش ترکیب ی ژنتیک - جستجوی ممنوع استفاده شده و مقایـسه بـین ایـن روشـها و کـاراترین روش های ارا یه شده در مقالات عملی ارا یه شده است . با بهره گیری از خصوصیات مثبت هر یک از الگوریتم های ژنتیک و جستجوی ممنوع و ایجاد ترکیب مناسب از عملگرهای مختلف این دو الگوریتم در جستجوی فضای جواب، شـاهد افـزایش قابـل ملاحظـه قـدرت الگـوریتم پیشنهادی در رسیدن به بهترین جواب، در مقایسه با سایر روشها خواهیم بود . از جمله دستاوردهای جنبـی ایـن مقالـه، بهـره گیـری از روش پیشنهادی برای حل مسایل با ساختارهای جواب مشابه ( جایگشتی از N مولفه ) ، از جمله مساله برنامه ریزی تک ماشینه می باشد که بـ ه نوبـه خود حائز اهمیت است .

کلیدواژه ها:

مساله فلوشاپ ترکیبی ، مسدود شدن ، انباره های میانی ، شبیه سازی گسسته پیشامد ، الگوریتم های فرا ابتکاری