دانشگاه بوعلی سینا

دانشکده مهندسی

   گروه مهندسی صنایع

جلسه دفاع پایان‌نامه کارشناسی ارشد در رشته مهندسی صنایع گرایش صنایع

 

عنوان:

ارائه یک الگوریتم هیبریدی کارا برای مسأله زمان‌بندی خط تولید کارگاهی همراه با یک مرحله مونتاژ

 

استاد:

دکتر پرویز فتاحی

 

اساتید داور:

دکتر جواد بهنامیان

دکتر پروانه سموئی

 

دانشجو:

ساناز کنشلو

 

زمان: دوشنبه  11/11/95 ساعت 13

مکان: کلاس 10

 

چكيده:

در این پایان‌نامه مسأله زمان‌بندی تولید کارگاهی همراه با یک مرحله مونتاژ با هدف حداقل کردن زمان تکمیل محصولات در نظر گرفته شده است. ابتدا مرور ادبیات جامعی بر روی مسأله تولید کارگاهی و مسائل زمان‌بندی تولید دو مرحله‌ای  صورت گرفت. سپس یک مدل برنامه‌ریزی خطی عدد صحیح مختلط ارائه گردید. جهت بررسی صحت عملکرد مدل، چند نمونه مسأله با اندازه کوچک توسط نرم‌افزار گمز حل گردید. برای مسائل با اندازه متوسط نیز حد بالایی توسط آن ارائه شد. با توجه به NP-hard بودن مسأله، برای حل آن در ابعاد بزرگ و متوسط از الگوریتم‌های ترکیبی مبتنی بر الگوریتم‌های ژنتیک، بهینه‌سازی انبوه ذرات، جستجوی فاخته، جستجوی همسایگی متغیر و جستجوی همسایگی متغیر موازی استفاده گردید. هم‌چنین جهت بررسی توانایی الگوریتم‌ها از آزمون آماری و معیارهایی از جمله درصد انحراف نسبی، درصد بهبود در جواب اولیه و انحراف معیار استفاده شد. نتایج محاسباتی نشان دادند که برای مسائل متوسط، الگوریتم‌ ترکیبی بهینه‌سازی انبوه ذرات و جستجوی همسایگی متغیر موازی(HPSOPVNS) و برای مسائل با ابعاد بزرگ نیز الگوریتم‌ ترکیبی ژنتیک و جستجوی همسایگی متغیر موازی(HGAPVNS) عملکرد بهتری دارد. در ادامه به‌منظور بهبود بهترین الگوریتم‌های ارائه شده، راه‌کارهایی از جمله اضافه نمودن ساختارهای همسایگی جدید ارائه و پیاده‌سازی شد. هم‌چنین رفتار الگوریتم‌های ترکیبی بهینه‌سازی انبوه ذرات و جستجوی همسایگی متغیر و متغیر موازی تحت چهار روش از مهم‌ترین روش‌های کدگذاری بررسی شد. علاوه بر این به‌منظور اعتبارسنجی بهترین الگوریتم‌های ارائه شده، از روشی کارا بر پایه الگوریتم ژنتیک و جستجوی ممنوع(HGATS) استفاده شد. نتایج نشان دادند که هر دو الگوریتم HPSOPVNS و HGAPVNS کارایی بالاتری نسبت به الگوریتم HGATS و الگوریتم‌های ژنتیک و بهینه‌سازی انبوه ذرات دارند. در نهایت جهت تشریح یک کاربرد واقعی از مسأله مورد بررسی، دو محصول از کارخانه لوازم خانگی بردنا توسط الگوریتم HPSOPVNS زمان‌بندی شدند. نتایج به‌دست آمده نشان از  بهبود 40 درصدی در زمان‌بندی فعلی کارخانه دارد.

 

واژه­های کلیدی: زمان‌بندی تولید کارگاهی، مونتاژ، الگوریتم ژنتیک، بهینه‌سازی انبوه ذرات، جستجوی فاخته، جستجوی همسایگی متغیر، جستجوی همسایگی متغیر موازی

 

Abstract:

In this paper a jobshop scheduling problem with an assembly stage is considered. The objective function is defined as the makespan minimization. At first a comprehensive study is conducted on jobshop scheduling and the two stage assembly problems. Then a mixed integer linear programming model is presented to describe the problem. In order to confirm the accuracy of the proposed model, some small instances are solved by GAMS. Since the considered problem is known as a NP-hard problem, hybrid metaheuristic algorithms are used to solve the problem in medium to large instances in a reasonable amount of time. The proposed algorithms are based on genetic algorithm, particle swarm optimization, cuckoo search, variable neighborhood search and parallel variable neighborhood search algorithm. Then, in order to the compare the algorithms and verifying their effectiveness, a statistical analysis is used along with some factor like relative percentage deviation and improvement of initial solution. Computational results show that the hybrid particle swarm optimization and parallel variable neighborhood search algorithm (HPSOPVNS) outperforms the other proposed algorithms in case of solving medium instances and the hybrid genetic and parallel variable neighborhood search algorithm (HGAPVNS) performs better than the others for solving large instances. Furthermore, several changes are applied on the best algorithms in order to improve their performance. Also, the behavior of HPSOPVNS and HPSOVNS algorithms has been analyzed under four famous solution representations. On the other hand, the HPSOPVNS and HGAPVNS algorithms, they are compared with an effective hybrid algorithm based on genetic and tabu search (HGATS). Computational results reveal that both HPSOPVNS and HGAPVNS outperform the HGATS, GA and PSO. Finally a case study on an appliance factory is presented. The proposed algorithm yields an improvement of about 40% in makespan over the present system.

Key Words: Jobshop Scheduling , Assembly, Genetic algorithm, Particle swarm optimization, Cuckoo search, Variable neighborhood search, Parallel variable neighborhood search.

 

شرح سوابق شغلی و علمی

 

1-    مشخصات فردی

2-   سوابق تحصیلی

3-  فعالیت­های علمی-پژوهشی

4-   آشنایی با زبانهای خارجی

5-   سوابق کاری

6-   آشنایی با کامپیوتر