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

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

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

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

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

پایان نامه

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

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

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

 

چکیده :

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

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

 

فهرست عنوان ها

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

۱-۱- مقدمه…………………………………………………………………………………………………………………………۲

 

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

۱-۷- مفروضات مسئله…………………………………………………………………………………………………………۵

۱-۸- ضرورت انجام تحقیق………………………………………………………………………………………………….۶

۱-۹- جمع بندی………………………………………………………………………………………………………………….۷

 

فصل ۲- مروری بر ادبیات موضوع…………………………………………………………………۴۵-۸

۲-۱- مقدمه………………………………………………………………………………………………………………………۲۴

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

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

۲-۳-۱- حداقل کل دیر کرد……………………………………………………………………………………………..۲۸

۲-۳-۲- حداقل کل دیر کرد وزنی…………………………………………………………………………………….۳۲

۲-۴- توالی ماشین های موازی با معیارهای زود کرد و دیر کرد……………………………………………….۳۴

۲-۴-۱- مسائل با تمرکز بر زمان آماده سازی بین کارها……………………………………………………….۳۵

۲-۴-۲- مسائل با تمرکز بر موعد تحویل یکسان برای کارها…………………………………………………۳۹

۲-۴-۲-۱- موعد تحویل معلوم………………………………………………………………………………………۳۹

۲-۴-۲-۲- موعد تحویل نامعلوم…………………………………………………………………………………….۴۴

۲-۵ دسترسی محدود به ماشینها …………………………………………………………………………………………..۴۵

۲-۶ جمع بندی ………………………………………………………………………………………………………………….۴۵

 

فصل ۳- ارائه مدل ریاضی…………………………………………………………………………….۵۸-۴۶

۳-۱- مقدمه………………………………………………………………………………………………………….۴۷

۳-۲-تعریف مسئله………………………………………………………………………………………………….۴۷

۳-۳- فرضیات مسئله……………………………………………………………………………………………….۴۸

۳-۴- مدل ریاضی پیشنهادی………………………………………………………………………………………۴۹

۳-۴-۱- پارامترهای ورودی…………………………………………………………………………………….۴۹

۳-۴-۲- نمادها، تعاریف، پارامترها و متغیر های تصمیم…………………………………………………….۵۰

۳-۴-۳- مدل ریاضی…………………………………………………………………………………………….۵۱

۳-۵ –اعتبار سنجی مدل……………………………………………………………………………………………۵۳

۳-۶ –تئوری پیچیدگی و پیچیدگی مساله مورد نظر……………………………………………………………۵۶

۳-۶- جمعﺑندی……………………………………………………………………………………………………..۵۸

 

فصل ۴- الگوریتم پیشنهادی نتایج محاسباتی…………………………………………………..۱۱۰-۵۹

۴-۱ مقدمه……………………………………………………………………………………………………………………………۶۰

۴-۲ الگوریتم ژنتیک ……………………………………………………………………………………………………………..۶۲

۴-۲-۱ شمای کلی الگوریتم ژنتیک………………………………………………………………………………………….۶۴

۴-۳) اجزای الگوریتم ژنتیک…………………………………………………………………………………………………۶۶

    ۴-۳-۱) کروموزوم………………………………………………………………………………………………………….۶۶

    ۴-۳-۲) جمعیت………………………………………………………………………………………………………………۶۶

    ۴-۳-۳) مقدار برازندگی……………………………………………………………………………………………………۶۷

     ۶-۳-۴) کدگذاری……………………………………………………………………………………………………………۶۷

     ۴-۳-۵) انتخاب……………………………………………………………………………………………………………….۶۸

    ۴-۳-۶) عملگر تقاطعی……………………………………………………………………………………………………..۷۶

    ۴-۳-۷) جهش………………………………………………………………………………………………………………….۸۲

    ۴-۳-۸) جابه‌جایی…………………………………………………………………………………………………………….۸۳

    ۴-۳-۸) قاعده توقف………………………………………………………………………………………………………..۸۳

۴-۳ الگوریتم حرکت جمعی پرندگان ……………………………………………………………………………………..۸۴

۴-۴ حرکت دسته جمعی ذرات ………………………………………………………………………………………………۸۶

۴-۵ مفاهیم پایه الگوریتم…………………………………………………………………………………………………………۸۸

۴-۶ رابطه بروز رسانی سرعت…………………………………………………………………………………………………..۸۸

۴-۷ رابطه بروز رسانی موقعیت………………………………………………………………………………………………….۹۲

۴-۸ گامهای الگوریتم……………………………………………………………………………………………………………..۹۳

۴-۹ شبه کد الگوریتم……………………………………………………………………………………………………………….۹۳

۴-۱۰)طراحی الگوریتم پیشنهادی………………………………………………………………………………………………۹۴

۴-۱۰) تنطیمات پارامترها و شرایط اجرای الگوریتم ها……………………………………………………………………۹۹

۴‐۱۱) ساختار مسائل…………………………………………………………………………………………………………………۹۹

۴‐۱۲)مسائل با ابعاد کوچک و متوسط…………………………………………………………………………………………۱۰۰

۴-۱۳) نتایج آزمایشات……………………………………………………………………………………………………………..۱۰۰

۴-۱۴ مسائل با ابعاد بزرگ…………………………………………………………………………………………………………۱۰۷

۴-۱۵ جمع بندی………………………………………………………………………………………………………………………۱۰۹

 

