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

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 ماشین فراهم گردیده است.