پایان نامه با واژگان کلیدی توسعه مدل

دانلود پایان نامه ارشد

الگوريتم حل است از اجراي الگوريتم مونت کارلوي بهبود يافته صرف نظر کرده و سناريوها بر اساس الگوريتم مونت کارلوي کلاسيک توليد شده اند. جدول 4-20 ابعاد مسائل تصادفي طرح شده به همراه زمان حل و تعداد سناريوهاي توليد شده را نشان ميدهد. لازم به ذکر است زمانهاي بدست آمده کاملاً تحت تأثير مشخصات سيستم کامپيوتري است. اين مشخصات در حل مدل پيشنهادي شماره يک آمده است. همچنين نحوه محاسبه زمان حل با توجه به امکان اجراي همزمان چند مسئله تحت سناريوهاي مختلف (بدليل ابعاد کوچک زير مسئله ها) ميتواند متفاوت گزارش شود. در اين تحقيق مدت زماني که از زمان اقدام به حل مسئله تا بدست آوردن جواب نهايي صرف شده، مبناي محاسبه زمان حل قرار گرفته و اگر قرار باشد تنها بر اساس زمان صرف شده پردازشگر محاسبه شود زمان گزارش شده به مراتب کمتر و در حدود يک ساعت و نيم خواهد بود.
جدول ‏‏4-20- مقايسه عملکرد الگوريتم پيشنهادي با تعداد سناريوهاي مختلف
شماره مسئله
اطلاعات مسئله

50 سناريو

100 سناريو

No. of j/c

CPU Time (min)
RG%

CPU Time (min)
RG%
1
12/20

170
1.253

170
1.358
2
20/25

180
1.668

180
1.681
3
25/30

200
2.446

230
2.588
4
25/35

210
2.477

240
2.356
5
30/40

250
2.302

250
3.01
شماره مسئله
اطلاعات مسئله

200 سناريو

300 سناريو

No. of j/c

CPU Time (min)
RG%

CPU Time (min)
RG%
1
12/20

180
1.392

200
1.501
2
20/25

200
1.382

210
1.661
3
25/30

240
2.508

270
2.446
4
25/35

270
2.21

280
2.477
5
30/40

290
2.788

320
2.302
براي ارزيابي عملکرد الگوريتم، اختلاف نسبي (RG239) بين بهترين مقدار تابع هدف اول در مجموعه جواب پارتو (AB) (که از الگوريتم پيشنهادي بدست آمده است ) از حد پائين تابع هدف اول (که با استفاده از روش Lp-metrics مدل شده و با استفاده از نرم افزار لينگو 12 حل شده است) گزارش شده است. لازم به ذکر است، به دليل بالا بودن تعداد سناريوها، نرم افزار لينگو زمان زيادي را براي توليد مسئله240 صرف مينمايد و پس از گذشت زمان نسبتاً طولاني اولين حد پائين مسئله را گزارش ميدهد (دقت شود در پنجره وضعيت241 در اين نرم افزار، گزينه حد تابع242، بصورت پيوسته بهترين جواب نشدني مسئله دوگان را گزارش ميدهد). که در اين مقايسه اولين حد پائين گزارش شده در نرم افزار از طريق فرمول زير، مبناي مقايسه قرار گرفته است.
(‏4-19)

