عنوان پایان‌نامه
ارایه یک الگوریتم فرا ابتکاری برای حل مساله زمانبندی کارگاه باز چن پردازنده
- رشته تحصیلی
- مهندسی صنایع
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 51805;کتابخانه پردیس 2 فنی شماره ثبت: 2078
- تاریخ دفاع
- ۲۵ بهمن ۱۳۹۰
- دانشجو
- سیدمرتضی گلدانساز
- استاد راهنما
- فریبرز جولای
- چکیده
- در این گزارش مطالعه مسائل زمانبندی کارگاه باز چندپردازنده انجام شده است. در این مسائل فرضیات جدیدی که درنظر گرفته شده است عبارتند از: درنظر گرفتن چند ماشین موازی و یکسان برای هر مرحله تا سرعت تولید افزایش یافته و کارایی آن نیز اضافی گردد. هم‌چنین زمان آماده‌سازی کارها بصورت مستقل و زمان آزادسازی کارها وابسته به توالی عملیات فرض شده‌اند. از طرفی برای کارها هیچ اجباری وجود ندارد که در تمام مراحل پردازش شوند، بریدگی کارها نیز مجاز نمی‌باشد. با درنظر گرفتن چنین فرضیاتی، یک مدل برنامه‌ریزی غیرخطی جهت حداقل کردن زمان تکمیل همه کارها ارائه شد که با یک رویکرد ساده آن را به مدل برنامه‌ریزی خطی تبدیل کردیم. مدل ساخته شده در این قسمت یکی از ساده‌ترین و بهترین مدل‌هایی است که تاکنون در مسائل زمانبندی کارگاه باز چندپردازنده ارائه شده‌اند. پس از ارائه مدل، الگوریتم رقابت استعماری معرفی شده و برای افزایش کارایی آن از بهترین عملگرهای الگوریتم ژنتیک استفاده شده است. هم‌چنین از آنجایی که انتخاب مقدار پارامترهای هر الگوریتم تأثیر زیادی در جواب نهایی حاصله دارد، پارامترهای مربوطه را با استفاده از روش سطوح پاسخ تنظیم کردیم. با توجه به پژوهش‌های گذشته، در این مطالعه مسائل زمانبندی را به سه دسته کوچک، متوسط و بزرگ تقسیم‌بندی کرده و برای هرکدام از آنها مثال‌های عددی طراحی نمودیم. مثال‌های کوچک را با نرم‌افزار GAMS حل کرده و برای آنها جواب بهینه بدست آوردیم. به کمک این نرم‌افزار برای مثال‌های متوسط نیز یک کران پایین محاسبه نمودیم. بعد از آن با استفاده از الگوریتم پیشنهادی، تمام مثال‌ها را حل کرده و نتایج مثال‌های کوچک و متوسط را با مقدار بهینه و کران پایین بدست آمده مقایسه نمودیم. مشاهده می‌شود که برای مثال‌های کوچک، جواب الگوریتم پیشنهادی دقیقا برابر با مقادیر بهینه بوده و در مثال‌های متوسط با انحراف بسیار جزئی و یا حتی بدون اختلاف همراه بوده است. با توجه به این نتایج و نتایجی که از معیارهای سنجش عملکرد الگوریتم پیشنهادی بدست آمد، می‌توان نتیجه گرفت که الگوریتم رقابت استعماری پیشنهادی یک الگوریتم بسیار کارا بوده و دارای سرعتی مناسب برای حل مسائل زمانبندی ارائه شده می‌باشد.
- Abstract
- In this paper, we studied multi-processor open shop (MPOS) scheduling problems. The assumptions such as independent setup time and sequence dependent removal time are considered. Also it is supposed that there is no force for the jobs to be processed in all the stages, amd preemption is not allowed. Then we proposed a MINLP model to minimize total completion time and by suggesting a simple method, we changed the model to a MILP one. This model is simpler and covers more assumptions than the proposed models for the MPOS problems until now. To solve the model, the imperialist competitive algorithm (ICA) is considered. To increase its performance, we used two effective operators of the genetic algorithm (GA) which are crossover and mutation. Moreover the parameters of the hybrid algorithm are tuned with the response surface methodology (RSM). On the other hand, the scheduling problems are classified into three groups based on the previous studies, small, medium and large size problems. For each class, some instances are generated. By coding the model in GAMS, the optimum results for the small size instances and the lower bounds for the medium size instances are calculated. Then the proposed algorithm is used to solve the same instances. The results show that the answers for the small size instances are exactly equal to the optimum results and for the medium ones are very close to the lower bounds. To evaluate the performance of our hybrid algorithm we considered two criterions. The results show that the proposed algorithm has a high performance and produces high quality answers. So it is concluded that the hybrid imperialist competitive algorithm can solve large size instances with high performance.
