وزارت علوم، تحقیقات و فناوری
دانشگاه علوم و فنون مازندران
پایان نامه
مقطع كارشناسی ارشد
رشته:
مهندسی صنایع – مهندسی صنایع
عنوان:
مدل برنامه ریزی ریاضی جدید برای مسأله زمانبندی کارگاه باز چند هدفه با در نظر گرفتن نگهداری و تعمیرات دورهای
استاد راهنما:
پروفسور رضا توكلی مقدم
استاد مشاور:
دكتر بهمن نادری
تیر 1391
برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود
(در فایل دانلودی نام نویسنده موجود است)
تکه هایی از متن پایان نامه به عنوان نمونه :
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
فهرست مطالب
عنوان | صفحه |
1- فصل اول: معرفی و كلیات تحقیق | 1 |
1-1- مقدمه | 2 |
1-2- تعاریف زمانبندی | 3 |
1-2-1- نمادها | 3 |
1-2-2- محیط ماشینها و نوع كارگاه | 4 |
1-2-3- مشخصههای كاری و محدودیتهای زمانبندی | 5 |
1-2-4- معیارهای بهینهسازی | 7 |
1-3- نظریهء زمانبندی | 9 |
1-4- برنامه ریزی ریاضی | 9 |
1-5- زمانبندی چند هدفه | 9 |
1-6- الگوریتمهای فرا ابتكاری در بهینهسازی | 11 |
1-6-1- الگوریتم ژنتیك | 11 |
1-6-2- الگوریتم شبیهسازی تبرید | 12 |
1-7- طراحی آزمایشات | 12 |
1-8- مسألهء زمانبندی كارگاه باز | 13 |
2- فصل دوم: مرور ادبیات | 15 |
2-1- مقدمه | 16 |
2-2- معیارهای اندازه گیری و تابع هدف | 16 |
2-3- مجاز نبودن بریدگی كارها | 18 |
2-4- نگهداری و تعمیرات دورهای و محدودیت عدم دسترسی ماشینها | 18 |
2-5- زمانهای حمل و نقل | 19 |
2-6- زمانهای آمادهسازی و جداسازی | 20 |
2-7- روشهای حل | 20 |
2-8- طراحی آزمایشات | 22 |
3- فصل سوم: طرح مسأله و ارائه روشهای حل | 24 |
3-1- مقدمه | 25 |
3-2- فرمولبندی مسأله | 25 |
3-2-1- فرضهای مسأله | 25 |
3-2-2- نماد گذاری | 26 |
3-2-2-1- اندیسها | 26 |
3-2-2-2- پارامترها | 26 |
3-2-2-3- متغیرهای تصمیم | 26 |
3-2-3- مدل برنامه ریزی خطی مختلط | 26 |
3-2-4- یك مثال | 28 |
3-2-5- تحلیل مدل | 29 |
3-3- الگوریتمهای فرا ابتكاری | 30 |
3-3-1- الگوریتم ژنتیك | 30 |
3-3-1-1- نمایش كروموزوم | 30 |
3-3-1-2- جمعیت اولیه | 30 |
3-3-1-3- تابع هدف | 31 |
3-3-1-4- تابع برازندگی | 31 |
3-3-1-5- انتخاب | 31 |
3-3-1-6- تقاطع | 31 |
3-3-1-7- جهش | 33 |
3-3-1-8- معیار توقف | 33 |
3-3-1-9- الگوریتم ژنتیك اولیه | 33 |
3-3-1-10- الگوریتم ژنتیك موازی چند هدفه | 34 |
3-3-2- الگوریتم شبیهسازی تبرید | 35 |
3-3-2-1- الگوریتم شبیهسازی تبرید اولیه | 35 |
3-3-2-2- الگوریتم شبیهسازی تبرید موازی چند هدفه | 37 |
4- فصل چهارم: طراحی آزمایشات و ارزیابی محاسباتی | 38 |
4-1- مقدمه | 39 |
4-2- طراحی آزمایشات تاگوچی | 39 |
4-2-1- تولید دادهها | 40 |
4-2-2- تنظیم پارامترهای الگوریتم MOPGA | 40 |
4-2-3- تنظیم پارامترهای الگوریتم MOPSA | 42 |
4-3- ارزیابی محاسباتی | 43 |
5- فصل پنجم: جمعبندی و مطالعات آتی |
45 |
5-1- جمعبندی | 46 |
5-2- مطالعات آتی | 46 |
مراجع | 48 |
فهرست جداول
عنوان | صفحه |
1-1- مقادیر پارامتر α | 5 |
1-2- مقادیر پارامتر β | 7 |
1-3- مقادیر پارامتر γ | 8 |
3-1- تعداد متغیرها | 29 |
3-2- تعداد محدودیتها | 29 |
3-3- تعداد متغیرها و محدودیتها مطابق با مدل MOMILP | 29 |
4-1 فاكتورهای الگوریتم MOPGA و سطوح آنها | 41 |
4-2- آزمایشات مربوط به آرایهء L9 در الگوریتم MOPGA | 41 |
4-3- جدول تحلیل واریانس كسر S/N مربوط به فاكتورهای الگوریتم MOPGA | 42 |
4-4- فاكتورهای الگوریتم MOPSA و سطوح آنها | 42 |
4-5- آزمایشات مربوط به آرایهء L4 در الگوریتم MOPSA | 42 |
4-6- جدول تحلیل واریانس كسر S/N مربوط به فاكتورهای الگوریتم MOPSA | 43 |
4-7- عملكرد مدل MOMILP و الگوریتمهای GA و SA اولیه در برخورد با مسألههای با ابعاد كوچك | 44 |
4-8- میانگین RPD برای الگوریتمهای MOPGA و MOPSA در حل مسألههای با ابعاد بزرگ | 44 |
فهرست شكلها
عنوان | صفحه |
1-1- رابطهء جایگزینی بین دو هدف و | 10 |
3-1- توالی كارها روی یك ماشین j | 25 |
3-2- نمودار گانت مربوط به حل بهینهء مثال | 28 |
3-3- نحوهء تقسیمبندی جمعیت و عملكرد موازی زیر-جمعیتها | 34 |
3-4- جستجوی همسایگی الگوریتم شبیهسازی تبرید | 36 |
3-5- قدمهای الگوریتم شبیهسازی تبرید اولیه | 36 |
4-1- نمودار كسر S/N مربوط به RPD در فاكتورهای الگوریتم MOPGA | 41 |
4-2- نمودار كسر S/N مربوط به RPD در فاكتورهای الگوریتم MOPSA | 43 |
فصل اول
معرفی و كلیات تحقیق
- مقدمه
از مهمترین شرطهای ارتقای وضعیت فعلی در هر سازمان میتوان به استفادهء مناسب از سرمایهها و جلوگیری از هدر رفت آنها اشاره كرد. منظور از ” استفادهء مناسب ” در اینجا مفهومِ واژهء كارایی[1] یعنی سرعت عمل در استفاده از ظرفیت است كه بدون داشتن برنامهء از پیش تعیین شده ممكن نیست. افزون بر آن، هرچه دقت در برنامه بیشتر و مطالعه مكفیتر باشد سرعت عمل بیشتر شده و توان رقابتی بالاتر میرود. وقتی صحبت از سرمایههای یك سازمان به میان میآید ممكن است ذهنها به سمت سرمایههای فیزیكی مثل ماشینآلات و دستگاههای گرانقیمت منحرف شود. حال آنكه، مفهوم مورد انتظار ما بطور خاص “زمان” است. استفادهء مناسب از زمان بعنوان یك سرمایه و جلوگیری از هدر رفت آن از جمله ابزارهای مهم مدیرانِ سازمانها در عرصههای رقابتی است. زمان را میتوان منبعی دانست كه باید بطور صحیح تقسیمبندی و مدیریت شده و با برنامهء خاص به فعالیتها تخصیص داده شود و این همان چیزیست كه به آن زمانبندی[2] اطلاق میشود.
زمانبندی شامل تخصیص[3] منابع محدود به فعالیتهاست با هدف بهینهسازی یك یا چند معیار اندازه گیری[4] [1]. از طرفی، ماهیت برخی منابع همچون ماشینآلات و نیروی انسانی بگونهای است كه قادر به انجام همزمان بیش از یك فعالیت نیستند. بنابراین، تعریف دیگری برای زمانبندی به این شرح ارائه میشود: زمانبندی، یافتن توالی[5] مناسب انجام فعالیتها توسط ماشینها و یا نیروی انسانی است بنحوی كه یك یا چند معیار اندازه گیری بهینه شوند. برای تحلیل سیستم زمانبندیِ تولیدِ جاری و یافتن راههای بهبود آن، آگاهی از روشهای زمانبندی تولید بسیار مهم است. دو مسألهء كلیدی در زمانبندیِ تولید اولویت و ظرفیت هستند [2]. بعبارت دیگر، “چه كاری باید ابتدا انجام شود؟” و “چه كسی باید آن را انجام دهد؟” وایت [2] زمانبندی را اینگونه تعریف میكند: “تعیین زمان برای انجام یك فعالیت”. او همچنین، در یك شركت تولیدی زمانبندیِ تفصیلی[6] در سطح یك كارگاه را درنظر میگیرد. یعنی، زمانبندی كه در آن زمان شروع و پایان هر عملیات معلوم است. كوكس و همكاران [3] زمانبندی تفصیلی را اینگونه تعریف میكنند: “تخصیص واقعی زمان شروع و یا پایان فعالیتها یا گروهی از فعالیتها بنحوی كه سفارش تولید در موعد مقرر تكمیل شود.” آنها همچنین از زمانبندی عملیات[7]، زمانبندی سفارش[8] و زمانبندی كارگاه[9] بطور معادل یاد میكنند.
تعابیر متنوعی از تعریفهای ارائه شده برای زمانبندی در محیط های مختلف قابل تصور است. بعنوان مثال، منابع میتوانند ماشینها در یك كارگاه، پردازنده و حافظه در یك سیستم كامپیوتری، باندهای فرود در یك فرودگاه، تعمیركاران در یك تعمیرگاه خودرو و غیره باشند. همچنین، فعالیتها میتوانند شامل عملیات مختلف در یك فرآیند ساخت، اجرای یك برنامهء كامپیوتری، نشستن و برخاستن هواپیماها در فرودگاه، تعمیر خودروهای تعمیرگاه و مواردی از این دست باشند.
مطالعه بر روی زمانبندی به دههء 1950 برمیگردد كه محققان در پژوهش عملیاتی[10]، مهندسی صنایع و مدیریت با مسألهء اداره كردن فعالیتهای مختلفی كه در یك كارگاه رخ میدادند مواجه بودند. در آن زمان، الگوریتمهای زمانبندی خوب میتوانستند هزینهء تولید را در فرآیند ساخت كاهش داده و توان رغابتی شركتها را بالا ببرند. در اواخر دههء 1960، دانشمندان كامپیوتر نیز با مسألهء زمانبندی در توسعه سیستمهای عملیاتی روبرو شدند. چراكه، در آن روزها منابع محاسباتی همچون پردازشگرها و حافظهها محدود بودند و بهره برداری مؤثر از این منابع محدود میتوانست هزینهء اجرای برنامه های كامپیوتری را كاهش دهد. بنابراین، مطالعه بر روی زمانبندی توجیه اقتصادی پیدا كرد [4].
مسألههای زمانبندی در دههء 1950 بسیار ساده بودند و تعدادی الگوریتمهای كارا برای رسیدن به جواب بهینه توسعه یافتند كه كارهای جكسون [5،6]، جانسون [7] و اسمیت [8] از مهمترین آنها هستند. با گذشت زمان، مسألهها پیچیدهتر شده و دیگر محققان قادر به توسعه الگوریتمهای كارا برای آنها نبودند. بیشتر محققان تلاش كردند روشهای شاخه و كران[11] را كه عمدتاً الگوریتمهایی با زمان نمایی[12] بودند را گسترش دهند. با ظهور تئوری پیچیدگی[13] [11-9]، محققان دریافتند كه بسیاری از این مسألهها ذاتاً برای حل سخت هستند. در دههء 1970 نشان داده شد كه بیشتر مسألههای زمانبندی NP-hard هستند [15-12] یعنی زمان حل آنها شدیداً غیر چندجملهای[14] است. در دههء 1980، چندین زمینهء مختلف در دانشگاه و صنعت مورد بررسی قرار گرفت. یكی از این زمینهها توسعه و تحلیل الگوریتمهای تقریبی[15] و دیگری افزایش توجه به مسألههای زمانبندی اتفاقی[16] بود. از آن پس، تحقیق در زمینهء تئوری زمانبندی با فراز و نشیبهایی همراه بوده است. بعد از گذشت بیش از 60 سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.
- تعاریف زمانبندی
هر چند كه مفهوم زمانبندی بسیار فراگیر بوده و كاربردهای متنوعی در محیطهای مختلف برای آن قابل تصور است ولی ما از رویكرد سیستمهای تولیدی و صنعتی جهت بسط و گسترش آن استفاده میكنیم. پیش از آن كه بخواهیم درمورد زمانبندی تخصصیتر صحبت كنیم، لازم است نمادها و عبارتهای مصطلح در این زمینه معرفی شوند. این بخش به معرفی برخی از آنها پرداخته و پس از توضیح چند نماد و تشریح محیط مورد نظر و شرایط آن، هدفها و معیارهای زمانبندی بیان میشوند.
[1] Efficiency
[2] Scheduling
[3] Allocation
[4] Performance measures
[5] Sequence
[6] Detailed scheduling
[7] Operations scheduling
[8] Order scheduling
[9] Shop scheduling
[10] Operations research
[11] Branch-and-bound
[12] Exponential-time
[13] Complexity theory
[14] Non-polynomial
[15] Approximation algorithms
[16] Stochastic
تعداد صفحه :61
قیمت :14700 تومان
بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد
و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.
پشتیبانی سایت : * asa.goharii@gmail.com
در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.
در صورتیکه با پرداخت آنلاین مشکلی دارید می توانید مبلغ مربوط به هر فایل را به شماره کارت 6037991199500590 به نام خيريه محک واريز کرده و تصوير پرداختي و عنوان فايل درخواستي را به ایمیل asa.gohari@gmail.com
ارسال کرده تا فايل برایتان ارسال شود.