4-6- روش حل پيشنهادي مدل 3
از آنجا که مدل پيشنهادي سوم، توسعه مدل پيشنهادي دوم از يک زنجيره تأمين دو سطحي به زنجيره تأمين سه سطحي بود. و توابع هدف مدلهاي اول و دوم در اين مدل لحاظ شده است. ميتوان گفت اين مدل در مقايسه با مدلهاي قبلي هم از نظر ابعاد بزرگتر و هم از نظر حل پيچيده تر است. از اين رو نياز به يک روش فرا ابتکاري که بتواند بر چالشهاي پيش روي دو بحث اصلي تحقيق که همانا چند هدفه بودن و نيز تصادفي بودن مدل است فائق آيد. در ادامه يک روش پيشنهادي فرا ابتکاري مبتني بر الگوريتم ژنتيک243 و اپسيلون-محدوديت توسعه يافته است و براي حل مدل پيشنهادي بکار گرفته شده است. نتايج بدست آمده کارايي الگوريتم فوق را بخوبي نشان ميدهد.
الگوريتم پيشنهادي داراي يک چارچوب کلي مبتني بر روش اپسيلون-محدوديت است و براي توليد مجموعه جوابهاي پارتويي توسعه يافته است. در درون اين الگوريتم، يک الگوريتم فرا ابتکاري توسعه يافته ژنتيک تعبيه شده است. در حقيقت در هر تکرار از الگوريتم اپسيلون-محدوديت الگوريتم ژنتيک فراخواني شده و براي حل مسئله برنامهريزي تصادفي تک هدفه عمل مينمايد. نحوه عملکرد الگوريتم پيشنهادي در ادامه خواهد آمد.
4-6-1- روش اپسيلون-محدوديت ارتقاء يافته
روش اپسيلون-محدوديت ارتقاء يافته در بخش قبلي نيز به عنوان تکنيک مواجهه با مسائل چند هدفه مورد استفاده قرار گرفت و در بخش (4-4-1) به طور کامل تشريح شده است.
4-6-2- الگوريتم ژنتيک
برازندهترينها زنده ميمانند244. اين همان فرضية تکامل و وراثت است که الگوريتم ژنتيک با الهام از آن شکل گرفته است. اين الگوريتم که از الگوريتمهاي جستجوي تصادفي تلقي ميشود داراي اين مزيت است که بجاي اينکه از يک نقطه اوليه شروع به جستجو نمايد، يک جمعيت از نقاط فضاي جستجو را به عنوان جمعيت اوليه براي شروع در نظر ميگيرد و با عملگرهاي ژنتيکي سعي در بهبود نسلهاي بعدي دارد. در سادهترين ويرايشهاي اين الگوريتم، يک جمعيت محدود از کروموزومهاي245 با طول ثابت متشکل از ژنها246، پردازش ميشوند. دو عملگر اصلي الگوريتم عبارتند از جابجايي247 و جهش248، عملگر جابجايي با تلفيق ژنهاي دو کروموزوم سعي در بازديد از نقاط مختلف منطقه موجه را داشته و عملگر جهش با تغيير جزئي در يک کروموزوم منتخب، سعي در دور کردن روند جستجو از بهينههاي محلي را دارد. کارايي الگوريتم به استفاده ترکيبي از اين دو عملگر مربوط ميشود.
در تحقيق حاضر براي حل مسئله برنامهريزي تصادفي دو مرحله اي از يک الگوريتم ژنتيک توسعه يافته بهره گرفته شده است. براي تشريح الگوريتم پيشنهادي شش ويژگي مهم اين الگوريتم به صورت زير تشريح ميگردد.
4-6-2-1- ساختار کرموزوم (نحوه کد کردن جواب)249
ساختار کروموزوم و يا جواب شدني مدل پيشنهادي سوم از دو قسمت مجزا تشکيل يافته ولي اين دو قسمت با همديگر در ارتباط بوده و شدني بودن يکي شدني بودن ديگري را تحت تأثير قرار ميدهد.
* ژنهاي مرتبط با متغيرهاي مرحله اول (A)
* ژنهاي مرتبط با متغيرهاي مرحله دوم (B)
ژنهاي مرتبط با متغيرهاي مرحله اول (A)
اين قسمت از کروموزوم همان طور که از اسم آن مشخص است به متغيرهاي مرحله اول که به متغيرهاي طراحي نيز معروف هستند، مرتبط است. تصميم گيري در مورد اين متغيرها بايستي قبل از مشخص شدن مقادير واقعي پارامترهاي غيرقطعي صورت پذيرد و خود به دو دسته زير تقسيم ميگردد:
قسمت A-1
اين زير قسمت از کروموزوم جهت نمايش متغيرهاي توليدي برنامه طراحي شده است و شامل چهار ژن (Xijgt, XPmjt, XSsmjt, XMijt) به قرار زير است:

