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

Abstract

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