20068

۲۰۰۶۸

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

دكتري

مهندسي صنايع

۹۲-۹۷

۱۳۹۷/۱۰/۱۸

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

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

صنايع

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

1397/12/05

Flowshop Scheduling with Time-dependent Costs and Due Date

2/24/2019 12:00:00 AM

This thesis studies two-machine flowshop scheduling problem under time-dependent electricity tariffs and due dates, in which electricity prices may vary from time to time throughout a day. The main issue is to assign a set of jobs to available time slots with different electricity prices so as to minimize the total resource cost required for processing the jobs and total tardiness. Firstly the problem is studied only with one objective of total resource costs. The main contribution of this work is two-fold. First, a new continuous-time mixed-integer linear programming (MILP) model is proposed for the problem. Second, a two-stage greedy heuristic is developed. Computational experiment on randomly generated instances demonstrates that the greedy algorithm can improve objective function up to 40 percent. The algorithm can be applied by production managers to scheduling jobs on a flowshop under time-of-use (TOU) electricity tariffs to save electricity costs. Secondly, multiobjective modeling is suggested. In the multiobjective approach, two-machine permutation flow shop scheduling is studied through integer linear programming (MILP) model as well as lexicographic approach focusing on two objectives of total tardiness and total energy cost under time-of-use energy tariffs. MILP model is commonly used for solving small-size problems; this study, however, suggests a heuristic algorithm to tackle large-size instances with the aim of minimizing total energy cost of a given sequence while simultaneously keeping total tardiness at the lowest value. The main idea behind this algorithm is to shift the start time of jobs forward in order to find a schedule with lowest possible energy cost. The results that are derived from a random sample consisting of 800 generated problems for this study show that 29 to 58 percent of such problems have improved in their total energy cost value through inserting some idle time in the middle. Remarkably, the improvement degree has been up to 10% in some cases.