دسته بندي علمی – پژوهشی : 
تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه-  …

دسته بندي علمی – پژوهشی : تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه- …

(۳-۲۱)

 

در مدل فوق تابع هدف شماره (۱۲-۳) مجموع هزینه های در اختیار گرفتن تمام منابع برای اجرای فعالیت ها در کل دوره زمانی برنامه ریزی و برای تمامی حالت های اجرای را به علاوه هزینه تخطی از افق زمانبندی نهایی پروژه را کمینه می نماید. تابع هدف (۱۳-۳) کل زمان پروژه را کمینه می کند. محدودیت شماره (۱۴-۳) تضمین می کند که هر فعالیت در تمام دروه برنامه ریزی و در تمام حالت های اجرایی فقط یکبار اجرا شود. محدودیت شماره (۱۵-۳) روابط تقدم و تاخر از نوع پایان به آغاز با مقداری تاخیر/تعجیل بین فعالیت های پیش نیاز و پس نیاز را با در نظر گرفتن کل حالت های اجرایی و کل دوره برنامه ریزی پروژه ارضا می کند. محدودیت شماره (۱۶-۳) رابطه میان زمان پایان و زمان شروع یک فعالیت را با در نظر گرفتن تمام حالت های اجرایی در کل دوره برنامه ریزی را ارضا می کند. محدویت شماره (۱۷-۳) به کمک متغیر آزاد در علامت y کمک می کند تا حد بالای پروژه ارضا شود و در غیر اینصورت در تابع هدف جریمهای برای تخطی از حد بالای پروژه در نظر گرفته شده است) (y+. محدودیت های (۱۸-۳) الی (۲۱-۳) نوع متغیرهای تصمیم مساله را شرح می دهند.
مدل فوق علاوه بر کمینه کردن مجموع مربعات منابع مصرفی در کل دوره ها (سعی در تسطیح مقدار مصرف منابع) در حالت منابع نامحدود، سعی در کمینه کردن زمان کل پروژه نیز دارد. همچنین برای تخطی از زمانبندی فراتر از کل افق برنامه ریزی یک جریمه به پای تابع هدف گذاشته می شود.
 
الگوریتم ژنتیکNSGA-II
این الگوریتم با اضافه شدن دو عملگر ضروری به الگوریتم ژنتیک تک هدفه معمولی، به یک الگوریتم چند هدفه تبدیل شده است که بجای یافتن بهترین جواب، دسته ای از بهترین جوابها را می دهد که با نام پارتو فرانت شناخته می شوند. این دو عملگر عبارتند از:
عملگری که یک معیار برتری (رتبه) براساس مرتب سازی نامغلوب به اعضای جمعیت اختصاص می دهد.
عملگری که تنوع جواب را در میان جوابهای با رتبه برابر حفظ نگه میدارد.
طرح پایه
قبل از اینکه الگوریتم ژنتیک اجرا گردد، ما یک روند پیش پردازش[۱۸۱] (معرفی شده توسط
Sprecher et al.1997)، بمنظور تطبیق داده های مسئله بامدل و کاهش فضای جستجو انجام می دهیم. بعد از روند پیش پردازش، الگوریتم چند هدفه NSGA-II اجرا شده که مراحل آن به صورت زیر می باشد:
تولید جمعیت اولیه (Pt)با N کروموزوم(جمعیت اولیه به صورت تصادفی انتخاب شده به صورتی که هیچیک از کروموزوم ها تکراری نباشند.)
تولید جمعیت ثانویه ای(Qt)با Nکروموزوم با اعمال تزویج و جهش برN کروموزوم اولیه (Pt).
یافتن کروموزوم های بیرونی و نزدیکتر به مبدا از جمعیت ۲N کروموزوم (Pt+Qt)(یافتن نقاط غیرپست با استفاده از الگوریتم مرتب سازی بر اساس نقاط غیر پست[۱۸۲])
انتخاب N عضو غیرپست (Pt+1) از مجموعه نقاط غیر پست با ۲N عضو از جبهه پارتو (Pt+Qt). (با استفاده از فضای مختصاتی زمان-هزینه-تسطیح منبع، تعداد N کروموزومی که نزدیک ترین فاصله نسبت به مبدا مختصات را دارا می باشند، انتخاب می گردد.)
اعمال انتخاب، آمیزش و جهش بر نسل قدیم (Pt+1) و تولید نسل جدید با اندازه N کروموزوم (Qt+1).
در ادامه برای توضیح واضحتر مولفههای الگوریتم ژنتیک، شبکه فعالیتهای یک پروژه ساده با ۶ فعالیت مانند شکل (۲-۳) را در نظر می گیریم.

این مطلب را هم بخوانید :
تسطیح منابع نامحدود پروژه با در نظر گرفتن منابع متعدد و اهداف چندگانه- ...

شکل ۲-۳- پروژه نمونه

کد گذاری و بازنمائی مدل
از آنجاکه ما با حالت چند مد مسئله زمانبندی پروژه سروکار داریم، الگوریتم ژنتیک ما باید بازتاب کننده هر دو مسئله زمانبندی(مشخص کردن زمان شروع فعالیتها) و مسئله تخصیص مد (مشخص کردن مدی که فعالیت در آن اجرا می شود) باشد. از طرفی چون این دو مسئله با هم در تداخلند و روی هم تاثیر می گذارند، هدف ما این است که این دو مسئله با هم و همزمان مطرح شوند.(برای مثال هیچ تعریفی برای خوب بودن تخصیص مد یک فعالیت وجود ندارد، تا اینکه اثر ناشی از تخصیص این مد، روی زمان شروع دیگر فعالیت ها و مدت زمان و میزان هزینه ی کل پروژه معلوم گردد.)
برای بازنمائی اعضا در مدل مذکور از ماتریس جفت I=(λ,μ) استفاده شده که در سطر اول این ماتریس (λ)، بازنمائی فعالیت پروژه به صورت لیست فعالیت ها[۱۸۳] و سطر دوم تخصیص مدها به فعالیت ها (μ) می باشد.
I =
(۳-۲۲)
طول این کروموزوم دو سطری به اندازه تعداد فعالیت های پروژه (J) می باشد.
در ادامه برای آشنائی بیشتر با بازنمائی کروموزوم به صورت لیست فعالیت ها، این موضوع بسط داده می شود:
لیست فعالیت ها[۱۸۴]
در بازنمائی کروموزوم به صورت لیست فعالیتها، فعالیت های یک شبکه در یک ردیف با رعایت پیش نیازی به صورت زیر قرار میگیرند:
(۳-۲۳)
 
در این لیست فعالیت، اندیس موقعیت jg بالاتر از اندیس موقعیت پیش نیازهای آن است. به بیان واضح تر فعالیت jg بعد از پیش نیازهای خود در لیست قرا می گیرد.
الگوریتم تولید لیست فعالیتها:
این الگوریتم شامل J مرحله است(یعنی به اندازه تعداد فعالیت ها تکرار می شود). در هر مرحله یک فعالیت از مجموعه فعالیت های واجد شرایط Dg (فعالیت هائی که تا این مرحله پیش نیازهای آنها Pj وارد لیست شده باشد.) انتخاب شده و به مجموعه فعالیت های لیست PSg اضافه می شود.
شکل ۳-۳-الگوریتم تولید لیست فعالیتها
جدول ۳-۳ مرحله به مرحله اجرای الگوریتم را در شبکه فعالیت های پروژه شکل (۲-۳) نمایش می دهد:
جدول ۳-۳-روند تولید یک نمونه از لیست فعالیت ها

منبع فایل کامل این پایان نامه این سایت pipaf.ir است
برچسب گذاری شده با: