پایان نامه ها و مقالات

تحقیق رایگان درمورد زمان بندی، ارزیابی کیفی، معیارهای ارزیابی، ارزیابی عملکرد

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

دوالگوریتم پیشنهادی
Test number
Problem size
N M size
درصدتغییرات
Cpu time
درصدتغییرات
Nons
درصدتغییرات
Domain
درصدتغییرات
Quality
1
4 2 S
-99.8
0
0
0
2
4 3 S
-93.8
0
0
0
3
5 2 S
– 97.6
0
0
0
4
5 3 S
-99.4
0
0
0
5
6 2 S
-97.9
0
0
0
6
6 3 S
-99.5
0
0
0
7
7 2 S
-98.6
0
0
0
8
7 3 S
-98.5
50
50
-80
9
8 2 M
-99.2
200
Inf
-100
10
8 3 M
-99
-25
-39
-28
11
10 2 M
-95.6
500
Inf
-100
12
10 3 M
-100
Inf
Inf
Inf
13
15 3 M
-100
Inf
Inf
Inf
14
20 3 M
-100
Inf
Inf
Inf
15
30 3 M
-100
Inf
Inf
Inf
16
50 5 L
-100
Inf
Inf
Inf
17
70 5 L
-100
Inf
Inf
Inf
18
100 5 L
-100
Inf
Inf
Inf

در این مقایسه مبنای مقایسه الگوریتم اپسیلون محدودیت پیشنهادی است. یعنی عددمنفی نشان دهنده ی کوچکتر بودن الگوریتم NSGAII پیشنهادی در آن شاخص نسبت به الگوریتم اپسیلون محدودیت است و عدد مثبت عکس آن میباشد. که فرمول محاسبه درصد تغییرات هرشاخص از دو الگوریتم بصورت زیر است:
(NSGAII الگوریتم از نظر مد شاخص-محدویت اپسیلون الگوریتم از نظر مد شاخص)/(محدودیت اپسیلون الگوریتم از نظر مد شاخص)*100

نتایج جدول4-5 نشان میدهد که زمان محاسباتی الگوریتم NSGAIIپیشنهادی در تمامی مسایل نمونه نسبت به روش اپسیلون محدودیت از کاهش چشمگیری برخورداراست. که در نمودار4-2 درصد تغییرات این شاخص برای تمامی مسائل نمونه گزارش میشود:

نمودار4-2: درصد تغییرات زمان محاسباتی
درضمن در اکثر مسائل نمونه تعداد نقاط واقع بر لبه ی پارتوبدست آمده از روش NSGAII بیشتر یامساوی روش اپسیلون محدودیت است به جز مثال شماره10 که در نمودار4-3 درصدتغییرات این شاخص برای تمامی مسائل نمونه گزارش شده است:

نمودار4-3: درصد تغییرات تعداد نقاط نامغلوب
ازنظر شاخص پراکندگی دامنه ی حلهاالگوریتم NSGAII در اکثر مسائل نمونه مقداری برابر یا بزرگترازروش اپسیلون محدودیت داشته است بجز مسئله شماره 10 که مقایسه ی این شاخص از دو الگوریتم در نمودار4-4 واضح است:

نمودار4-4: درصد تغییرات پراکندگی حل ها
با توجه به نمودار4-5 درصد تغییرات برای شاخص کیفیت جوابهای بدست آمده از دو روش پیشنهادی نشان دهنده ی سه نکته ی اساسی است:
۱-برای مسائل نمونه در سایز کوچک جوابهای بدست آمده از روش NSGAII عینا” شبیه جوابهای دقیق حاصل از روش اپسیلون محدودیت میباشد. یعنی شاخص ارزیابی کیفیت حل برای هر دو الگوریتم برابر است با0.5
۲-برای مسائل در ابعاد متوسط تا حدودی از کیفیت حل الگوریتم NSGAII نسبت به روش دقیق اپسیلون محدودیت کاسته میشود. بعبارت دیگر با توجه به تقریبی بودن الگوریتم NSGAII طبیعی است که کیفیت حل بدست آمده ازآن کمترازروشهای دقیق شمارشی چون:اپسیلون محدودیت و..باشد.
۳-برای مسائل درابعادبزرگ ازآنجایی که عملا”روش اپسیلون محدودیت در زمان معقول به جوابی نمی رسد از اینرو جوابهای حاصل از روش NSGAII 100% از کیفیت قابل قبولی برای تصمیم گیرنده برخوردارند.

