مدل احتمال جدید برای ضمانت کردن مشکل مسیر بحرانی با الگوریتم اکتشافی A new probability model for insuring critical path problem with heuristic algorithm

Abstract

In order to obtain an adequate description of risk aversion for insuring critical path problem, this paper develops a new class of two-stage minimum risk problems. The first-stage objective function is to minimize the probability of total costs exceeding a predetermined threshold value, while the second-stage objective function is to maximize the insured task durations. For general task duration distributions, we adapt sample average approximation (SAA) method to probability objective function. The resulting SAA problem is a two-stage integer programming model, in which the analytical expression of second-stage value function is unavailable, we cannot solve it by conventional optimization algorithms. To avoid this difficulty, we design a new hybrid algorithm by combining dynamic programming method (DPM) and genotype-phenotype-neighborhood based binary particle swarm optimization (GPN-BPSO), where the DPM is employed to find the critical path in the second-stage programming problem. We conduct some numerical experiments via a critical path problem with 30 nodes and 42 arcs, and discuss the proposed risk averse model and the experimental results obtained by hybrid GPN-BPSO, hybrid genetic algorithm (GA) and hybrid BPSO. The computational results show that hybrid GPN-BPSO achieves the better performance than hybrid GA and hybrid BPSO, and the proposed critical path model is important for risk averse decision makers.

Keywords: Critical path; Probability model; Stochastic optimization; Minimum risk criterion; Hybrid algorithm

چکیده فارسی

برای بدست آوردن شرح کافی در مورد ریسک مخالفت با ضمانت مشکل مسیر بحرانی، این مقاله رده جدیدی از مسائل ریسک حداقل دو مرحله ای توسعه می دهد. تابع هدف مرحله اول برای به حداقل رساندن احتمال وجود هزینه های مجموع متجاوز از مقدار آستانه از پیش تعیین شده است، در حالی که کار تابع هدف مرحله دوم به حداکثر رساندن طول مدت وظیفه تضمین است. برای توزیع دوره وظیفه عمومی، ما روش تخمین میانگین نمونه (SAA) را برای تابع هدف احتمال اتخاذ می کنیم. مسأله SAA منتج شده یک مدل برنامه نویسی صحیح دو مرحله ای است، که در آن نمود تحلیل از تابع ارزش مرحله دوم قابل دسترس نیست، و ما نمی توانیم آن را با الگوریتم های بهینه سازی مرسوم حل کنیم. برای جلوگیری از بروز این مشکل، ما الگوریتم پیوندی جدیدی با تلفیق روش برنامه نویسی پویا (DPM) و مجاورت ژنوتیپ-فنوتیپ مبنی بر بهینه سازی گروه حروف باینری (DPN-BPSO) طراحی کرده ایم که در آن DPM برای یافتن مسیر بحرانی در مسأله برنامه نویسی مرحله دوم به کار رفته است و ما چند آزمایش عددی از طریق مسأله مسیر بحرانی یا 30 گره و 42 کمان انجام داده ایم و در مورد مدل مغایر ریسک و نتایج تجربی حاصل شده با GPN-BPSO پیوندی، الگوریتم ژنتیک پیوندی (GA) و BPSO پیوندی بحث کرده ایم. نتایج محاسباتی نشان می دهند که GPN-BPSO به عملکرد بهتری نسبت به GA پیوندی و BPSO پیوندی دست می یابد، و مدل مسیر بحرانی پیشنهادی برای تصمیم گیرندگان مخالف ریسک مهم است.

واژگان کلیدی: مسیر بحرانی، مدل احتمال، بهینه سازی تصادفی، شرایط ریسک مینیمم، الگوریتم پیوندی

مشخصات

توسط: Zhenhong Li,YankuiLiu, GuoqingYang مجله: Neurocomputing انتشارات: Elsevier سال انتشار: 2012 میلادی تعداد صفحات متن اصلی: 7 تعداد صفحات متن ترجمه: 16 تاریخ درج: ۱۳۹۵/۱۰/۸ منبع: دیتاسرا

خرید آنلاین فایل ترجمه

عنوان: مدل احتمال جدید برای ضمانت کردن مشکل مسیر بحرانی با الگوریتم اکتشافی حجم: 408.20 کیلوبایت فرمت فایل: pdf قیمت: 129500 تومان رمز فایل (در صورت نیاز): www.datasara.com نرم افزارهای مورد نیاز: winrar - adobe acrobat - office