مساله پذيرش سفارش و زمان بندي مبتني بر تئوري بهينه سازي استوار در سيستم هاي ساخت براسا س سفارش

STUDENT

DEGREE

YEAR

Increasing global competition, lower profit margins, higher customer expectations, shortened product lifecycles, synchronized supply chains, etc. are driving most firms towards make-to-order (MTO) operations. Acceptance or rejection of incoming orders by sale department and scheduling of accepted orders by production department are one of the main problems in the systems. However, it is common in many industrial practices that the order acceptance and scheduling decisions are made separately by the sales department and the production department, respectively. The integrated Order Acceptance and Scheduling (OAS) problem has received increasing attention in recent years. Several researchers proposed different models and approaches by considering diverse conditions and assumptions for the problem. In this thesis, the OAS problem in a non-identical parallel machines environment is considered. Three Mixed-Integer Linear Programming (MILP) formulations to maximize profit based on specific assumptions are presented. The main assumption in the most researches is that the parameters of the models are deterministic, while uncertainty is innate characteristic of production systems. There are some approaches to deal with uncertainty of parameters such as stochastic programming and fuzzy programming. In this thesis, the setbased Robust Optimization (RO) approach to deal with uncertainty of some parameters such as revenues and processing times is considered. The approach does not need to identity distribution and membership function of an uncertain parameter similar to stochastic programming and fuzzy programming, respectively. In this thesis, to obtain less conservative solutions, the globalized robust optimization approach and the robust optimization approach with multiple uncertainty sets are extended. Simulation studies demonstrated that the extended robust approaches are provided slightly better results in comparison with conventional robust counterpart. In the globalized robust optimization approach assumed that the normal range of the perturbation is an intersection of a box and a polyhedral and the robust counterpart formulation of a constraint with uncertain coefficients is presented. Moreover, box and polyhedral uncertainty sets are considered to extend the robust optimization approach with multiple uncertainty sets and is presented the robust counterpart of a constraint with uncertain coefficients for different cases. Moreover, a method to estimate the maximum number of uncertain parameters that can take value from lth uncertainty set and a probability bound of constraint violation is introduced. On the other hand, the proposed mathematical models and their robust counterparts are computationally intractable and solving them is only possible for small problems (10 orders and 6 machines). Therefore, Nested Partitions (NP), Benders Decomposition (BD), Lagrangian Relaxation (LR) and Column and Constraint Generation (C CG) algorithms are used. By extension the algorithms, possibility of solving medium and large sizes problems (40 orders and 6 machines) is provided.

