مهندسی صنایع

پایان نامه: مدل برنامه ریزی ریاضی جدید برای مسأله زمان بندی کارگاه باز چند هدفه با در نظر …

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

پروفسور رضا توکلی مقدم

متن پایان نامه :

فهرست مطالب:

۱- فصل اول: معرفی و کلیات تحقیق۱
۱-۱- مقدمه۲
۱-۲- تعاریف زمان­بندی۳
۱-۲-۱- نمادها۳
۱-۲-۲- محیط ماشین­ها و نوع کارگاه۴
۱-۲-۳- مشخصه­های کاری و محدودیت­های زمان­بندی۵
۱-۲-۴- معیارهای بهینه­سازی۷
۱-۳- نظریهء زمان­بندی۹
۱-۴- برنامه ­ریزی ریاضی۹
۱-۵- زمان­بندی چند هدفه۹
۱-۶- الگوریتم­های فرا ابتکاری در بهینه­سازی۱۱
۱-۶-۱- الگوریتم ژنتیک۱۱
۱-۶-۲- الگوریتم شبیه­سازی تبرید۱۲
۱-۷- طراحی آزمایشات۱۲
۱-۸- مسألهء زمان­بندی کارگاه باز۱۳
۲- فصل دوم: ادبیات۱۵
۲-۱- مقدمه۱۶
۲-۲- معیارهای اندازه ­گیری و تابع هدف۱۶
۲-۳- مجاز نبودن بریدگی کارها۱۸
۲-۴- نگهداری و تعمیرات دوره­ای و محدودیت عدم دسترسی ماشین­ها۱۸
۲-۵- زمان­های حمل و نقل۱۹
۲-۶- زمان­های آماده­سازی و جداسازی۲۰
۲-۷- روش­های حل۲۰
۲-۸- طراحی آزمایشات۲۲
۳- فصل سوم: طرح مسأله و ارائه روش­های حل۲۴
۳-۱- مقدمه۲۵
۳-۲- فرمول­بندی مسأله۲۵
۳-۲-۱- فرض­های مسأله۲۵
۳-۲-۲- نماد گذاری۲۶
۳-۲-۲-۱- اندیس­ها۲۶
۳-۲-۲-۲- پارامترها۲۶
۳-۲-۲-۳- متغیرهای تصمیم۲۶
۳-۲-۳- مدل برنامه ­ریزی خطی مختلط۲۶
۳-۲-۴- یک مثال۲۸
۳-۲-۵- تحلیل مدل۲۹
۳-۳- الگوریتم­های فرا ابتکاری۳۰
۳-۳-۱- الگوریتم ژنتیک۳۰
۳-۳-۱-۱- نمایش کروموزوم۳۰
۳-۳-۱-۲- جمعیت اولیه۳۰
۳-۳-۱-۳- تابع هدف۳۱
۳-۳-۱-۴- تابع برازندگی۳۱
۳-۳-۱-۵- انتخاب۳۱
۳-۳-۱-۶- تقاطع۳۱
۳-۳-۱-۷- جهش۳۳
۳-۳-۱-۸- معیار توقف۳۳
۳-۳-۱-۹- الگوریتم ژنتیک اولیه۳۳
۳-۳-۱-۱۰- الگوریتم ژنتیک موازی چند هدفه۳۴
۳-۳-۲- الگوریتم شبیه­سازی تبرید۳۵
۳-۳-۲-۱- الگوریتم شبیه­سازی تبرید اولیه۳۵
۳-۳-۲-۲- الگوریتم شبیه­سازی تبرید موازی چند هدفه۳۷
۴- فصل چهارم: طراحی آزمایشات و ارزیابی محاسباتی۳۸
۴-۱- مقدمه۳۹
۴-۲- طراحی آزمایشات تاگوچی۳۹
۴-۲-۱- تولید داده­ ها۴۰
۴-۲-۲- تنظیم پارامترهای الگوریتم MOPGA۴۰
۴-۲-۳- تنظیم پارامترهای الگوریتم MOPSA۴۲
۴-۳- ارزیابی محاسباتی۴۳
۵- فصل پنجم: جمع­بندی و مطالعات آتی 

۴۵

۵-۱- جمع­بندی۴۶
۵-۲- مطالعات آتی۴۶
مراجع۴۸

