قاسم مصلحی، علی حکیمیان، مصطفی ابویی اردکان،
جلد ۲۳، شماره ۴ - ( ۱۲-۱۳۹۱ )
چکیده
در این مقاله مسئله زمان‌بندی فلوشاپ دو ماشین با در نظر گرفتن ورود غیر همزمان و با هدف کمینه‌سازی تعداد کارهای دیرکرددار بررسی شده‌است. در ابتدا پیچیدگی مسأله بررسی و ثابت شده که مسأله NP hard است. بنابراین برای حل مسئله فوق یک الگوریتم ابتکاری که قابلیت حل مسائل با ابعاد خیلی بزرگ را دارد، ارائه شده است. همچنین به منظور حل بهینه مسئله از روش شاخه و کران با در نظر گرفتن الگوریتم ابتکاری به عنوان حد بالا بهره گرفته شده‌است. نتایج محاسباتی نشان میدهد که رویه شاخه‌و‌کران مسائل با ابعاد ۲۸ فعالیت در گروه High و ۲۰ فعالیت در گروه Low را در زمان منطقی و به طور کامل حل می‌کند، که این امر کارآیی حد بالا، حدود پایین و اصول غلبه ارائه شده برای مسئله را نشان میدهد. همچنین نشان داده شد که متوسط نسبت جواب بهینه به الگوریتم ابتکاری با هدف ∑(۱-Ui) حداکثر ۱۱/۱ برابر می‌باشد که در مقایسه با الگوریتم‌های ارائه شده در تحقیقات مرتبط با کارهای دیرکرددار نسبت کوچکی می‌باشد. این نسبت نشان دهنده کارایی بالای الگوریتم ابتکاری است. با توجه به کارآیی بالای الگوریتم ابتکاری، مسائل نمونه با ابعاد بزرگ نیز حل و نتایج آن ارائه شده است.
