شاخص دسته های پردازش k=1,2,3,…,n
پارامترهاواطلاعات مسئله:
تعدادکارهn=
تعداد خانواده های قطعاتm=
ظرفیت ماشینB=
زمان پردازش کارهاPj=
زمان دسترسی کارهاRj=
موعد تحویل کارهاDj=
میزان سفارش هر کارSj=
ماتریس زمان آماده سازی ماشین برای پردازش خانواده های مختلف از کارها.
متغییرهای تصمیم:
= kزمان پردازش دسته
= kزمان شروع پردازش دسته
= kزمان تکمیل پردازش دسته
= jزمان تکمیل پردازش کار
میزان دیرکردازموعدتحویل کار Tj= j
۳-۲-۲٫مفروضات مسئله
۱- ماشین در تمامی زمانها دردسترس است و هیچگونه ازکارافتادگی و تعمیرات ونگهداری برنامه ریزی شده ای مجاز نمیباشد.
۲- تمامی پارامترهای ورودی مسئله قطعی ومعیین هستند.
۳- nکار متعلق به mخانواده ی متفاوت برای پردازش داریم که کارهای متعلق به هر خانواده دارای زمان پردازش یکسانند.
۴- ماشین قابلیت پردازش حداکثر B کار را دریک واحد زمانی داردکه این کارها باید از یک خانواده باشند.
۵- همه ی کارها در زمان صفر دردسترس نیستند.
۶- هر کار دارای یک میزان سفارش دلخواه است که قابلیت تفکیک روی این مقدار را دارد.
۷- هر دسته پس از شروع پردازش باید تا پایان بدون وقفه پردازش شود.
۸- جهت پردازش ازیک دسته به دسته ای که متعلق به خانواده ی دیگر است ماشین نیازمند به زمان آماده سازی خواهدبود.
۳-۲-۳٫مدل ریاضی
توابع هدف و محدودیت های مسئله بصورت زیر میباشند:
(۸-۳)
هدف اول حداقل سازی زمان تکمیل آخرین دسته را نشان میدهد و دومین هدف قصد در حداقل سازی دیرکرد از موعدتحویل کارها را دارد.
محدودیت های شماره۳ تضمین میکند که هر دسته متعلق به حداکثر یک خانواده است.
مجموعه محدودیت های شماره۴ تضمین میکند که مجموع سفارشات کارهای مختلف در یک دسته از ظرفیت ماشین تجاوز نکند.
محدودیت های شماره۵ نشان میدهد که مجموع سفارشات کارjام در دسته های مختلف برابر است با Sj.
محدودیت های شماره۶ نشان میدهد که کار jام حداکثر میتواند در تعداد دسته قرار گیرد.
مجموعه محدودیت های شماره۷ زمان پردازش دسته ی kام را محاسبه میکنند.
مجموعه محدودیت های شماره۸و۹ نشان می دهند که اگر یک کاراز دستهkام متعلق به خانواده iام باشند آنگاه دستهkام فقط متعلق به خانواده iام است و برعکس.
محدودیت های شماره۱۰ نشان میدهد که کار j حداکثر به تعدادSj میتواند در یک دسته قرار گیرد.
مجموعه محدودیت های شماره۱۱ و۱۲ زمان شروع پردازش هردسته را حساب میکند.
محدودیت های شماره۱۳ زمان تکمیل هر دسته را حساب میکند که برابر است با زمان شروع بعلاوه زمان پردازش آن دسته.
محدودیت های شماره۱۴ نشان دهنده زمان تکمیل هرکار است که برابر است با زمان تکمیل آخرین دسته ای که کار مدنظر در آن واقع شده است.
محدودیت های شماره۱۵ حداکثر زمان دیرکرد از موعد تحویل کارها را نشان میدهد.
محدودیت های شماره۱۶ متغییرهای مستقل باینری و عددصحیح را درمدل نشان میدهند.
۳-۲-۴٫اعتبارسنجی[۲۶] مدل
برای بررسی اعتبار مدل پیشنهادی میتوان این مدل را بایکی از کارهای قبلی مقایسه کرد مثلا” در سال۲۰۰۵ [۳] کوه و همکارانش یک مدل ریاضی برای بهینه سازی Cmax برای کارهایی که متعلق به خانواده های مختلف بوده و هر کار دارای اندازه سفارش دلخواه بوده ارائه شده است.اگر بخواهیم این مدل ریاضی را با مدل پیشنهادی در بهینه سازی Cmax اعتبارسنجی کنیم باید محدودیت هایی که در مدل پیشنهادی اضافه شده درحالیکه در مدل قبلی وجود نداشته را طوری اعمال کنیم که عملا” در فضای جستجو غیرفعال شوند.ازجمله این محدودیتها وجود زمان دسترسی دلخواه برای کارها- وجود زمان آماده سازی است که با برابر صفر قرار دادن این پارامترها عملا” از مدل حذف میشوند و یا در مدل پیشنهادی قابلیت تفکیک یک کار روی اندازه سفارش آن کار(Sj) وجود دارد که به جهت غیر فعال این ویژگی از مدل پیشنهادی باید یک محدودیتی بصورت زیر به مدل پیشنهادی اضافه کرد:
یعنی کار jام فقط قابلیت پردازش در یک دسته راخواهد داشت. با اعمال تغییرات فوق در مدل ریاضیاتی پیشنهادی و اجرای آن برای یک مثال مشخص به جوابی میرسیم که مدل قبلی میرسید که این نشان از اعتبار مدل پیشنهادی ما دارد.
در ادامه از آنجایی که با افزایش ابعاد مسئله تعداد جوابهای موجه بصورت نمایی افزایش می یابد در نتیجه دستیابی به جوابهای بهینه نامغلوب برای مسائل بزرگ عملا” ناممکن میشود.ازاینرو در این تحقیق الگوریتم فراابتکاری با ساختار NSGAII را برای مدل پیشنهادی توسعه خواهیم داد.
۳-۳٫ساختار کلی الگوریتم های تکاملی[۲۷]
الگوریتمهای تکاملی یک نوع از الگوریتمهای فراابتکاری اند که از تکامل بیولوژیکی طبیعت الهام گرفته اند که از جمله نمونه بارز آن الگوریتم ژنتیک است.
به هر الگوریتمی که براساس یک جمعیت اولیه اقدام به ایجاد تغییرات و سپس اقدام به ایجاد جمعیت جدید بهتر میکند واژه تکاملی نسبت داده میشود.هر الگوریتم تکاملی مستقل از نوع مسئله بهینه سازی دارای ساختار زیر است:
۱- ایجاد یک جمعیتی از افراد(معمولا”بصورت تصادفی) بعنوان حلهای شدنی و بالقوه ی مسئله.
۲- محاسبه میزان شایستگی هر کدام از افراد جمعیت.
۳- حفظ و ارتقای مطلوبیت جمعیت جدید از طریق:
۳.۱-مکانیسم انتخاب متناسب با میزان شایستگی.
۳.۲-استفاده از اپراتورهای مناسب (تقاطع-جهش) جهت ایجاد نسل جدید.
۴- تکرار گامهای ۲و۳ تا برقراری شرط توقف.
۳-۴٫الگوریتمهای ژنتیک چندهدفه
در طی سالهای ۱۹۹۳ تا ۲۰۰۵ الگوریتم های تکاملی زیادی در ادبیات مسائل چند هدفه پیشنهاد شده است. از جمله این الگوریتمها میتوان به[۵۸]NSGAو [۲۴]NSGAII و [۵۴]SPEAIIو …اشاره کرد که برای جزئیات بیشتر این الگوریتمها میتوان به مراجع مربوطه رجوع کرد.
از آنجایی که در بهینه سازی چندهدفه هدف دستیابی به مجموعه ای از حلهای نامغلوب بهینه است بنابراین دو مشخصه برای الگوریتمهای MOEA در نظر گرفته میشود:
۱- تخصیص برازش به اعضای جمعیت برحسب مرتب کردن غیر مغلوب ها.
۲- حفظ تنوع در جوابهای یک مرز نامغلوب.
گرچه الگوریتمهای تکاملی چندهدفه نامبرده حلهای کارایی را برای اینگونه مسائل بدست میدهد ولی همچنان تلاش محققان بر این است که با معرفی عملگرهای بهتر کارایی اینگونه الگوریتمها را بالاتر ببرند.در این میان بهبود عملگر انتخاب از همه مهمتر می باشد چراکه بهبود این عملگر منجر به همگرایی بهتر MOEA خواهد شد.
در سال ۲۰۰۲ دب وهمکارانش الگوریتمی بنام NSGAII را ارائه دادند که مشکلات الگوریتم قبلی(NSGA) را تا حدودی برطرف کرد.از جمله این مشکلات عبارت بودند از:
۱-پیچیدگی محاسباتی الگوریتم قبلی از()o به()o کاهش یافت.
۲-عدم نخبه گرایی کارا.
۳-رفع نیاز به تعیین پارامتر در فرایند تقسیم.
در این االگوریتم عملگر انتخاب براساس دو معیار:رتبه بندی نامغلوب لبه های پارتو-فاصله ازدحامی محاسبه شده برای هر فرد پایه ریزی میشود.و این الگوریتم در اکثر موارد قادر به دستیابی جوابهایی در مرز پارتوی بهینه با پراکندگی مناسب خواهدبود.ازآنجایی که کارایی تمام الگوریتمهای تکاملی به شدت تحت تاثیر عملگرهای انتخاب و تقاطع و… میباشند در ادامه به جزئیات اپراتورهای این الگوریتم خواهیم پرداخت.
۳-۵٫ساختار الگوریتم فراابتکاری پیشنهادی

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