فصل۵- نتیجه گیری و پیشنهادات آتی……………………………………………………………..۱۱۳-۱۱۰

۵-۱) نتیجه گیری……………………………………………………………………………………………………………………..۱۱۱

۵-۲) پیشنهادات آتی ………………………………………………………………………………………………………………..۱۱۳

منابع……………………………………………………………………………………………………………………………………….۱۱۵

 

 

فهرست جداول

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

جدول ۳-۱٫موعد تحویل و وزنهای زود کرد و دیرکرد……………………………………………………………۵۴

جدول ۳-۲ زمان پردازش کارها ………… ………………………………………………………………………………۵۴

جدول۳-۳ زمان آماده سازی کارها روی ماشین ۱…………………………………………………………………..۵۴

جدول۳-۴ زمان آماده سازی کارها روی ماشین ۲…………………………………………………………………..۵۵

جدول۳-۴ زمان آماده سازی کارها روی ماشین ۳…………………………………………………………………..۵۵

جدول ۳-۵- محاسبه تعداد متغیرها و محدودیت ها ………………………………………………………………۵۳

جدول۴-۱: انتخاب کروموزوم‌ها با استفاده از مدل چرخ رولت………………………………………………..۷۲

جدول۴-۲: مشکلات ممکن در مدل چرخ رولت…………………………………………………………………..۷۴

جدول۴-۳ وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای ۵j2m………………100

جدول۴-۴ زمان آماده سازی کارها روی ماشین ۱…………………………………………………………………..۱۰۱

جدول۴-۵ زمان آماده سازی کارها روی ماشین ۲……………………………………………………………………۱۰۱

جدول۴-۶ نتایج مربوط به مسئله ۵ کار و ۲ ماشین به تفکیک روشها………………………………………۱۰۱

جدول۴-۷ وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای ۵j3m……………….102

جدول ۴-۸ زمان آماده سازی کارها روی ماشین ۱………………………………………………………………….۱۰۲

جدول ۴-۹ زمان آماده سازی کارها روی ماشین ۲………………………………………………………………….۱۰۲

جدول ۴-۱۰ زمان آماده سازی کارها روی ماشین ۳………………………………………………………………..۱۰۳

جدول ۴-۱۱ نتایج مربوط به مسئله ۵ کار و ۳ ماشین………………………………………………………………۱۰۳

جدول۴-۱۲ وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای ۸j2m……………….103

جدول۴-۱۳ زمان آماده سازی کارها روی ماشین ۱…………………………………………………………………..۱۰۴

جدول۴-۱۵ زمان آماده سازی کارها روی ماشین ۲…………………………………………………………………..۱۰۵

جدول ۴-۱۶ نتایج مسئله ۸ کار و ۲ ماشین به تفکیک روشها……………………………………………………..۱۰۵

جدول۴-۱۷ وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای ۸ کارو۳ ماشین …..۱۰۵

جدول۴-۱۸ زمان آماده سازی کارها روی ماشین ۱…………………………………………………………………..۱۰۵

جدول۴-۱۹ زمان آماده سازی کارها روی ماشین ۲ ………………………………………………………………….۱۰۵

جدول۴-۲۰ زمان آماده سازی کارها روی ماشین ۳ ………………………………………………………………….۱۰۵

جدول ۴-۲۱ نتایج مسئله ۸ کار و ۳ ماشین به تفکیک روشها……………………………………………………..۱۰۶

جدول ۴-۲۲ نتایج مسئله ۱۰ کار و ۳ ماشین………………………………………………………………………۱۰۷

جدول ۴-۲۳ نتایج مسئله ۵۰ کار و ۱۰ ماشین……………………………………………………………………..۱۰۸

جدول ۴-۲۴ نتایج مسئله ۵۰ کار و ۲۰ ماشین……………………………………………………………………..۱۰۸

جدول ۴-۲۵ نتایج مسئله ۶۰ کار و ۱۰ ماشین…………………………………………………………………….۱۰۸

جدول ۴-۲۶ نتایج مسئله ۵۰ کار و ۲۰ ماشین……………………………………………………………………..۱۰۹

 

 

فهرست اشکال:

شکل۴-۱: چرخ رولت………………………………………………………………………………………………………..۷۰

شکل۴-۲: نمونه‌ای از انتخاب در چرخ رولت…………………………………………………………………………۷۱

شکل۴-۳: نمونه‌ای از عملگر تقاطع تک نقطه‌ای……………………………………………………………………..۷۷

شکل۴-۴: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ۰-۱………………………………………………..۷۹

شکل۴-۵: نمونه‌ای از عملگر تقاطع دو نقطه‌ای برای آرایه ترتیبی………………………………………………۷۹

شکل۴-۶: نمونه‌ای از عملگر تقاطع یکنواخت………………………………………………………………………..۸۱

شکل۴-۷ : ساختار کروموزوم……………………………………………………………………………………………….۹۵

شکل ۴-۸ : نحوه عملکرد عملگر تقاطع…………………………………………………………………………………۹۷

شکل ۴-۹: نحوه عملکرد عملگر جهش………………………………………………………………………………….۹۸

 

قیمت:   ۱۲۰۰۰ تومان

 

فرمت

مطلب مشابه

پایان نامه کارشناسی ارشد با عنوان تئوری تئوکراسی و قانون اساسی جمهوری اسلامی ایران

  عنوان: تئوری تئوکراسی و قانون اساسی جمهوری اسلامی ایران فهرست مطالب عنوان                                                                                                                          صفحه …