زمان‏بندي در محيط جريان كارگاهي با هزينه ‏هاي وابسته به زمان و موعد تحويل

دكتري

اين رساله به معرفي يك مسئله جديد در حوزه زمان‌بندي كارها با درنظرگيري هزينه پردازش كارهاي وابسته به زمان پرداخته است. مهم‌ترين كاربرد اين نوع مسائل در زمان‌بندي كارهايي است كه هزينه انرژي متفاوتي بر سيستم تحميل مي‌كنند. اين رساله به دنبال يافتن بهترين زمان‌بندي كارها است در شرايطي كه هزينه انرژي و هزينه تحويل كارها به مشتريان حداقل گردد. در اين مسئله بازه‌هاي هزينه‌اي گوناگون وجود خواهند داشت كه در هر بازه هزينه‌اي، مقدار هزينه انرژي يا منبع متفاوت خواهد بود. مسئله اصلي در فضاي جريان كارگاهي دو ماشينه باجايگشت بررسي شده است. اين مسئله براي اولين بار در ادبيات مورد بررسي قرار گرفته است و نوآوري اصلي رساله، تحليل و ارائه روش‌هاي حل دقيق و ابتكاري براي يافتن جواب‌هاي مسئله است. در شرايط كلي، تابع هدف مجموع هزينه‌هاي منابع، تابعي بي‌قاعده است. در نتيجه با افزودن مقدار بيكاري تعمدي به برنامه زمان‌بندي، ممكن است مقدار تابع هدف بهتر شود. با توجه به وجود اين ويژگي در مسئله، لازم است تا هر دو نوع مسئله 1- با درنظرگيري امكان ايجاد بيكاري 2- بدون درنظرگيري امكان ايجاد بيكاري لحاظ شوند. در بخش اول، براي حل مسئله زمان‌بندي در فضاي جريان كارگاهي، به بررسي مسائل جريان‌كارگاهي بدون موعد تحويل و در دو حالت بيكاري مجاز و بيكاري غيرمجاز پرداخته‌ايم و مسئله به صورت تك‌هدفه و بدون دخيل كردن مقدار موعد تحويل كار به مشتري بررسي شده است و در بخش دوم، تابع هدف تاخير كل در تحويل كارها نيز در كنار تابع هدف هزينه انرژي لحاظ شده است و رويكردهاي بهينه‌سازي چند هدفه استفاده شده است. براي حل مسئله تك هدفه رويكردهاي مختلفي پيشنهاد شده است. در ابتدا يك مدل رياضي MIP خطي پيشنهاد شده است كه امكان حل مسائل در زمان معقول تا 10 كار و 3 بازه هزينه‌اي را به كمك سالورهاي تجاري داراست. اين مدل رياضي به صورت زمان پيوسته به يافتن جواب بهينه مي‌پردازد. سپس يك الگوريتم حريصانه ابتكاري پيشنهاد شده است كه در دو مرحله ابتدا به تخصيص كارها به مرزهاي هزينه‌اي و سپس به جابه‌جايي كارها جهت حداقل كردن هزينه انرژي مي‌پردازد. اين الگوريتم در حل مسائل سايز بالا عملكرد خوبي از خود نشان داده است و در حالت 100 كار و 8 بازه هزينه‌اي، به مقدار 40% بهتر از جواب يافته شده ناشي از الگوريتم توالي جانسون عمل كرده است. براي حالتي‌كه امكان جابه‌جايي تعمدي كارها وجود نداشته باشد، يك الگوريتم مبتني بر شاخه و كران پيشنهاد شده است. اين الگوريتم با قوانين تسلط و همچنين تعريف يك حد پايين، ارتقاي عملكرد يافته است و جواب بهينه تا 15 كار را در زمان معقول استخراج مي‌كند. در نهايت حدود پايين با دو رويكرد الگوريتمي و مدل رياضي ارائه شده‌اند كه مقدار هزينه انرژي از 16 تا 20 درصد اختلاف با مقدار بهينه را حاصل مي‌كنند. با دو هدفه كردن مسئله و درنظرگيري مقدار جريمه تاخير در تحويل كارها به مشتري، يك مدل رياضي تعميم‌يافته و بهبود يافته نسبت به مدل رياضي قبلي ارائه شده است كه در مسائل با تعداد بازه هزينه بالا، تا 60% بهبود در سرعت عملكرد مدل تجاري سيپلكس را به دنبال دارد. البته همچنان به دليل پيچيدگي مسئله، امكان يافتن جواب بهينه براي تعداد كارهاي بيش از 10 مهيا نيست. به منظور بي‌بعدسازي توابع هدف، از روش نرمالسازي وزن‌دار استفاده شده است و براي استخراج جبهه پارتويي رويكرد اپسيلون محدوديت براي مسئله پياده شده است. براي حل مسائل بزرگتر در زمان معقول، چندين رويكرد بهينه‌سازي فراابتكاري تركيبي چند هدفه پيشنهاد شده است كه از بين آن‌ها الگوريتم تركيبي NSGA-II با همسايگي نسبت به الگوريتم چندهدفه MOPSO عملكرد بسيار بهتري داشته است و مي‌تواند در حل مسائل سايز بالا به منظور استخراج يك جبهه پارتويي مورد استفاده قرار گيرد. درنهايت به منظور بررسي دو تابع هدف به صورت ترتيبي، يك رويكرد لكسيكوگرافي پيشنهاد شده است كه تابع هدف جريمه ديركرد را به عنوان تابع هدف اول در نظر مي‌گيرد حال آنكه به دنبال حداقل كردن مقدار هزينه انرژي است (به شرط خراب نشدن تابع هدف اول). در همين راستا يك مدل رياضي MIP و همچنين يك الگوريتم ابتكاري مبتني بر قوانين بازگشتي ارائه شده است كه در مسائل سايز بالا تا 60% توالي اوليه را در جهت كاهش مقدار هزينه انرژي بهبود مي‌دهد. اين ميزان بهبود در برخي موارد تا 10% نيز گزارش شده است. موردكاوي صنعتي كه در اين رساله مورد بررسي قرار گرفته است، شركت پرسكاري سايپاپرس است. در اين مجموعه براي يك فعاليت واحد، مصرف انرژي براي قطعات تا 300% مي‌تواند متفاوت باشد. به عنوان مثال پرس بلنك قطعه ركاب تندر 6 كيلووات انرژي مصرف مي‌كند در حاليكه پرس شيت رويه درب موتور پرايد حدود 18 كيلووات انرژي برق مصرف مي‌كند. اين تفاوت در مصرف انرژي از دلايل متنوعي نظير آلياژ قطعات، مدت زمان پرس، تعداد دفعات پرس، نوع قالب و غيره ناشي مي‌شود. با توجه به اينكه در اين مجموعه از داده‌ها، مقدار زمان و مصرف هزينه براي پردازش و پرسكاري هر قطعه متفاوت است، امكان بكارگيري بخشي از راهكارهاي مطرح شده در اين رساله به منظور زمان‌بندي بهينه با درنظرگيري هزينه انرژي وابسته به زمان ميسر خواهد بود. در نتيجه پس از جمع‌آوري اطلاعات مرتبط نظير زمان پردازش و مقدار برق مصرفي قطعات، دو سناريو مختلف براي دستيابي به توالي بهينه كارها درنظر گرفته شده است. در سناريو اول، تعداد كارها زياد است و دستيابي به جواب بهينه از طريق مدل رياضي ميسر نيست. در اين حالت با بهره‌گيري از رويكرد شاخه و كران مشاهده شده است كه مقدار هزينه برق مجموعه مي‌تواند تا 18% كاهش يابد. در سناريو دوم تعداد كارها كمتر است و امكان ايجاد بيكاري تعمدي (خاموشي دستگاه‌ها) فراهم شده است. تحت اين سناريو با بهره‌گيري از نتايج حاصله از مدل رياضي، امكان كاستن هزينه‌هاي برق تا 60% محقق شده است. به طور خلاصه، در اين رساله ضمن معرفي يك مسئله نو در ادبيات زمان‌بندي، انواع رويكردها به جهت استخراج جواب‌هاي بهينه محلي و جهاني مورد استفاده قرار گرفته است. رويكردهاي برنامه‌ريزي رياضي تك‌هدفه و چندهدفه، ارائه الگوريتم‌هاي ابتكاري مبتني بر روش‌هاي حريصانه، ارائه الگوريتم‌هايي براي محاسبه حدود پايين، ارائه الگوريتم شاخه و كران جهت استخراج جواب بهينه جهاني به همراه قوانين تسلط و محاسبه حد پايين، ارائه الگوريتم‌هاي فراابتكاري مبتني بر روش ژنتيك، جستجوي همسايگي و جستجوي جمعي و در نهايت ارائه رويكردهاي مبتني بر روش لكسيكوگرافي براي بهبود در مقدار تابع هدف، همگي از جمله تكنيك‌ها و رويكردهاي اتخاذ شده در اين رساله است.

192436

دانشگاه علم و صنعت ايران

دكتر مهدوي مزده

مهندسي صنايع

دكتر مهدي حيدري