حداقل دیرکرد در زمان بندی مسائل جریان کارگاهی با موعد تحویل میانی

این مقاله به  زمان بندی کارها در سیستم جریان کارگاهی با معیار عملکرد مجموع دیرکردهای مرحله ای می پردازد. این معیار بیانگر شرایطی است که کارها علاوه بر موعد نهایی، دارای موعدهای تحویل میانی برای فعالیت ها هستند. در برخی از امور، مانند پروژه های تحقیقاتی، کارهای خدماتی، طراحی و مهندسی، خروجی گام های مختلف تعیین شده و زمان تحویل آن ها مشخص می شود. با توجه به طی نمودن یک مسیر توسط این پروژه ها، استفاده از منابع مشترک و همچنین تعهد به انجام به موقع مراحل کاری و عدم تاخیر آن ها، برنامه ریزی صحیح برای تخصیص منابع و زمان بندی مناسب جهت حداقل کردن مجموع دیرکردها ضروری می نماید. تاکنون، این هدف کمتر مدنظر قرار گرفته و استفاده از روش های فراابتکاری برای حل آن مشاهده نشده است.  با توجه به NP-hard بودن چنین مسئله ای، در این مقاله نسبت به حل آن با روش های فراابتکاری، الگوریتم ژنتیک، شبیه سازی تبرید و ازدحام ذرات اقدام شد. ۹۶ مسئله در ابعاد مختلف و سه مقدار عامل فشردگی برای زمان های تحویل ایجاد و حل شدند. الگوریتم های شبیه سازی تبرید و الگوریتم ژنتیک در رابطه با دستیابی به هدف مسئله، یعنی حداقل مجموع دیرکرد، نتایج بهتری را نشان دادند. روش ازدحام ذرات زمان حل کمتری داشت. در کل با در نظر گرفتن هر دو شاخص، نتایج نشان از برتری الگوریتم ژنتیک در این مسئله دارد.

کلیدواژه ها:

زمان بندی جریان کارگاهی ، موعد تحویل میانی ، دیرکرد کل ، الگوریتم های فراابتکاری