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

در این مقاله مسئله زمان بندی فلوشاپ دو ماشین با در نظر گرفتن ورود غیرهمزمان و با هدف کمینه سازی تعداد کارهای دارای دیرکرد بررسی شده است . در ابتدا پیچیدگی مساله بررسی و ثابت شده که مساله NP-hard است . بنابراین برای حل مسئله فوق یک الگوریتم ابتکاری که قابلیت حل مسائل با ابعاد خیلی بزرگ را دارد ، ارائه شده است . همچنین به منظور حل بهینه مسئله از روش شاخه و کران با در نظر گرفتن الگوریتم ابتکاری به عنوان حد بالا بهره گرفته شده است . نتایج محاسباتی نشان می دهد که رویه شاخه و کران مسائل با ابعاد 28 فعالیت در گروه High و 20 فعالیت در گروه Low را در زمان منطقی و به طور کامل حل می کند ، که این امر کارآیی حد بالا ، حدود پایین و اصول غلبه ارائه شده برای مسئله را نشان می دهد. همچنین نشان داده شده که متوسط نسبت جواب بهینه وبه الگوریتم ابتکاری با هدف Σ(1-Ui) حداکثر 1/11 برابر می باشد که در مقایسه با الگوریتم های ارائه شده در تحقیقات مرتبط با کارهای دارای دیرکرد نسبت کوچکی می باشد. این نسبت نشان دهنده کارایی بالای الگوریتم ابتکاری است . با توجه به کارآیی بالای الگوریتم ابتکاری ، مسائل نمونه با ابعاد بزرگ نیز حل و نتایج آن ارائه شده است .

Keywords:

فلوشاپ دو ماشین , تعداد کارهای دارای دیرکرد , ورود غیرهمزمان , الگوریتم شاخه و کران , الگوریتم ابتکاری