که در آن T تعداد دوره هاست. XM وXP ماتريسهاي پيوسته اي هستند که به ترتيب سطح موجودي مواد اوليه m و محصول نهائي i را در کارخانه j و در دوره t مشخص مينمايند. هر عنصر يا درايه از اين ماتريس ها با ظرفيت انبارش مربوط به خود محدود ميگردند. Xژني است که تعداد محصولات نوع i توليد شده در کارخانه j را نشان ميدهد و از G ماتريس پيوسته به فرم تشکيل شده که در آن i، j و g به تريب انديسهاي مربوط به محصول، کارخانه و روش توليد ميباشد. هر درايه از اين ماتريس با زمان در دسترس در اوقات عادي (g=1)، اضافه کاري (g=2) و ظرفيت پيمانکاري (g=3) محدود ميگردد.
نهايتاً، ماتريس XS ژني است که نشاندهنده تعداد اقلام ماده اوليه m است که توسط تأمين کننده sبه کارخانه j ارسال ميگردد و خود از M ماتريس به فرم تشکيل شده است و در آن m (1, 2, …, M)انديس مواد اوليه و s (1, 2, …, S) انديس تأمين کنندگان است. هر درايه از اين ماتريس با ظرفيت تأمين کننده محدود ميشود.

همانطور که در شکل 4-12 مشخص است ژنهاي X و XS ماتريسهاي سه بعدي و ژنهاي XM و XP ماتريسهاي دو بعدي هستند. توجه شود که ماتريسهاي Xijgt و XPijt داراي دو انديس مشترک i و j هستند و مطابق شکل 4-12 طوري در کنار يکديگر قرار گرفته اند که انديسهاي مشترک بر يکديگر منطبق شوند. بهمين ترتيب ژنهاي XSsmjt و XMmjt داراي دو انديس مشترک m و i هستند و طوري کنار هم قرار داده شده اند تا انديسهاي مشترک بر هم منطبق گردند.

شکل ‏4-12- قسمت A-1 از کروموزوم پيشنهادي
قسمت A-2
اين زير قسمت از کروموزوم به منظور نمايش متغيرهاي مرتبط با نيروي کار از برنامهريزي توليد طراحي شده اند و شامل چهار ژن (XLkjt, XFkjt, XHkjt , XUkk’jt) به قرار زير است:

که در آن T تعداد دوره ها است. XL، XF، XH و XU ماتريسهاي صحيحي هستند و به ترتيب نشاندهنده تعداد کارکنان با سطح تخصص k موجود، استخدام شده، اخراج شده و يا آموزش ديده براي ارتقاء به سطوح بالاتر تخصصي در کارخانه j و در دوره t هستند. مقادير ماتريس XU زمان در دسترس اوقات عادي و اضافه کاري را تنظيم مينمايد. اين ماتريس ها داراي انديسهاي مشترک k و j هستند و مطابق شکل 4-13 طوري در کنار يکديگر قرار گرفته اند تا انديسهاي مشترک بر هم منطبق گردند.

شکل ‏4-13- قسمت A-2 از کروموزوم پيشنهادي
ژنهاي مرتبط با متغيرهاي مرحله دوم (B)
اين قسمت از کروموزوم همانطور که از نام آن مشخص است با متغيرهاي مرحله دوم مرتبط است که متغيرهاي کنترلي ناميده ميشوند و براي مواجهه با مقادير واقعي پارامترهاي غير قطعي در نظر گرفته شده اند. و در واقع اين متغيرها انحرافات ناشي از عدم انطباق متغيرهاي مرحله اول و مقادير مشخص شده پارامترها و سناريوهاي غير قطعي را اصلاح ميکنند. و در مورد چگونگي تصميم گيري مديريت در مواجهه با وقوع سناريوهاي مختلف تعيين تکليف مينمايند و از اين رو به آن ها متغيرهاي ريکورس/ارجاع250 گفته ميشود. اين متغيرهاي “منتظر شو و ببين251” خود شامل سه ژن (XInict, YSnijct, Bnict) به قرار زير هستند.

