پایان نامه مقطع کارشناسی ارشد رشته صنایع

!–more–

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

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

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

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

عنوان:

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

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

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

استاد مشاور:

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

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

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

فصل 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…………………………………………..

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- مقدمه

در جهان رقابتی حاضر، توالی و زمانبندی موثر ضرورتی برای بقا در فضای بازار می باشد. زمانبندی ابزاری می باشد که بهره گیری از منابع در دسترس را بهینه می کند.زمان همواره یک محدودیت اساسی بوده، پس زمانبندی فعالیتها به مقصود حداقل کردن این منبع محدود یک الزام می باشد. زمانبندی و توالی عملیات یکی از مهم ترین مسائل برنامه ریزی تولید بوده و کاربردهای زیادی در واحدهای تولیدی و غیرتولیدی دارد.

اقدام زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان بهره گیری می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه می باشد که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می گردد. شرکت های تولیدی در کوشش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[1](JIT)، پاسخگوی سریع[2](QR)، تکنولوژی گروهی[3](GT)و مدیریت کیفیت جامع[4](TQM)بدست آورند[3].

این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده می باشد. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل گردد، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می گردد. در یک بازار رقابتی دیرکرد کارها با در نظر داشتن موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع می باشد.

مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیمJITمورد توجه بسیار قرار گرفته می باشد.چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل نمود اظهار می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری می باشد ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می گردد[4].

بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[5](ET) کاملا با سیاست کنترل تولید JITمطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به اینخاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول می باشد مورد توجه قرار گرفته شده می باشد.

مسئله به کارگیری ماشین های موازی[6] از آنجا مورد توجه می باشد که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی گردد ممکن می باشد در نظر گرفتن ماشینهای بیشتر سبب کاهش هزینه گردد. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می گردد که با حل مسئله بهینه سازی می توان تعیین نمود چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام گردد.

در اقدام، زمانبندی ها با بهره گیری از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند.

در این فصل، آغاز مروری بر انواع مسائل زمانبندی و تعریف بعضی مفاهیم اولیه زمانبندی پرداخته می گردد، در ادامه به خصوصیات و مشخصات مسأله مورد بحث این پژوهش، پرداخته می گردد. در پایان اهداف، ضرورت و متدولوژی پژوهش اظهار شده می باشد.

1-6- تعریف مسأله زمانبندی مربوط به پژوهش :

اظهار مسأله:

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

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

نظام تولید بهنگام[7] تفکر و نظری جدید در اداره سازمانهای صنعتی می باشد که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.

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

JIT یعنی :

  • پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر
  • بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن می باشد
  • در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”

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

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

1-زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها هست

2-هر کدام از کارها تنها بر روی زیر مجموعه ای از مجموعه ماشینها می تواند پردازش شوند

3-تمامی کارها در ابتدای افق زمانبندی در دسترس نمی باشد به تعبیری پردازش کار نمی تواند قبل از زمان دسترسی آغاز گردد

4-تمامی ماشینها به گونه مستمر دسترس هستند و امکان خرابی ماشینها وجود ندارد

5-هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد

6-هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می گردد

7-زمانهای پردازش،نصب،موعد تحویل و ضرایب هزینه زود نمود و دیر نمود زمانی معین می باشد

8-بیکاری ماشینها مجاز می باشد

1-8- ضرورت انجام پژوهش :

با در نظر داشتن اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.

امروزه در اغلب کارخانجات تولیدی و شرکت های خدماتی تأمین به موقع سفارش مشتری یا خدمت رسانی به موقع مهم می باشد. هزینه های زودکرد و دیرکرد در این امور نه تنها مشتری را متضرر می گرداند بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از نظر مشتری از دست می دهد. مسائل تخصیص موعد تحویل زمانی جنبه عملی دارد که یک شرکت یک موعد تحویل به مشتریان در طول مذاکرات فروش پیشنهاد می کند و یک قیمت تقلیل یافته (جریمه) برای زمانیکه موعد تحویل دور از موعد انتظار باشد پیشنهاد می کند.

هر چه موعدهای تحویل ثابت شده تر باشد احتمال اینکه محصول به موقع تحویل داده گردد بیشتر می باشد. به مقصود نگهداشتن یک وجهه خوب در میان مشتریان بسیاری از شرکت ها برای حفظ موعدهای تحویل ایجاد شده، هزینه های نگهداری معقولی را متحمل می شوند .

تقریبا همه مقالاتی که هدف های زودکرد و

  • 1