وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

پایان نامه

مقطع کارشناسی ارشد

رشته: مهندسی صنایع- صنایع

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

استاد راهنما:

دکتر جواد رضائیان

استاد مشاور:

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

زمستان 1391

چکیده :

امروزه با بکارگیری موفقیت آمیز مفهوم تولید به موقع در مفاهیمی چون مدیریت تولید و انبار داری نیاز به تکمیل پردازش کارها در موعد تحویل آن ها یک امر کلیدی در محیطهای صنعتی محسوب می شود.به بیان دیگر تکمیل کارها پیش از موعد تحویل به همان اندازه که دیرکرد در تکمیل آنها اهمیت دارد در کانون توجه قرار میگیرد.زمانبندی ماشینهای موازی نامرتبط حالت عمومی مسائل کلاسیک ماشینهای موازی به شمار می آید.در برخی از کاربردهای زمانبندی ماشینهای موازی نامرتبط ماشینها دارای سطح تکنولوژیکی متفاوتی هستندو لزما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نمی باشد و در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشین ها به وقوع      می پیوندد. تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیکهای مدیریت تولید نو ظهور نظیر تولید به موقع، تکنولوژی گروهی و تولید سلولی مورد استفاده قرار می گیرد.

در این تحقیق مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن محدودیت های زمان نصب وابسته به توالی پرداژش کارها و دسترسی محدود به ماشینها و کارها با هدف کمینه سازی زمانهای دیرکرد و زودکرد وزنی کل بررسی میشود.یک مدل برنامه ریزی عدد صحیح برای این مسئله پیشنهادمی شود.همچنین یک روش ترکیبی فرا ابتکاری متشکل از الگوریتم ژنتیک و اگوریتم حرکت جمعی پرندگان برای حل آن ارائه گردیده است.

فصل 1-کلیات و بیان مسأله…………………………………………………………………………..22-1

1-1- مقدمه…………………………………………………………………………………………………………………………2

1-6- تعریف مسأله زمانبندی مربوط به تحقیق………………………………………………………………………..3

1-7- مفروضات مسئله…………………………………………………………………………………………………………5

1-8- ضرورت انجام تحقیق………………………………………………………………………………………………….6

1-9- جمع بندی………………………………………………………………………………………………………………….7

فصل 2- مروری بر ادبیات موضوع…………………………………………………………………45-8

2-1- مقدمه………………………………………………………………………………………………………………………24

2-2- مروری بر رویکرد و اصول سیستم تولیدی JIT……………………………………………………………26

2-3- توالی ماشین های موازی با معیار دیر کرد…………………………………………………………………….28

2-3-1- حداقل کل دیر کرد……………………………………………………………………………………………..28

2-3-2- حداقل کل دیر کرد وزنی…………………………………………………………………………………….32

2-4- توالی ماشین های موازی با معیارهای زود کرد و دیر کرد……………………………………………….34

2-4-1- مسائل با تمرکز بر زمان آماده سازی بین کارها……………………………………………………….35

2-4-2- مسائل با تمرکز بر موعد تحویل یکسان برای کارها…………………………………………………39

2-4-2-1- موعد تحویل معلوم………………………………………………………………………………………39

2-4-2-2- موعد تحویل نامعلوم…………………………………………………………………………………….44

2-5 دسترسی محدود به ماشینها …………………………………………………………………………………………..45

2-6 جمع بندی ………………………………………………………………………………………………………………….45

فصل 3- ارائه مدل ریاضی…………………………………………………………………………….58-46

3-1- مقدمه………………………………………………………………………………………………………….47

3-2-تعریف مسئله………………………………………………………………………………………………….47

3-3- فرضیات مسئله……………………………………………………………………………………………….48

3-4- مدل ریاضی پیشنهادی………………………………………………………………………………………49

3-4-1- پارامترهای ورودی…………………………………………………………………………………….49

3-4-2- نمادها، تعاریف، پارامترها و متغیر های تصمیم…………………………………………………….50

3-4-3- مدل ریاضی…………………………………………………………………………………………….51

3-5 –اعتبار سنجی مدل……………………………………………………………………………………………53

3-6 –تئوری پیچیدگی و پیچیدگی مساله مورد نظر……………………………………………………………56

3-6- جمعﺑندی……………………………………………………………………………………………………..58

فصل 4- الگوریتم پیشنهادی نتایج محاسباتی…………………………………………………..110-59

4-1 مقدمه……………………………………………………………………………………………………………………………60

4-2 الگوریتم ژنتیک ……………………………………………………………………………………………………………..62

4-2-1 شمای کلی الگوریتم ژنتیک………………………………………………………………………………………….64

4-3) اجزای الگوریتم ژنتیک…………………………………………………………………………………………………66

    4-3-1) کروموزوم………………………………………………………………………………………………………….66

    4-3-2) جمعیت………………………………………………………………………………………………………………66

    4-3-3) مقدار برازندگی……………………………………………………………………………………………………67

     6-3-4) کدگذاری……………………………………………………………………………………………………………67

     4-3-5) انتخاب……………………………………………………………………………………………………………….68

    4-3-6) عملگر تقاطعی……………………………………………………………………………………………………..76

    4-3-7) جهش………………………………………………………………………………………………………………….82

    4-3-8) جابه‌جایی…………………………………………………………………………………………………………….83

    4-3-8) قاعده توقف………………………………………………………………………………………………………..83

