بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***


حل مسأله زمانبندي پروژه با منابع محدود چند هدفه فازي با استفاده از الگوريتم ژنتيک NSGA-II


خلاصه
در اين مقاله ، به مسأله زمانبندي پروژه چند هدفه فازي با محدوديت منابع پرداخته ميشود. چنانچه به منظور نزديکي هر چه بيشتر مدل به شرايط واقعي زمان انجام هر فعاليت به صورت فازي در نظر گرفته شده است . اهدافي که در اين مدل در نظر گرفته شدهاند عبارتند از حداقل کردن زمان و هزينه کل پروژه. با توجه به چند هدفه بودن و پيچيدگي محاسباتي مدل بدست آمده، از الگوريتم تکاملي چند هدفه معروف بنام الگوريتم ژنتيک مرتب شده نامغلوب ١ (NSGA-II) براي حل مدل ارايه شده است . براي ارزيابي روش پيشنهادي، مسايل متعددي انتخاب شده و کارايي اين روش بر پايه شاخص هاي طراحي شده، با الگوريتم ژنتيک رتبه بندي شده نامغلوب ٢ (NRGA) مورد مقايسه قرار گرفته ميشود و در نهايت براي بررسي نتايج جوابهاي اين دو الگوريتم از روشهاي تصميم گيري چند معياره و روشهاي آماري استفاده مي گردد تا الگوريتم کاراتر انتخاب گردد.
کلمات کليدي: زمانبندي پروژه، محدوديت منابع ، تئوري مجموعه هاي فازي، الگوريتم ژنتيک مرتب شده نامغلوب (NSGA-II) و الگوريتم ژنتيک رتبه بندي شده نامغلوب (NRGA)

.1 مقدمه
مساله زمانبندي پروژه با منابع محدود٣ (RCPSP) در واقع کلي ترين مساله زمانبندي است که مسائل زمانبندي کار کارگاهي ٤، جريان کارگاهي ٥ و ساير مسائل زمانبندي همگي زير مجموعه اي از اين مساله به حساب ميآيند [١]. به طور کلي، RCPSP درگير يافتن توالي مناسبي براي انجام فعاليت هاي يک پروژه است به نحوي که محدوديتهاي تقدم و تاخر شبکه پروژه و انواع مختلف محدوديت هاي منبعي موجود در پروژه به طور همزمان ارضاء شوند و اهداف معيني از جمله زمان انجام پروژه، هزينه انجام، تعداد فعاليت هاي تاخيردار و غيره بهينه گردند [٢]. RCPSP در حالت کلي يک مسأله بهينه يابي ترکيبي است که از لحاظ رده پيچيدگي جزء مسائل سخت و پيچيده تلقي مي شود. [٣]. با توجه به پيچيدگي اين مسائل ، براي حل مسأله زمانبندي پروژه با منابع محدود چند هدفه فازي از الگوريتم تکاملي چند هدفه معروف بنام الگوريتم ژنتيک مرتب شده نامغلوب استفاده شده است . از سوي ديگر يکي از عواملي که استفاده از روشهاي قطعي را در حل مسائل RCPSP مورد ترديد قرار ميدهد، ماهيت غير قطعي بسياري از فعاليت هاست . از آنجاکه به دليل کمبود اطلاعات در مورد فعاليت هاي پروژه، پارامترهاي مربوط به آنها توسط افراد خبره تخمين زده ميشوند ، استفاده از روش فازي براي مدل کردن اين اطلاعات مناسبتر است . در اين مقاله در بخش دوم به مرور ادبيات مسائل زمانبندي پروژه با منابع محدود پرداخته ميشود. در بخش سوم مدل رياضي به همراه فرضهاي مدل در نظر گرفته شده ارائه ميگردد. در بخش چهارم روشي براي تبديل اعداد فازي به يک مقدار قطعي ارائه ميگردد. در بخش پنجم روش حل تشريح ميگردد. در بخش ششم کارائي الگوريتم ارائه شده مشخص مي گردد و در بخش هفتم نتيجه گيري مطرح ميشود.

.2 مرور ادبيات




