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