M

Q>=0.5

Q<=0.5

L

Q=0

Q=1

نمودار۴-۵ درصد تغییرات کیفیت حلهای نامغلوب
۴-۵٫جمع بندی
دراین فصل برای بهینه سازی چندهدفه مسئله مد نظرازالگوریتم دقیق اپسیلون محدودیت وتقریبی NSGAII استفاده شده است. سپس تحت چهار شاخص: تعداد جوابهای لبه ی پارتو- پراکندگی نقاط واقع بر لبه ی پارتو- زمان محاسباتی- کیفیت جوابهای نامغلوب به مقایسه وارزیابی عملکرد الگوریتمهای پیشنهادی پرداختیم. برای ارزیابی کیفیت جوابهای الگوریتمها نسبت به هم به مقایسه دودویی(جفتی)در سطح اطمینان ۰٫۹۵باآزمون t¸ نقاط واقع بر لبه های پارتو میپردازیم و از نتایج بدست آمده نتجه می گیریم که در مسائل با ابعاد کوچک کیفیت جوابها یکسان و برای مسائل متوسط گاها” کیفیت روش اپسیلون محدودیت بهتر خواهد بودو برای مسائل بزرگ با توجه به عدم کارایی روش های دقیق¸ الگوریتم فراابتکاری NSGAII از کیفیت جواب خوبی برخوردار است.
ضمنا” الگوریتم NSGAII درنرم افزار matlab کدنویسی شده و برخلاف الگوریتم اپسیلون محدودیت که در لینگو به چندین بار اجرا نیازمند است¸ با یکبار اجرا به مجموعه جوابهای بهینه پارتو خواهد رسید که این امر موجب کاهش شدید زمان محاسباتی خواهد شد.

فصل پنجم
نتیجه گیری و
پیشنهادات آتی