فهرست جداول

پایان نامه - مقاله - متن کامل

عنوانصفحه
۱-۱- مقادیر پارامتر α۵
۱-۲- مقادیر پارامتر β۷
۱-۳- مقادیر پارامتر γ۸
۳-۱- تعداد متغیرها۲۹
۳-۲- تعداد محدودیت­ها۲۹
۳-۳- تعداد متغیرها و محدودیت­ها مطابق با مدل MOMILP۲۹
۴-۱ فاکتورهای الگوریتم MOPGA و سطوح آن­ها۴۱
۴-۲- آزمایشات مربوط به آرایهء L9 در الگوریتم MOPGA۴۱
۴-۳- جدول تحلیل واریانس کسر S/N مربوط به فاکتورهای الگوریتم MOPGA۴۲
۴-۴- فاکتورهای الگوریتم MOPSA و سطوح آن­ها۴۲
۴-۵- آزمایشات مربوط به آرایهء L4 در الگوریتم MOPSA۴۲
۴-۶- جدول تحلیل واریانس کسر S/N مربوط به فاکتورهای الگوریتم MOPSA۴۳
۴-۷- عملکرد مدل MOMILP و الگوریتم­های GA و SA اولیه در برخورد با مسأله­های با ابعاد کوچک۴۴
۴-۸- میانگین RPD برای الگوریتم­های MOPGA و MOPSA در حل مسأله­های با ابعاد بزرگ۴۴

 

فهرست شکل­ها

عنوانصفحه
۱-۱- رابطهء جایگزینی بین دو هدف و۱۰
۳-۱- توالی کارها روی یک ماشین j۲۵
۳-۲- نمودار گانت مربوط به حل بهینهء مثال۲۸
۳-۳- نحوهء تقسیم­بندی جمعیت و عملکرد موازی زیر-جمعیت­ها۳۴
۳-۴- جستجوی همسایگی الگوریتم شبیه­سازی تبرید۳۶
۳-۵- قدم­های الگوریتم شبیه­سازی تبرید اولیه۳۶
۴-۱- نمودار کسر S/N مربوط به RPD در فاکتورهای الگوریتم MOPGA۴۱
۴-۲- نمودار کسر S/N مربوط به RPD در فاکتورهای الگوریتم MOPSA۴۳

چکیده

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

مقدمه

از مهمترین شرط­های ارتقای وضعیت فعلی در هر سازمان می­توان به استفادهء مناسب از سرمایه­ها و جلوگیری از هدر رفت آن­ها اشاره کرد. منظور از ” استفادهء مناسب ” در اینجا مفهومِ واژهء کارایی[۱] یعنی سرعت عمل در استفاده از ظرفیت است که بدون داشتن برنامهء از پیش تعیین شده ممکن نیست. افزون بر آن، هرچه دقت در برنامه بیشتر و مطالعه مکفی­تر باشد سرعت عمل بیشتر شده و توان رقابتی بالاتر می­رود. وقتی صحبت از سرمایه­های یک سازمان به میان می­آید ممکن است ذهن­ها به سمت سرمایه­های فیزیکی مثل ماشین­آلات و دستگاه­های گران­قیمت منحرف شود. حال آنکه، مفهوم مورد انتظار ما بطور خاص “زمان” است. استفادهء مناسب از زمان بعنوان یک سرمایه و جلوگیری از هدر رفت آن از جمله ابزارهای مهم مدیرانِ سازمان­ها در عرصه­های رقابتی است. زمان را می­توان منبعی دانست که باید بطور صحیح تقسیم­بندی و مدیریت شده و با برنامهء خاص به فعالیت­ها تخصیص داده شود و این همان چیزیست که به آن زمان­بندی[۲] اطلاق می­شود.