که در آن n (1, 2, …, N) انديس سناريو است. XI سطح موجودي محصول نهائي i در نقطه مشتري c و YS تعداد کالاي نوع i است که توسط کارخانه j به نقطه مشتري c ارسال ميگردد. و B کمبود محصول نوع i در نقطه مشتري c در دوره t و تحت سناريوي n ميباشد. طبق شکل 4-14، XI و B ماتريسهاي دو بعدي و YS ماتريس سه بعدي است. اين ماتريس ها داراي انديسهاي مشترک iو c هستند و طوري کنار يکديگر قرار گرفته اند که انديسهاي مشترک آن ها بر يکديگر منطبق گردند.

شکل ‏4-14- قسمت B از کروموزوم پيشنهادي

در نهايت ساختار کلي سه بعدي (3D) کروموزوم پيشنهادي در شکل 4-15 نشان داده شده است. همانطور که در شکل 4-15 مشخص است همه قسمتهاي کروموزوم طوري در کنار يکديگر قرار گرفته اند که انديسهاي مشترک بر هم منطبق شده اند.

شکل ‏4-15- ساختار کلي کروموزوم پيشنهادي
با توجه به ساختار سه بعدي کروموزوم پيشنهادي عملگرهاي سنتي جهش و جابجايي بايستي براي مواجهه با اين کروموزوم به حالت سه بعدي توسعه يابند. به عبارت ديگر بايستي عملگرها را طوري بهبود دهيم تا قابليت کاربردپذيري در سه محور اصلي طول، عرض و ارتفاع را داشته باشند که در ادامه شرح آن خواهد آمد.
4-6-2-2- جمعيت اوليه
يک استراتژي تناوبي براي بدست آوردن جواب شدني اوليه استفاده ميشود. در قدم اول ژن X از کروموزوم به صورت تصادفي بر اساس محدوديتهاي منابع و اميد رياضي تقاضا توليد ميشود. سپس قسمتهاي ديگر XS، XM و XP از کروموزوم بصورت تصادفي پُر ميشوند. سپس با توجه به الگوي بدست آمده تعداد مورد نياز از کارکنان بخشهاي توليدي براي هر سطح تخصص محاسبه ميگردد. پس از آن، کروموزوم دوم به صورت تصادفي توليد ميشود تا محدوديت ها و نيازمنديهاي مدل را به ازاي هر سناريو ارضاء نمايد. توجه شود که کروموزوم ها در صورت نياز در هر يک از قدمهاي فوق الذکر تعديل ميشوند. براي جلوگيري از توليد کروموزومهاي مشابه در هر نسل، هر کروموزوم با ساير کروموزومهاي موجود در استخر252 مقايسه ميگردد.
4-6-2-3- تابع برازندگي253
ارزيابي برازندگي در الگوريتم ژنتيک معمولاً بر اساس مقدار تابع هدف مسئله صورت ميگيرد. همانطور که قبلاً اشاره شد، در الگوريتم پيشنهادي، چارچوب اصلي اپسيلون-محدوديت بکار گرفته شده است و طبق توضيحات مربوطه، در اين الگوريتم يکي از توابع به عنوان تابع هدف اصلي در نظر گرفته شده و مابقي توابع به عنوان محدوديت وارد مدل ميگردند. بنابراين در الگوريتم ژنتيک پيشنهادي تابع هدف اول مدل پيشنهادي سوم که مجموع وزني اميد رياضي و تغييرپذيري هزينههاي کل سيستم توليدي است به عنوان تابع برازندگي در نظر گرفته ميشود.
4-6-2-4- استراتژي انتخاب254
در الگوريتم ژنتيک پيشنهادي دو استراتژي براي انتخاب استفاده شده است. در استراتژي اول بهترين

پایان نامه
Previous Entries منابع پایان نامه ارشد با موضوع قانون کار، سابقه خدمت Next Entries پایان نامه با واژگان کلیدی حقوق و دستمزد