منبع پایان نامه ارشد درباره توسط نرم افزار و الگوریتم ژنتیک


Widget not in any sidebars

M3 : P3 , P1
M4 : P5 , P4 , P3
M5 : P4 , P5
مقادیر پارامتر خروجی مربوط به زمان جابجایی بین دو علمیات متوالی هر قطعه و زمان تکمیل کار هر قطعه به شرح زیر میباشد:
T112=1 , T123=4 , T212=1 , T312=1 , T323=4 , T412=4 , T512=4
g(1)=21 , g(2)=9 , g(3)=31 , g(4)=14 , g(5)=19
محل سلولهای تشکیلی و نحوه استقرار ماشینها در هر سلول و دستهبندی قطعه به صورت کلی در شکل 4-1 قابل مشاهده است.
شکل 41. نمایی از تشکیل سلول و چیدمان سلولی مثال حل شده
زمانبندی که با توجه به سلول تشکیلی فوق حاصل خواهد شد را در نمای گانت ارائه شده در شکل 4-2 میتوان مشاهده نمود.
شکل 42. نمای گانت مثال حل شده
همانطوریکه در نمای گانت مشاهده مینماییم تشکیل سلول(استقرار ماشینها) و زمانبندی به نحوی انجام گرفته است که تا جای ممکن زمانهای جابجایی کاهش یافته و زمان بیکاری ماشینها حداقل شده است. در مورد تخصیص قطعهها به سلولها نیز دقت مورد نظر انجام شده است به طور مثال قطعه 4 در سلولی قرار دارد که اولین ماشین مورد نیاز آن برای پردازش در آن سلول قرار دارد یعنی ماشین 5 تا بدین ترتیب از جابجاییهای بیمورد در اتبدای کار پیشگیری شود. در مورد تابع هدف که دارای مقدار 94 است، از حاصل جمع مقادیر 31 ، 21 ، 9 ، 14 و 19 که به ترتیب زمانهای تکمیل کارهای (قطعههای) 3 ، 2 ، 1 ، 4 و 5 هستند به این مقدار خواهیم رسید. لازم به ذکر است مدت زمان حل این مدل در نرم افزار لینگو، 5 دقیقه و 31 ثانیه به طول انجامیده است.
Runtime = 5′ : 31′′ (= 331′′ )
4-3- نتایج محاسباتی و تحلیل آنها
در بخش قبل مثالی را در مقیاس کوچک شرح داده و توسط نرم افزار لینگو حل شد، اما این دست از مدلها که از جمله مسائل NP-hard هستند در مقیاسهای بزرگتر نیاز به زمان بیشتری خواهد داشت به همین منظور ما برای حل این مدل از الگوریتم ژنتیک بهره گرفتهایم تا در زمان منطقی به جواب نسبتا خوبی دست یابیم.
در این بخش در ابتدا یک مقایسه نسبی بین زمان حل در نرم افزار لینگو و روش حل با استفاده از الگوریتم ژنتیک برای چند مثال ارائه مینماییم و سپس مثالهایی به جهت مقایسه چیدمان سلولی مرسوم خطی تک ردیفی و چیدمان پیشنهادی خطی دو ردیفی در مقیاس بزرگتر و پیچیدهتر که توسط الگوریتم ژنتیک پیشنهادی در نرمافزار متلب حل شده است، ارائه کرده و نتایج بدست آمده را مورد بررسی قرار خواهیم داد.
در جدول 4-2 نتایج بدست آمده برای 5 مثال با پارامترها و مقیاسهای متفاوت و زمان حل در نرم افزار لینگو و متلب به همراه مقدار تابع هدف مدل در هر یک ارائه شده است. در ستون دوم این جدول اندازه مساله یعنی تعداد ماشین، قطعه و عملیاتها آورده شده، در سه ستون بعدی محدودیتهای تعریف شده مساله قابل مشاهده است و در دو ستون بعدی مقدار حل در لینگو و زمان رسیدن به جواب در این نرم افزار نوشته شده است. در سه ستون بعدی مربوط به حل ژنتیک به ترتیب در ستون اول مقدار بهترین جواب در بین پنج بار حل مساله با الگوریتم ژنتیک محاسبه شده و سپس مقدار و زمان میانگین این پنج بار حل در ستونهای بعدی ارائه شده است. همانطوریکه مشاهده مینماییم مقادیر بهترین جواب تا حد منطقی به جواب حل دقیق با لینگو نزدیک است و در مقیاسهای بزرگتر مساله ما توسط الگوریتم ژنتیک در زمان بسیار کمتری به حل دقیق نزدیک میشویم.
جدول 41. مقایسه زمانی بین حل با لینگو و حل با الگوریتم GA
Time_ave
(min)
GA_
(Ave sol)
GA_
(Best Sol)
Time