براي نخستين بار مسئله تخصيص منابع محدود توسط پريتسکر و همکاران [٤] در ادبيات مساله برنامه ريزي پروژه مطرح شد. اولين مطالعه بر روي مدلهاي برنامه ريزي پروژه با محدوديت منابع در شرايط فازي توسط هاپکه و همکاران [٥] و هاپکه اسلووينسکي [٦] ارائه گرديد. لئو و همکاران [٧] از الگوريتم ژنتيک براي حل مساله زمان هزينه با محدوديت منابع در شرايط فازي استفاده کردند. آنها زمان انجام فعاليت ها را فازي در نظر گرفتند و مساله را با تابع هدف مي نيمم زمان اتمام پروژه حل کردند. کوليش و هارتمن [٨] به بررسي آزمايشي بسياري از رويکردهاي ابتکاري حل مساله برنامه ريزي پروژه با منابع محدود پرداختند. نتايج تحقيقات آنان نشان داد که الگوريتم هاي ژنتيک ، جستجوي محلي و ترکيبي ژنتيک نتايج بهتري نسبت به رويکردهاي ديگر داشتند. باسکار و همکاران [٩] از يک روش هيوريستيک براي حل مساله زمانبندي پروژه با محدوديت منابع با زمان فعاليت هاي فازي استفاده کردند، روش آنها بر پايه اولويت بندي نسل هاي موازي ميباشد.
.3 ارائه مدل
٣-١. فرضيات مسأله
شبکه تقدم و تأخر فعاليتها جهتدار است . هر زمان که پيشنيازهاي يک فعاليت انجام شده باشند، آن فعاليت قابل اجراست . ارتباط پيش نيازي بين فعاليت ها از نوع پايان به شروع ميباشد. فعاليت هاي اول و آخر (N و١) موهومي ١ در نظر گرفته ميشوند. فعاليت ها تنها در يک حالت ٢ انجام ميپذيرند.
ظرفيت منابع محدود و مشخص ميباشد. سطح مورد نياز منابع براي انجام هر فعاليت مشخص است . منابع مورد استفاده در پروژه از نوع تجديدپذير ميباشد. مدت زمان لازم براي انجام هر فعاليت مشخص ولي غير قطعي (به صورت عدد فازي) است . زمان پرداخت وامها براي انجام فعاليت در ابتداي پروژه مشخص شده است . مدل ارائه شده هم داراي وام مصوب و هم داراي وام ضروري ميباشد که نرخ بهره وام مصوب و وام ضروري متفاوت ميباشد. پرداخت وام در زماني زودتر از زمان تعين شده براي هر فعاليت ، داراي نرخ بهره بيشتري ميباشد. هزينه انجام هر فعاليت در هر روز از مدت انجام آن مشخص است . محدوديت بودجه وجود ندارد.
٣-٢. مدل رياضي
n
٣-٣. متغيرها و پارامترها
n تعداد فعاليت ها، t زمان شروع فعاليت t،i زمان شروع فعاليت j،di مدت زمان انجام فعاليت i،Si مجموعه فعاليت هاي که فعاليت jبه
آنها وابسته است ، k تعداد انواع منابع قابل تجديد، Rk تعداد واحدهاي در دسترس از منبع k به ازاي هر واحد زمان ، rik مقدار منبع k که مورد نياز فعاليت i است ، (m)t مجموعه فعاليت هاي در حال انجام در زمان t،r نرخ بهره در واحد زمان براي فعاليت هاي که طبق برنامه وام دريافت ميکنند،  نرخ بهره در واحد زمان براي فعاليت هاي که زودتر از زمان برنامه وام دريافت مي کنند، t زمان کل اتمام پروژه، Ci هزينه انجام n فعاليت i،xi زمان دريافت وام فعاليت iام طبق برنامه ،i زمان دريافت وام فعاليت iام زودتر از معادله (١) مقدار تابع هدف اول بوده و زمان تکميل پروژه را نشان ميدهد که بايد کمينه گردد. معادله (٢) مقدار تابع هدف دوم بوده و هزينه انجام پروژه را نشان ميدهد که بايد کمينه گردد. معادله (٣) نشان دهنده روابط تقدم و تاخر است . معادله (٤) بيان ميکند که در هيچ لحظه زماني از برنامه ريزي پروژه، ميزان مصرف منابع K توسط فعاليت i نبايد از ميزان در دسترس آن بيشتر شود. معادله (٥) نشان ميدهد که زمان شروع هر فعاليت
i بايد مثبت باشد.
.4پتبديل فازي به کلاسيک
در اين مقاله براي تبديل اعداد فازي به يک مقدار قطعي از روشي که توسط خيمينس و همکاران [١٠] مطرح شد استفاده گرديده است . اين روش براي دي فازي کردن اعداد فازي، از برشهاي در بازه [٠,١] اعداد صحيح استفاده ميکند و بهترين برش قابل قبول و مطلوب را ارائه ميکند. مقدار تابع هدف و محدوديت ها مطابق (٦) و (٧) بر اساس هر يک از برشها محاسبه ميگردند.
در معادله (٦)،c مقدار فازي، x متغير تصميم
با استفاده از معادلات (٨) و (٩) تابع عضويت و درجه عضويت بر اساس هر يک از برش ها مشخص ميگردد.
در معادله (٨)،تابع عضويت ، G بالاترين سطح در تابع عضويت ، G پائين ترين سطح در تابع عضويت .

براي بالانس بين درجه شدني و درجه رضايتبخشي از معادله (١٠) و انتخاب ماکزيمم جواب مطابق معادله (١١) انتخاب مي باشد.

F درجه شدني ، S درجه رضايتبخشي
در واقع اين مقدار بالاترين درجه عضويت در تصميم گيري مجموعه فازي ميباشد.
.5 روش حل
در اين مقاله براي حل مدل دو هدفه ، از الگوريتم فراابتکاري شامل الگوريتم ژنتيک مرتب سازي نامغلوب کنترل شده ontrolled NSGA-II) استفاده شده است . روش حل اين الگوريتم مطابق فلوچارت شکل ١ ميباشد.




شکل ١- فلوچارت الگوريتم Controlled NSGA-II
٥-١) مقدار دهي اوليه
اندازه جمعيت اوليه ٢، احتمال عملگر تقاطع ٣ (Pc)، احتمال عملگر جهش ٤ (Pm)، توليد نسل (Gen)
٥-٢) ارزيابي کروموزوم
براي دستيابي به يک الگوريتم مناسب يکي از مهمترين اقدامات، طرح کروموزوم مناسب است . در اين مقاله براي نمايش جوابهاي مساله ، يک کروموزوم يک رديفه ارائه شده است . کروموزومها نشان دهنده تعداد فعاليت ها ميباشند که الويت آنها را براي استفاده از منابع مشخص ميکند. بطور مثال براي يک پروژه با ٥ فعاليت ، يک نمايش از کروموزومها بصورت شکل ٢ ميباشد.که فعاليت چهارم براي انجام در اولويت سوم قرار دارد.

شکل ٢- ساختار کروموزوم

٥-٣) مرتب سازي سريع نامغلوب ها و فاصله ازدحام
در اين مرحله مرتب کردن جمعيت براساس نامغلوبها با استفاده از مفهوم غلبه و مغلوب و فاصله ازدحام صورت ميگيرد.

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید