استفاده از بهینه سازی کلونی مورچگان ترکیب شده با روش جستجوی ممنوع برای مساله زمان بندی تولید کارگاهی

دراین مقاله از بهینه سازی کلونی مورچگان ترکیب شده با روش جستجوی ممنوع برای مساله زمان بندی تولید کارگاهی استفاده شده است. بجای روش های متداول برای ایجاد یک زمان بندی مجاز از روش جدید تجزیه که از فرآیند تغییرسمت دادن گلوگاه "shifting bottleneck procedure" و مکانیزم باز-بهینه سازی زمان بندی های جزیی الهام گرفته شده است. در ضمن روش جستجوی ممنوع برای بالا بردن کیفیت جواب بکار برده شده است.در مساله زمان بندی تولید کارگاهی یک مجموعه متناهی ازکارها باید توسط یک مجموعه متناهی از ماشین ها پردازش شوند، هر کار از یکسری ترتیب اجرایی روی ماشین ها پیروی می کند؛ بعلاوه زمان پردازش هر شغل روی یک ماشین قطعی است، هر ماشین در یک زمان میتواند حداکثر یک کار را انجام دهد که این تابع قیود فصلی و عطفی می باشد، همچنین یک کار پس از شروع تا زمان اتمامش نمیتواند به وقفه بیفتد. این مساله در حالت کلی یک مساله NP-hard می باشد.الگوریتم فراابتکاری مجموعه ای از مفاهیم الگوریتمی است که از آنها می توان برای تعریف روش های ابتکاری اسفاده کرد که این کاربرد گسترده ای در مسائل مختلف دارد. لیکن هر الگوریتم فراابتکاری نقاط قوت و ضعف خاص خودش را دارد بهمین خاطر اکثر محققان سعی در استفاده از الگوریتم های مرکب دارند تا یکدیگر را کامل کنند که این باعث بهبود کارآمدی و اثربخشی الگوریتم خواهد شد. بهینه سازی کلونی مورچگان(ACO) یک زمانبندی اولیه مناسب ارائه می دهد که این زمان بندی به طور تکراری به توسط روش جستجوی ممنوع بهبود پیدا می کند.یک زمان بندی مجاز در مورد JSSP ساختن جایگشتی از کارها برای هر یک از ماشین ها است، در واقع هدف پیداکردن یک زمان بندی مجاز است که زمان اتمام کل کارها مینیمم شود. این مساله را میتوان به صورت ریاضی نیز بیان کرد، اگر M مجموعه ماشین ها و J مجموعه کارها وO مجموعه عملیات ها باشد که در آن ، ( O ) نشان دهنده عملیات خاصی از کار j که روی ماشین m انجام می شود باشد آنگاه نماد نشان دهنده محدودیت اجراء عملیات باشد، بدین معنا که نمیتواند قبل از پردازش شود. فرض کنید نشاندهنده جایگشتی از کارها روی ماشین m باشد ونیز عنصری از باشد که در موقعیت j ام قرار گرفته است