چکيده امروزه به‌دليل رقابت‌هاي جهاني، حاشيه سود کمتر، سطح بالاي انتظارات مشتريان، سيکل عمر کوتاه محصولات، زنجيره‌هاي تأمين هماهنگ و ... اکثر شرکت ها در حال حرکت به سمت سيستم هاي عملياتي ساخت بر اساس سفارش (MTO) هستند. يکي از مسائل مهم در اين سيستم‌ها، پذيرش يا رد سفارشات ورودي توسط بخش فروش و برنامه ريزي و زمانبندي توليد سفارشات پذيرفته شده توسط بخش توليد است. به طور سنتي در اکثر شرکت ها اين دو تصميم به طور جداگانه و بر پايه اطلاعات کلي توسط دو بخش فروش و توليد اتخاذ مي‌گردد. در سال‌هاي اخير تصميم گيري همزمان و يکپارچه پذيرش سفارش و زمانبندي (OAS) مورد توجه قرار گرفته است که اثر مطلوبي بر افزايش سوددهي سازمان ها داشته است. پژوهشگران متعددي با لحاظ نمودن فرضيات متنوع و در نظر گرفتن شرايط متفاوت، مدل ها و رويکردهاي متعددي را براي اين مسأله پيشنهاد داده اند. در اين رساله، مسأله يکپارچه پذيرش سفارش و زمانبندي در محيط ماشين‌هاي موازي متفاوت به دليل کاربرد فراوان آن مورد توجه قرار گرفته است و بر پايه فرضيات مشخص سه مدل‌ برنامه‌ريزي خطي عدد صحيح مختلط (MILP) به منظور بيشينه نمودن سود ارائه گرديده است. فرض اصلي در بسياري از تحقيقات گذشته، قطعي بودن مشخصه ها و پارامترهاي سيستم است، در حالي‌که عدم قطعيت پارامترهائي نظير زمان‌‌هاي پردازش، درآمدها و ... جزء لاينفک سيستم‌هاي توليدي است. از اينرو، در اين رساله از ميان رويکردهاي موجود در ادبيات موضوع براي مواجهه با عدم قطعيت پارامترها نظير برنامه‌ريزي احتمالي، برنامه‌ريزي فازي و... به رويکرد بهينه‌سازي استوار مبتني بر مجموعه‌ عدم قطعيت توجه شده است. در اين رويکرد، برخلاف رويکرد برنامه‌ريزي احتمالي نيازي به شناسائي توزيع پارامترها و يا برخلاف برنامه‌ريزي فازي نيازي به تعيين تابع عضويت پارامترهاي غيرقطعي نمي‌باشد. در اين راستا و به منظور دستيابي به جواب‌هاي استوار با سطح محافظه‌کاري کمتر، دو رويکرد بهينه‌سازي استوار جهاني و بهينه‌سازي استوار با مجموعه‌هاي عدم قطعيت چندگانه توسعه داده شده است و نتايج مطلوبي در مقايسه با رويکردهاي متداول بهينه‌سازي استوار حاصل شده است. در توسعه رويکرد بهينه‌سازي استوار جهاني، فرض شده که ناحيه نرمال عدم‌قطعيت، از اشتراک دو مجموعه جعبه‌اي و چندوجهي تشکيل گرديده است. از اينرو فرموله‌بندي هم‌‌ارز استوار، براي يک محدوديت خطي با ضرايب غيرقطعي در سمت چپ ارائه شده است. همچنين با هدف توسعه رويکرد بهينه‌سازي استوار با مجموعه‌هاي عدم‌قطعيت چندگانه، با در نظر گرفتن اين مجموعه‌ها به صورت جعبه‌اي و چندوجهي، اقدام به ارائه فرموله‌بندي‌هاي هم‌ارز استوار براي محدوديت خطي با پارامترهاي غيرقطعي در سمت چپ شده است. به علاوه، روشي براي محاسبه حداکثر تعداد پارامترهاي غيرقطعي که در يک مجموعه عدم قطعيت مقدار مي‌پذيرند و يک حد بالا براي احتمال تغيير محدوديت با ضرايب غيرقطعي ارائه گرديده است. مدل‌هاي رياضي پيشنهادي و هم‌ارزهاي استوار آنها، داراي پيچيدگي‌هاي محاسباتي فراوان بوده و حل آنها فقط براي مسائل کوچک با10 سفارش و 6 ماشين امکان‌پذير بوده است. از اينرو، توسعه الگوريتم فرا ابتکاري تفکيک‌سازي تو در تو (NP)، الگوريتم‌هاي دقيق تجزيه بندرز (BD)، آزادسازي لاگرانژين (LR) و توليد ستون و سطر (C CG) مورد توجه قرار گرفت. در راستاي توسعه الگوريتم NP، اقدام به معرفي الگوريتم تفکيک‌سازي دروني براي نمونه‌برداري در تفکيک‌هاي مختلف شده است. همچنين با معرفي چند لم و به تبع آنها لحاظ نمودن برش‌هاي مناسب و بکارگيري روش‌هاي ابتکاري براي دستيابي به يک جواب شدني از جواب نشدني، سرعت همگرائي الگوريتم‌هاي BD، LR و C CG ارتقا يافته و امکان حل مسائل در ابعاد متوسط و بزرگ با40 سفارش و 6 ماشين فراهم گرديده است.