4-3 الگوریتم حرکت جمعی پرندگان ……………………………………………………………………………………..84

4-4 حرکت دسته جمعی ذرات ………………………………………………………………………………………………86

4-5 مفاهیم پایه الگوریتم…………………………………………………………………………………………………………88

4-6 رابطه بروز رسانی سرعت…………………………………………………………………………………………………..88

4-7 رابطه بروز رسانی موقعیت………………………………………………………………………………………………….92

4-8 گامهای الگوریتم……………………………………………………………………………………………………………..93

4-9 شبه کد الگوریتم……………………………………………………………………………………………………………….93

4-10)طراحی الگوریتم پیشنهادی………………………………………………………………………………………………94

4-10) تنطیمات پارامترها و شرایط اجرای الگوریتم ها……………………………………………………………………99

4‐11) ساختار مسائل…………………………………………………………………………………………………………………99

4‐12)مسائل با ابعاد کوچک و متوسط…………………………………………………………………………………………100

4-13) نتایج آزمایشات……………………………………………………………………………………………………………..100

4-14 مسائل با ابعاد بزرگ…………………………………………………………………………………………………………107

4-15 جمع بندی………………………………………………………………………………………………………………………109

فصل5- نتیجه گیری و پیشنهادات آتی……………………………………………………………..113-110

5-1) نتیجه گیری……………………………………………………………………………………………………………………..111

5-2) پیشنهادات آتی ………………………………………………………………………………………………………………..113

منابع……………………………………………………………………………………………………………………………………….115

فهرست جداول

جدول 1-1- تعدادی از معیارهای کارایی زمان بندی………………………………………………………………..4

جدول 3-1.موعد تحویل و وزنهای زود کرد و دیرکرد……………………………………………………………54

جدول 3-2 زمان پردازش کارها ………… ………………………………………………………………………………54

جدول3-3 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..54

جدول3-4 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..55

جدول3-4 زمان آماده سازی کارها روی ماشین 3…………………………………………………………………..55

جدول 3-5- محاسبه تعداد متغیرها و محدودیت ها ………………………………………………………………53

جدول4-1: انتخاب کروموزوم‌ها با استفاده از مدل چرخ رولت………………………………………………..72

جدول4-2: مشکلات ممکن در مدل چرخ رولت…………………………………………………………………..74

جدول4-3 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j2m………………100

جدول4-4 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..101

جدول4-5 زمان آماده سازی کارها روی ماشین 2……………………………………………………………………101

جدول4-6 نتایج مربوط به مسئله 5 کار و 2 ماشین به تفکیک روشها………………………………………101

جدول4-7 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j3m……………….102

جدول 4-8 زمان آماده سازی کارها روی ماشین 1………………………………………………………………….102

جدول 4-9 زمان آماده سازی کارها روی ماشین 2………………………………………………………………….102

جدول 4-10 زمان آماده سازی کارها روی ماشین 3………………………………………………………………..103

جدول 4-11 نتایج مربوط به مسئله 5 کار و 3 ماشین………………………………………………………………103

جدول4-12 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8j2m……………….103

جدول4-13 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..104

جدول4-15 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..105

جدول 4-16 نتایج مسئله 8 کار و 2 ماشین به تفکیک روشها……………………………………………………..105

جدول4-17 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8 کارو3 ماشین …..105

جدول4-18 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..105

جدول4-19 زمان آماده سازی کارها روی ماشین 2 ………………………………………………………………….105

جدول4-20 زمان آماده سازی کارها روی ماشین 3 ………………………………………………………………….105

جدول 4-21 نتایج مسئله 8 کار و 3 ماشین به تفکیک روشها……………………………………………………..106

جدول 4-22 نتایج مسئله 10 کار و 3 ماشین………………………………………………………………………107

جدول 4-23 نتایج مسئله 50 کار و 10 ماشین……………………………………………………………………..108

جدول 4-24 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..108

جدول 4-25 نتایج مسئله 60 کار و 10 ماشین…………………………………………………………………….108

جدول 4-26 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..109

فهرست اشکال:

شکل4-1: چرخ رولت………………………………………………………………………………………………………..70

شکل4-2: نمونه‌ای از انتخاب در چرخ رولت…………………………………………………………………………71

شکل4-3: نمونه‌ای از عملگر تقاطع تک نقطه‌ای……………………………………………………………………..77

شکل4-4: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه 0-1………………………………………………..79

شکل4-5: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ترتیبی………………………………………………79

شکل4-6: نمونه‌ای از عملگر تقاطع یکنواخت………………………………………………………………………..81

شکل4-7 : ساختار کروموزوم……………………………………………………………………………………………….95

شکل 4-8 : نحوه عملکرد عملگر تقاطع…………………………………………………………………………………97

شکل 4-9: نحوه عملکرد عملگر جهش………………………………………………………………………………….

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