جدول4-6 یک مقایسه کلی از کیفیت حلهای بدست آمده از هر دو روش را برای مسائل در ابعاد مختلف نشان میدهد که هرچه این شاخص Q به یک نزدیکتر باشد کیفیت حل بالاتری را تضمین میکند:
جدول4-6:مقایسه کیفی حلهای نامغلوب

ε-constraint
NSGAII
S
Q=0.5
Q=0.5
M
Q=0.5
Q=0.5
L
Q=0
Q=1

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

فصل پنجم

نتیجه گیری و

پیشنهادات آتی

5-1.نتیجه گیری
در فصل های اول و دوم این پایان نامه مروری بر کلیات تحقیق وادبیات موضوع انجام شد.در فصل سوم به تعریف مسئله مدنظر و مدل
ریاضی دوهدفه برای مسئله پرداخته شد و در ادامه این فصل ساختار الگوریتم فراابتکاری NSGAII برای برای مسئله بطور مفصل تشریح شد.
در فصل چهارم این تحقیق ابتدا رویکرد اپسیلون محدودیت را برای حل دقیق مسائل کوچک بیان نمودیم سپس به تعریف شاخصهای ارزیابی عملکرد الگوریتمهای پیشنهادی پرداختیم و در آخر این فصل به مقایسه و تجزیه و تحلیل نتایج بدست آمده از حل مسائل نمونه توسط الگوریتمهای پیشنهادی اشاره داشتیم, و در فصل جاری به نتیجه گیری و همچنین پیشنهاداتی برای تحقیقات آتی خواهیم پرداخت.
در این پایان نامه برای دستیابی به مرز بهینه پارتو برای مسئله دوهدفه تعریف شده از الگوریتم دقیق اپسیلون محدودیت و الگوریتم فراابتکاری NSGAII استفاده شده است.
مشخصه اصلی این تحقیق اولا” در نظر گیری چندین محدودیت بطور همزمان در زمینه زمان بندی سیستم های تک ماشینه با قابلیت پردازش دسته ای و نزدیک کردن این مسئله تا جای ممکن به دنیای واقعی , و ثانیا” بررسی دوهدفه این مسئله بوده است از آنجایی که این مسئله در کلاس مسائل NP-Hard قرار دارد لذا در ابعاد بزرگ توسط روشهای دقیق شمارشی مثل اپسیلون محدودیت قابل حل نخواهد بود از اینرو برآن شدیم تا از یک الگوریتم فراابتکاری با ساختار NSGAII استفاده کنیم.
برای بررسی و مقایسه بهتر عملکرد الگوریتم های پیشنهادی سه دسته مسائل نمونه در ابعاد کوچک- متوسط- بزرگ را طراحی نمودیم و برای هر دسته از مسائل با توجه به طراحی آزمایشات مختلف, بصورت تجربی به تنظیم پارامترهای الگوریتم NSGAII پرداختیم.
در تجزیه و تحلیل عملکرد الگوریتمهای پیشنهادی با توجه به معیارهای ارزیابی , حلهایی بهینه یا نزدیک به مرز بهینه را در زمان محاسباتی معقول از الگوریتم NSGAII مشاهده نمودیم.یا به عبارت دیگر میتوان بعنوان نتیجه بیان کرد که الگوریتم فراابتکاری پیشنهاد شده از نظر زمان محاسباتی در تمامی ابعاد مسئله کاراتر از الگوریتم اپسیلون محدودیت است و در اکثر موارد الگوریتم فراابتکاری از اپسیلون محدودیت از نظر شاخص تعداد نقاط لبه نامغلوب و پراکندگی حلها کاراتر است ولی از بعد کیفی الگوریتم فراابتکاری در سایز کوچک و متوسط مسائل بواسطه تقریبی بودن آن کارایی کمتر از اپسیلون محدودیت دارد ولی در مسائل بزرگ از آنجایی که الگوریتم اپسیلون محدودیت ناتوان از حل مسئله است جوابهای الگوریتم فراابتکاری برای تصمیم گیرنده کاراست.
5-2.پیشنهادات
بطور کلی پیشنهادات برای تحقیقات آتی را میتوان از چند جنبه مورد تحلیل و بررسی قرار داد:
1-بهبود الگوریتم
جهت بهبود در کیفیت و تنوع جوابهای پارتو و زمان محاسباتی الگوریتم پیشنهادی میتوان با بکارگیری یک الگوریتم جستجوی محلی عملکرد الگوریتم NSGAII پیشنهادی را تا حد مطلوبی افزایش داد یا اینکه با تغییر در اپراتورهای الگوریتم کارایی بهتر آن را تضمین کنیم.
۲-توسعه الگوریتم پیشنهادی برای سایر مسائل زمان بندی پردازش دسته ای
از آنجایی که الگوریتم پیشنهادی طبق معیارهای ارزیابی از عملکرد قابل قبولی برخوردار بوده لذا میتوان از این الگوریتم برای بهینه سازی سایر مسائل چندهدفه در زمینه پردازش دسته ای و یا سایر محیط های کارگاهی(جریان کارگاهی- ماشین های موازی و…)استفاده کرد.
۳-استفاده از الگوریتم های ابتکاری
برای ایجاد جمعیت اولیه در الگوریتم فراابتکاری پیشنهادی میتوان با بکارگیری الگوریتمهای ابتکاری دیگر, جمعیت اولیه بهتری را ایجاد کرد که باعث بهبود عملکرد الگوریتم خواهد شد.
۴-حذف برخی از فرضهای ساده ساز
۱- در نظرگیری پارامترهای احتمالی یا فازی بجای داده های قطعی مسئله.
۲-در نظرگیری احتمال خرابی برای ماشین.
۳-توسعه این مدل به سایر سیستم های:جریان کارگاهی-ماشین های موازی و…

