.jpg) نام و نام خانوادگی: امیر ابراهیم زاده پیله رود
استاد راهنما: دکتر مهدی حیدری
اساتید مشاور: دکتر محمد مهدوی مزده
اساتید داور داخلی: دکتر تیموری، دکتر عمران محمدی
اساتید داور خارجی: دکتر تقوی فرد، دکتر زندیه
زمان جلسه: روز سه شنبه 18 دی ماه 1397 ساعت 11 - کلاس 314- طبقه سوم
موضوع رساله: زمان بندی جریان کارگاهی با هزینه های وابسته به زمان و موعد تحویل
چکیده
این رساله به معرفی یک مسئله در حوزه زمان‌بندی کارها با درنظرگیری هزینه پردازش کارهای وابسته به زمان پرداخته است. ابتدا مسئله زمان‌بندی در ساده‌ترین شکل، یعنی زمان‌بندی تکماشینه با هدف حداقل کردن هزینه‌های وابسته به زمان بدون درنظرگیری موعد تحویل کارها، مورد بررسی قرار گرفته است.
حل مسئله در محیط جریان کارگاهی دو ماشینه مورد بررسی قرار گرفته است. در شرایط کلی، تابع هدف مجموع هزینه‌های منابع، تابعی غیرمنظم است. در نتیجه با افزودن مقدار بیکاری تعمدی به برنامه زمان‌بندی، ممکن است مقدار تابع هدف بهتر شود.
با درنظر گرفتن امکان ایجاد بیکاری بین کارها، مسئله از حالت بهینه‌سازی ترکیبی خارج خواهد شد. چراکه فضای جواب‌های بهینه شامل بینهایت جواب شدنی خواهد بود. به عنوان مثال برای هریک از توالی کارها، تعیین مقدار بیکاری بین دو کار مجاور، یکی از متغیرهای پیوسته مسئله خواهد بود. از طرف دیگر وجود فرض بیکاری مجاز برای ماشین‌ها، ممکن است منجر به بهتر شدن تابع هدف شود چراکه فضای حل مسئله را محدودتر نمی‌کند. در بخش اول، برای حل مسئله زمان‌بندی در فضای جریان کارگاهی، به بررسی مسائل جریان‌کارگاهی بدون موعد تحویل و در دو حالت بیکاری مجاز و بیکاری غیرمجاز پرداخته‌ایم و مسئله به صورت تک‌هدفه و بدون دخیل کردن مقدار موعد تحویل کار به مشتری بررسی شده است و در بخش دوم، تابع هدف تاخیر کل در تحویل کارها نیز در کنار تابع هدف هزینه انرژی لحاظ شده است و رویکردهای بهینه‌سازی چند هدفه استفاده شده است.
برای حل مسئله تک هدفه رویکردهای مختلفی پیشنهاد شده است. در ابتدا یک مدل ریاضی MIP خطی پیشنهاد شده است که امکان حل مسائل در زمان معقول تا 10 کار و 3 بازه هزینه‌ای را به کمک سالورهای تجاری داراست.
سپس یک الگوریتم حریصانه ابتکاری پیشنهاد شده است که در دو مرحله ابتدا به تخصیص کارها به مرزهای هزینه‌ای و سپس به جابه‌جایی کارها جهت حداقل کردن هزینه انرژی می‌پردازد. این الگوریتم در حل مسائل سایز بالا عملکرد خوبی از خود نشان داده است و در حالت 100 کار و 8 بازه هزینه‌ای، به مقدار 40% بهتر از جواب یافته شده ناشی از الگوریتم توالی جانسون عمل کرده است.
برای حالتی‌که امکان جابه‌جایی تعمدی کارها وجود نداشته باشد، یک الگوریتم مبتنی بر شاخه و کرانه پیشنهاد شده است. این الگوریتم با قوانین تسلط و همچنین تعریف یک حد پایین، ارتقای عملکرد یافته است و جواب بهینه تا 15 کار را در زمان معقول استخراج می‌کند. در نهایت حدود پایین با دو رویکرد الگوریتمی و مدل ریاضی ارائه شده‌اند که مقدار هزینه انرژی از 16 تا 20 درصد اختلاف با مقدار بهینه را حاصل می‌کنند.
با دو هدفه کردن مسئله و درنظرگیری مقدار جریمه تاخیر در تحویل کارها به مشتری، یک مدل ریاضی تعمیم‌یافته و بهبود یافته نسبت به مدل ریاضی قبلی ارائه شده است که در مسائل با تعداد بازه هزینه بالا، تا 60% بهبود در سرعت عملکرد مدل تجاری سیپلکس را به دنبال دارد. البته همچنان به دلیل پیچیدگی مسئله، امکان یافتن جواب بهینه برای تعداد کارهای بیش از 10 مهیا نیست. به منظور بی‌بعدسازی توابع هدف، از روش نرمالسازی وزن‌دار استفاده شده است و برای استخراج جبهه پارتویی رویکرد اپسیلون محدودیت برای مسئله پیاده شده است.
برای حل مسائل بزرگتر در زمان معقول، چندین رویکرد بهینه‌سازی فراابتکاری ترکیبی چند هدفه پیشنهاد شده است که از بین آن‌ها الگوریتم ترکیبی NSGA-II با VNS نسبت به الگوریتم چندهدفه MOPSO عملکرد بسیار بهتری داشته است و می‌تواند در حل مسائل سایز بالا به منظور استخراج یک جبهه پارتویی مورد استفاده قرار گیرد.
درنهایت به منظور بررسی دو تابع هدف به صورت ترتیبی، یک رویکرد لکسیکوگرافی پیشنهاد شده است که تابع هدف جریمه دیرکرد را به عنوان تابع هدف اول در نظر می‌گیرد حال آنکه به دنبال حداقل کردن مقدار هزینه انرژی است (به شرط خراب نشدن تابع هدف اول). در همین راستا یک مدل ریاضی MIP و همچنین یک الگوریتم ابتکاری مبتنی بر قوانین بازگشتی ارائه شده است که در مسائل سایز بالا تا 60% توالی اولیه را در جهت کاهش مقدار هزینه انرژی بهبود می‌دهد. این میزان بهبود در برخی موارد تا 10% نیز گزارش شده است.
به طور خلاصه، در این رساله ضمن معرفی یک مسئله نو در ادبیات زمان‌بندی، انواع رویکردها به جهت استخراج جواب‌های بهینه محلی و جهانی مورد استفاده قرار گرفته است. رویکردهای برنامه‌ریزی ریاضی تک‌هدفه و چندهدفه، ارائه الگوریتم‌های ابتکاری مبتنی بر روش‌های حریصانه، ارائه الگوریتم‌هایی برای محاسبه حدود پایین، ارائه الگوریتم شاخه و کرانه جهت استخراج جواب بهینه جهانی به همراه قوانین تسلط و محاسبه حد پایین، ارائه الگوریتم‌های فراابتکاری مبتنی بر روش ژنتیک، جستجوی همسایگی و جستجوی جمعی و در نهایت ارائه رویکردهای مبتنی بر روش لکسیکوگرافی برای بهبود در مقدار تابع هدف، همگی از جمله تکنیک‌ها و رویکردهای اتخاذ شده در این رساله است. |