زمان­بندی شامل تخصیص[۳] منابع محدود به فعالیت­هاست با هدف بهینه­سازی یک یا چند معیار اندازه ­گیری[۴] [۱]. از طرفی، ماهیت برخی منابع همچون ماشین­آلات و نیروی انسانی بگونه­ای است که قادر به انجام همزمان بیش از یک فعالیت نیستند. بنابراین، تعریف دیگری برای زمان­بندی به این شرح ارائه می­شود: زمان­بندی، یافتن توالی[۵] مناسب انجام فعالیت­ها توسط ماشین­ها و یا نیروی انسانی است بنحوی که یک یا چند معیار اندازه ­گیری بهینه شوند. برای تحلیل سیستم زمان­بندیِ تولیدِ جاری و یافتن راه­های بهبود آن، آگاهی از روش­های زمان­بندی تولید بسیار مهم است. دو مسألهء کلیدی در زمان­بندیِ تولید اولویت و ظرفیت هستند [۲]. بعبارت دیگر، “چه کاری باید ابتدا انجام شود؟” و “چه کسی باید آن را انجام دهد؟” وایت [۲] زمان­بندی را اینگونه تعریف می­ کند: “تعیین زمان برای انجام یک فعالیت”. او همچنین، در یک شرکت تولیدی زمان­بندیِ تفصیلی[۶] در سطح یک کارگاه را درنظر می­گیرد. یعنی، زمان­بندی که در آن زمان شروع و پایان هر عملیات معلوم است. کوکس و همکاران [۳] زمان­بندی تفصیلی را اینگونه تعریف می­ کنند: “تخصیص واقعی زمان شروع و یا پایان فعالیت­ها یا گروهی از فعالیت­ها بنحوی که سفارش تولید در موعد مقرر تکمیل شود.” آن­ها همچنین از زمان­بندی عملیات[۷]، زمان­بندی سفارش[۸] و زمان­بندی کارگاه[۹] بطور معادل یاد می­ کنند.

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

مطالعه بر روی زمان­بندی به دههء ۱۹۵۰ برمی­گردد که محققان در پژوهش عملیاتی[۱۰]، مهندسی صنایع و مدیریت با مسألهء اداره کردن فعالیت­های مختلفی که در یک کارگاه رخ می­دادند مواجه بودند. در آن زمان، الگوریتم­های زمان­بندی خوب می­توانستند هزینهء تولید را در فرآیند ساخت کاهش داده و توان رغابتی شرکت­ها را بالا ببرند. در اواخر دههء ۱۹۶۰، دانشمندان کامپیوتر نیز با مسألهء زمان­بندی در توسعه سیستم­های عملیاتی روبرو شدند. چراکه، در آن روزها منابع محاسباتی همچون پردازشگرها و حافظه­ها محدود بودند و بهره ­برداری مؤثر از این منابع محدود می­توانست هزینهء‌ اجرای برنامه ­های کامپیوتری را کاهش دهد. بنابراین، مطالعه بر روی زمان­بندی توجیه اقتصادی پیدا کرد [۴].

مسأله­های زمان­بندی در دههء ۱۹۵۰ بسیار ساده بودند و تعدادی الگوریتم­های کارا برای رسیدن به جواب بهینه توسعه یافتند که کارهای جکسون [۵،۶]، جانسون [۷] و اسمیت [۸] از مهمترین آن­ها هستند. با گذشت زمان، مسأله­ها پیچیده­تر شده و دیگر محققان قادر به توسعه الگوریتم­های کارا برای آن­ها نبودند. بیشتر محققان تلاش کردند روش­های شاخه و کران[۱۱] را که عمدتاً الگوریتم­هایی با زمان نمایی[۱۲] بودند را گسترش دهند. با ظهور تئوری پیچیدگی[۱۳] [۱۱-۹]، محققان دریافتند که بسیاری از این مسأله­ها ذاتاً برای حل سخت هستند. در دههء ۱۹۷۰ نشان داده شد که بیشتر مسأله­های زمان­بندی NP-hard هستند [۱۵-۱۲] یعنی زمان حل آن­ها شدیداً غیر چندجمله­ای[۱۴] است. در دههء ۱۹۸۰، چندین زمینهء مختلف در دانشگاه و صنعت مورد بررسی قرار گرفت. یکی از این زمینه­ها توسعه و تحلیل الگوریتم­های تقریبی[۱۵] و دیگری افزایش توجه به مسأله­های زمان­بندی اتفاقی[۱۶] بود. از آن پس، تحقیق در زمینهء تئوری زمان­بندی با فراز و نشیب­هایی همراه بوده ­است. بعد از گذشت بیش از ۶۰ سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.
***ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود است***

متن کامل را می توانید دانلود نمائید

چون فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به طور نمونه)

ولی در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

تعداد صفحه : ۶۶

99