این مطلب مشابه را هم بخوانید :   سلسله مراتب، تلاش مضاعف

فهرست

منابع و مراجع

[1]Rui Xu , HuapingChen و XuepingLi, ‘’Makespan minimization on single batch-processing machine via ant colony optimization’’ Computers & Operations Research2012

[2]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 – 164

[3]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–96

[4]Gur Mosheiov , Daniel Oron ‘’A single machine batch scheduling problemwith bounded batch size’’ European Journal of Operational Research 187 (2008) 1069–1079

[5]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

[6]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–1730

[7]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–922

[8]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–147

[9]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–891

[10]Lionel Dupont, Clarisse Dhaenens-Flipo’’ Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure’’ Computers & Operat
ions Research 29 (2002) 807}819

[11]Purushothaman Damodaran, Krishnaswami Srihari, Sarah S. Lam’’ Scheduling a capacitated batch-processing machine to minimize makespa’’ Robotics and Computer-Integrated Manufacturing 23 (2007) 208–216

[12]Bayi Cheng, Kai Li, Bo Chen’’ Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization’’ Journal of Manufacturing Systems 29 (2010) 29–34

[13]L.F. Lu, J.J. Yuan ‘’ The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard’’ European Journal of Operational Research 177 (2007) 1302–1309

[14]Cheng-Shuo Wang_, Reha Uzsoy’’ A genetic algorithm to minimize maximum lateness on a batch processing machine’’ Computers &Operations Research 29 (2002) 1621}1640

[15]Jay B. Ghosh , Jatinder N.D. Gupta’’ Batch scheduling to minimize maximum lateness’’ Operations Research Letters 21 (1997) 77 80

[16]Erdal Erel , Jay B. Ghosh ‘’ Batch scheduling to minimize the weighted number of tardy jobs’’ Computers & Industrial Engineering 53 (2007) 394–400

[17]L.L. Liu, C.T. Ng, T.C.E. Chen’’ Bicriterion scheduling with equal processing times on a batch processing machine’’ Computers & Operations Research 36 (2009) 110 – 118

[18]Fariborz’’ Minimizing number of tardy jobs on a batch processing machine with incompatible job families’’ European Journal of Operational Research 162 (2005) 184–19

[19]Imelda . Perez, John W. Fowler, W. Matthew Carlyle’’ Minimizing total weighted tardiness on a single batch process machine with incompatible job families’’ Computers & Operations Research 32 (2005) 327–341

[20]M.T. Yazdani Sabouni, F. Jolai’’ Optimal methods for batch processing

Leave a Reply