۵-۱٫نتیجه گیری
در فصل های اول و دوم این پایان نامه مروری بر کلیات تحقیق وادبیات موضوع انجام شد.در فصل سوم به تعریف مسئله مدنظر و مدل ریاضی دوهدفه برای مسئله پرداخته شد و در ادامه این فصل ساختار الگوریتم فراابتکاری NSGAII برای برای مسئله بطور مفصل تشریح شد.
در فصل چهارم این تحقیق ابتدا رویکرد اپسیلون محدودیت را برای حل دقیق مسائل کوچک بیان نمودیم سپس به تعریف شاخصهای ارزیابی عملکرد الگوریتمهای پیشنهادی پرداختیم و در آخر این فصل به مقایسه و تجزیه و تحلیل نتایج بدست آمده از حل مسائل نمونه توسط الگوریتمهای پیشنهادی اشاره داشتیم, و در فصل جاری به نتیجه گیری و همچنین پیشنهاداتی برای تحقیقات آتی خواهیم پرداخت.
در این پایان نامه برای دستیابی به مرز بهینه پارتو برای مسئله دوهدفه تعریف شده از الگوریتم دقیق اپسیلون محدودیت و الگوریتم فراابتکاری NSGAII استفاده شده است.
مشخصه اصلی این تحقیق اولا” در نظر گیری چندین محدودیت بطور همزمان در زمینه زمان بندی سیستم های تک ماشینه با قابلیت پردازش دسته ای و نزدیک کردن این مسئله تا جای ممکن به دنیای واقعی , و ثانیا” بررسی دوهدفه این مسئله بوده است از آنجایی که این مسئله در کلاس مسائل NP-Hard قرار دارد لذا در ابعاد بزرگ توسط روش های دقیق شمارشی مثل اپسیلون محدودیت قابل حل نخواهد بود از اینرو برآن شدیم تا از یک الگوریتم فراابتکاری با ساختار NSGAII استفاده کنیم.
برای بررسی و مقایسه بهتر عملکرد الگوریتم های پیشنهادی سه دسته مسائل نمونه در ابعاد کوچک- متوسط- بزرگ را طراحی نمودیم و برای هر دسته از مسائل با توجه به طراحی آزمایشات مختلف, بصورت تجربی به تنظیم پارامترهای الگوریتم NSGAII پرداختیم.
در تجزیه و تحلیل عملکرد الگوریتمهای پیشنهادی با توجه به معیارهای ارزیابی , حلهایی بهینه یا نزدیک به مرز بهینه را در زمان محاسباتی معقول از الگوریتم NSGAII مشاهده نمودیم.یا به عبارت دیگر میتوان بعنوان نتیجه بیان کرد که الگوریتم فراابتکاری پیشنهاد شده از نظر زمان محاسباتی در تمامی ابعاد مسئله کاراتر از الگوریتم اپسیلون محدودیت است و در اکثر موارد الگوریتم فراابتکاری از اپسیلون محدودیت از نظر شاخص تعداد نقاط لبه نامغلوب و پراکندگی حلها کاراتر است ولی از بعد کیفی الگوریتم فراابتکاری در سایز کوچک و متوسط مسائل بواسطه تقریبی بودن آن کارایی کمتر از اپسیلون محدودیت دارد ولی در مسائل بزرگ از آنجایی که الگوریتم اپسیلون محدودیت ناتوان از حل مسئله است جوابهای الگوریتم فراابتکاری برای تصمیم گیرنده کاراست.
۵-۲٫پیشنهادات
بطور کلی پیشنهادات برای تحقیقات آتی را میتوان از چند جنبه مورد تحلیل و بررسی قرار داد:
۱-بهبود الگوریتم
جهت بهبود در کیفیت و تنوع جوابهای پارتو و زمان محاسباتی الگوریتم پیشنهادی میتوان با بکارگیری یک الگوریتم جستجوی محلی عملکرد الگوریتم NSGAII پیشنهادی را تا حد مطلوبی افزایش داد یا اینکه با تغییر در اپراتورهای الگوریتم کارایی بهتر آن را تضمین کنیم.
۲-توسعه الگوریتم پیشنهادی برای سایر مسائل زمان بندی پردازش دسته ای
از آنجایی که الگوریتم پیشنهادی طبق معیارهای ارزیابی از عملکرد قابل قبولی برخوردار بوده لذا میتوان از این الگوریتم برای بهینه سازی سایر مسائل چندهدفه در زمینه پردازش دسته ای و یا سایر محیط های کارگاهی(جریان کارگاهی- ماشین های موازی و…)استفاده کرد.
۳-استفاده از الگوریتم های ابتکاری
برای ایجاد جمعیت اولیه در الگوریتم فراابتکاری پیشنهادی میتوان با بکارگیری الگوریتمهای ابتکاری دیگر, جمعیت اولیه بهتری را ایجاد کرد که باعث بهبود عملکرد الگوریتم خواهد شد.
۴-حذف برخی از فرضهای ساده ساز
۱- در نظرگیری پارامترهای احتمالی یا فازی بجای داده های قطعی مسئله.
۲-در نظرگیری احتمال خرابی برای ماشین.
۳-توسعه این مدل به سایر سیستم های:جریان کارگاهی-ماشین های موازی و…
فهرست
منابع و مراجع
[۱]Rui Xu , HuapingChen و XuepingLi, ‘’Makespan minimization on single batch-processing machine via ant colony optimization’’ Computers & Operations Research2012
[۲]Shuguang li, Guojun Li, Xiaoli Wang, Qiming Liu,’’ Minimizing makespan on a single batching machine with release times andnon-id entical job sizes’’ Operations Research Letters 33 (2005) 157 – ۱۶۴
[۳]Shie-Gheun Koh, Pyung-Hoi Koo, Dong-Chun Kim, Won-Suk Hur’’ Scheduling a single batch processing machine with arbitrary jobsizes and incompatible jobfamilies’’ Int. J. Production Economics 98 (2005) 81–۹۶
[۴]Gur Mosheiov , Daniel Oron ‘’A single machine batch scheduling problemwith bounded batch size’’ European Journal of Operational Research 187 (2008) 1069–۱۰۷۹
[۵]H.A.J. Crauwels . C.N. Potts b L.N. Van Wassenhove’’ Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs’’ European Journal of Operational Research 90 (1996) 200-213
[۶]N. RafieeParsa,B.Karimi , A.HusseinzadehKashan’’ A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes’’ Computers & Operations Research 37 (2010) 1720–۱۷۳۰
[۷]Ali HusseinzadehKashan , BehroozKarimi , FariborzJolai ‘’ An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes’’ Engineering Applications of Artificial Intelligence 23 (2010) 911–۹۲۲
[۸]SharifMelouk , Purushothaman Damodaran, Ping-Yu Chang’’ Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing’’ Int. J. Production Economics 87 (2004) 141–۱۴۷
[۹]Purushothaman Damodaran, Praveen Kumar Manjeshwar, Krishnaswami Srihari’’ Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms’’ Int. J. Production Economics 103 (2006) 882–۸۹۱
[۱۰]Lionel Dupont, Clarisse Dhaenens-Flipo’’ Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure’’ Computers & Operations Research 29 (2002) 807}819
[۱۱]Purushothaman Damodaran, Krishnaswami Srihari, Sarah S. Lam’’ Scheduling a capacitated batch-processing machine to minimize makespa’’ Robotics and Computer-Integrated Manufacturing 23 (2007) 208–۲۱۶

برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.