A Two-dimensional Fix and Optimize Algorithm to Solve the Flexible Manufacturing System Lot-sizing with Co-production Problem

Document Type : Persian Research paper

Authors

Department of Industrial Engineering, Faculty of Engineering, Payame Noor University, Tehran, Iran

Abstract

Purpose: In this paper, the flexible manufacturing system lot-sizing with the co-production problem is modeled. It is also simplified using the relationships between variables. One of the common methods for solving such problems is the fix and optimize algorithm, which is generally used in a one-dimensional approach. Also, a two-dimensional fix and optimize algorithm is applied to solve the problem. This algorithm is compared with two common algorithms using simulated data series.
 
Design/methodology/approach: In this paper, Flexible Manufacturing System Lot-sizing with Co-production problem is modeled using mixed-integer programming. The production of products in this flexible system varies with the change of production mode, and a different mixture of products is produced for each production mode. Also, the planning interval includes T periods, and the demand for each product in each given period is constant. In each period, a fixed setup cost is added to the production and maintenance variable costs, if production occurs. The objective function of the model minimizes the sum of fixed setup costs and production and maintenance variable costs of inventory in each period and each production mode. Problem constraints include setup forcing constraints, inventory balance constraints, initial inventory constraints, co-production constraints, production mode constraints, non-negative variables constraints, and binary variable constraints. Among the methods proposed to solve this group of problems, the fix and optimize method is one of the most effective and general methods. The basic idea of ​​this approach is that due to the difficulty of solving the main problem with a longtime interval, a problem with a shorter time interval called the time window is solved instead. Except for the variables in the time window, other integer variables are considered continuous variables, so the resulting problem is easier to solve. In the following steps, the time window variables in the current step are assumed constant, and this repetition will continue until the end of the desired periods. Time windows can be considered with or without overlap. In this paper, two innovative one-dimensional fix and optimize algorithms based on time and production mode variables and a new two-dimensional algorithm based on time and production mode variables are applied to solve the model using simulated data at three levels of small, medium, and large scales. MATLAB 2016 software is used to code the algorithms of this study, and numerical calculations are performed by a personal computer with Intel®Core™i3-7100@3.90GHz processor and 8 GB RAM.
 
Findings: The research results indicated the significant superiority of the proposed two-dimensional algorithm in terms of response time over the two one-dimensional algorithms. It is important to note that in terms of the quality of the answer in the studied problems, no significant difference was observed.
 
Research limitations/implications: In many real cases, due to the fact that the cost parameters in different production situations (e.g., the oil, gas, and petrochemical downstream industries) are close to each other and in practice, determining production conditions in accordance with other parameters such as demand is independent of production costs, the efficiency of the proposed algorithm will be more visible in this article. The most important limitation in this study was the lack of real data for a flexible production system with correlated products, which is why simulated data were used to validate the model and test the proposed algorithms.
 
Practical implications: In the future, researchers can use real-time case studies based on the proposed model and algorithms in this paper. They can also add other features to the model, such as limited production capacity and allowable shortages. Manufacturing plants that have features similar to this study can benefit from the findings to optimize production costs.
 
Social implications - Applying the results of this research can increase the productivity of production units and the use of non-renewable energy resources.
 
Originality/value: In this paper, a mathematical model (MILP) was proposed for the Flexible Manufacturing System Lot-sizing with Co-production problem. In addition, an innovative two-dimensional fix and optimize algorithm was developed.

Keywords

Main Subjects

Full Text

۱-مقدمه

یکی از شایع‌ترین و مهم‌ترین مسائل همیشگی در بیشتر صنایع، مدیریت موجودی‌هاست. مغازه‌های خرده‌فروشی با مقادیر زیادی از کالاها انباشته شده‌اند؛ صنایع تولیدی نیز، با موجودی‌های کلانی از مواد خام، محصولات نیم‌ساخته و کالاهای نهایی و همچنین: تجهیزات، ماشین‌آلات، قطعات یدکی و نیروی انسانی مواجه‌اند. به‌طورکلی، علت وجود موجودی‌ها، عدم تعادل بین تأمین یک کالا در یک محل با فروش یا مصرف آن است. این عدم تعادل می‌تواند به علل متعددی همچون فنی، اقتصادی، اجتماعی و طبیعی بروز کند. چهار سؤال اساسی که دربارۀ موجودی‌ها مطرح است، عبارت است از: چه آیتم‌هایی در سیستم باید ذخیره شود؟ این آیتم‌ها کجا باید ذخیره شود؟ چه مقدار از هر آیتم و در چه زمانی باید سفارش داده یا تولید شود؟ در بیشتر تحقیقاتی که درزمینۀ مدیریت موجودی انجام می‌شود، پژوهشگران با ارائۀ یک مدل ریاضی از مسئله، به دنبال یافتن راه حلی برای پاسخ به یک یا چند سؤال از سؤالات مذکوراند (موکستادت و اسپارا[i]، ۲۰۱۰).

 در برخی از واحدهای تولیدی، با تولید یک محصول، سایر محصولات نیز برای الزامات شیمیایی یا فیزیکی در فرایند تولید، باید به‌اجبار تولید شود که به آن تولید همبسته[ii] گفته می‌شود. این نوع تولید می‌تواند در محیط‌های صنعتی با فنّاوری بالایا پایین اتفاق بیفتد که می‌توان به صنایع شیشه‌سازی، نیمه‌هادی‌ها و فرآورده‌های دامی اشاره کرد؛ برای مثال، در صنعت شیشه، جریان یکنواختی از شیشه به اندازه‌های مختلف بریده می‌شود که هر اندازۀ آن، مستقل با بازار به‌خصوص است. ویژگی این صنعت ایجاب می‌کند برای تولید یک محصول با اندازۀ خاص برای حداکثر استفاده از مواد اولیه، باید محصولات دیگری به‌صورت هم‌زمان تولید شود. در صنعت تولید فرآورده‌های دامی نیز، برای تولید یک فرآوردۀ گوشتی (مانند گوشت) به‌اجبار، باید میزان مشخصی از محصولات دیگر مثل پشم و پوست را نیز تولید کرد (کالای و تاسکین[iii]، ۲۰۲۱؛ ویدمان[iv] و همکاران، ۲۰۱۵).

انعطاف‌پذیری تولید، پاسخی اساسی برای بقا در بازارهای امروزی است که دارای ویژگی‌هایی ‌همچون زمان تحویل کوتاه، فشار هزینه‌ها و تغییرات متناوب در تقاضاهاست. اگرچه انعطاف‌پذیری، یک گزینۀ استراتژیک مهم برای شرکت‌های امروزی است، از طرف دیگر، انعطاف‌پذیرکردن یک سیستم تولیدی، به سرمایه‌گذاری‌های بسیاری نیاز دارد؛ بنابراین، تصمیم دربارۀ میزان انعطاف‌پذیری در یک سیستم، نیازمند بررسی کاملی از فواید و مضرات آن با یک نگاه جامع و همه‌جانبه است. نکتۀ شایان ذکر این است که معمولاً بین بهره‌وری و انعطاف‌پذیری، رابطۀ معکوس وجود دارد و باید با توجه به نیاز سیستم با سبک‌وسنگین‌کردن فواید و مضرات، به ‌میزان مناسبی از انعطاف‌پذیری رسید (تولیو، ۲۰۰۸). سیستم تولید انعطاف‌پذیر[v](FMS)، به چیدمانی از ماشین‌ها گفته می‌شود که با یک سیستم حمل‌ونقل به یکدیگر مرتبط شده‌اند و با یک سیستم کامپیوتری کنترل می‌شوند. به‌عبارت‌دیگر یک سیستم تولید انعطاف‌پذیر، مجموعه‌ای از ایستگاه‌های کاری است که با یک سیستم حمل نقل و انبارش خودکار به یکدیگر متصل شده‌اند و توانایی پاسخگویی به الگوهای متفاوت تقاضا را دارند و همگی اجزای آن با یک سیستم کنترل کامپیوتری یکپارچه، کنترل می‌شوند (شیواناد[vi] و همکاران، ۲۰۰۶).

از پژوهش‌های انجام‌شده در سالیان اخیر، در حوزۀ تعیین اندازۀ انباشته عبارت است از: تعیین اندازۀ انباشته با بازتولید[vii] (کانها[viii] و همکاران، ۲۰۱۹؛ روشنی و همکاران،۲۰۱۷)، تعیین اندازۀ انباشته با پارامترهای تصادفی (تاس[ix] و همکاران، ۲۰۱۹؛ توقف-گیگلو و مینر[x]، ۲۰۲۰؛ گیکول و چنگ، ۲۰۱۸؛ ون پلت و فرانسو[xi]، ۲۰۱۸؛ خسروی و میرمحمدی،1397)، تعیین اندازۀ انباشته با پارامترهای فازی (غلامرضایی و خادمی زارع، 1394؛ جوهری و لاکسونو[xii]، ۲۰۱۷؛ ابراهیمی و امیری، 1396)، تعیین اندازۀ انباشته با ماشین‌های موازی (وو[xiii] و همکاران، ۲۰۱۸؛ دی آرماس و لاگونا[xiv]، ۲۰۲۰؛ وینسنت[xv] و همکاران، ۲۰۲۰؛ کاروالیو و ناسیمنتو[xvi]، ۲۰۲۱)، تعیین اندازۀ انباشته با محدودیت‌های زمان راه‌اندازی (بن عمار[xvii] و همکاران، ۲۰۲۰؛ بیلی[xviii] و همکاران، ۲۰۱۸؛ گورن و تونالی[xix]، ۲۰۱۸؛ کاروالیو و ناسیمنتو[xx]، ۲۰۱۸)، تعیین اندازۀ انباشته با محدودیت‌های سطح خدمت[xxi]، سفارش دسته‌ای[xxii]، مسیریابی (استادلر و میسترینگ[xxiii]،۲۰۱۹؛ کاردونا-والدز[xxiv]،۲۰۲۰، میرزایی و همکاران، ۲۰۱۱) و اندازۀ انباشتۀ چندسطحی با درنظر گرفتن موجودی تخریب شدنی و هزینه‌های دفع (وجدانی و دولتی، 1394).

انعطاف‌پذیری در سیستم‌های تولیدی، مفهوم گسترده‌ای است و معنای آن در زمینه‌های مختلف تغییر می‌کند. پراساد و جیسوال[xxv] (۲۰۱۹)، در مقاله‌ای این موضوع را مرور کرده‌ و در بررسی تعاریف ارائه‌شده برای انعطاف‌پذیری به «سازگاری سیستم با عدم قطعیت‌ها»، «توانایی یک سیستم تولیدی برای مقابله با وضعیت متغیر یا بی‌ثباتی ناشی از محیط» ، «سرعت و سهولت واحدهای تولیدی در پاسخ به تغییرات وضعیت بازار»، «توانایی سیستم برای تنظیم سریع هرگونه تغییر در فاکتورهای مربوط، مانند محصول، فرآیند، دفعات و خرابی ماشین‌آلات» اشاره کرده‌اند؛ ولی تعریف «توانایی تغییر یا واکنش با به‌کارگیری زمان، تلاش، هزینه یا عملکرد کمتر» را دارای جامعیت بیشتری دانسته‌اند. ایماراقی[xxvi] (۲۰۰۵) با بررسی پژوهش‌های انجام‌شده در حوزۀ انعطاف‌پذیری به ده نوع انعطاف‌پذیری، شامل: انعطاف‌پذیری ماشین‌آلات، انعطاف‌پذیری به‌کارگیری مواد، انعطاف‌پذیری عملیات، انعطاف‌پذیری فرآیندی، انعطاف‌پذیری محصول، انعطاف‌پذیری مسیریابی، انعطاف‌پذیری حجم (تولید)، انعطاف‌پذیری گسترش، انعطاف‌پذیری برنامۀ کنترل و انعطاف‌پذیری تولید (محصولات) پرداخته است. یک سیستم تولید انعطاف‌پذیر، همان‌طور که از نام آن مشخص است، انعطاف‌پذیری بسیار زیادی دارد. به‌طورکلی، یک سیستم انعطاف‌پذیر تولیدی عبارت است از: مجموعه‌ای از ماشین‌آلات خودکار که در اتصال با سیستم‌های خودکار به‌کارگیری مواد تولیدی، سیستم ذخیره‌سازی و انبارداری است و با یک سیستم کامپیوتری یکپارچه کنترل می‌شود (گروور[xxvii]، ۲۰۲۰).

مسئلۀ تعیین اندازۀ انباشته برای محصولات همبسته[xxviii] را آگرالی[xxix] (۲۰۱۲) بررسی کرد. او برای مسئلۀ تعیین اندازۀ انباشتۀ پویا، بدون محدودیت ظرفیت با لحاظ محصولات همبسته، یک مدل ترکیبی عدد صحیح خطی(MIP) ارائه کرد. به‌تازگی سوزانی[xxx] و همکاران (۲۰۲۰)، در پژوهشی مسئلۀ تعیین اندازۀ انباشته با محصولات همبسته و محدودیت‌های انبار تک‌محصولی را بررسی کرده‌اند.

با توجه به پیشرفت سیستم‌های کنترل کامپیوتری در سال‌های اخیر و به‌کارگیری آن‌ها در کارخانه‌های بزرگ شیمیایی، همچون پالایشگاه‌های نفت که دو ویژگی انعطاف‌پذیری و همبستگی محصولات را با هم دارد، برای بهینه‌کردن هزینه‌های زیاد تولید در این صنایع، نیاز به مدل‌سازی و ارائۀ راه‌حل‌های عملی برای بهینه‌کردن هزینه‌های تولیدی را بیش‌ازپیش بااهمیت کرده است. مرور پیشینۀ موضوع، نشان می‌دهد با وجود تحقیقات گسترده درزمینۀ مسئلۀ تعیین اندازۀ انباشته، به لحاظ‌کردن دو ویژگی هم‌زمان انعطاف‌پذیری و همبستگی محصولات تولیدی در مسئله، چندان توجهی نشده است.

محققان مختلف نشان داده‌اند که مسائل تعیین اندازۀ انباشته جزء مسائل NP-Hard است (کانا[xxxi] و همکاران، ۲۰۲۱؛ دیووتو[xxxii] و همکاران، ۲۰۲۱ و بوو[xxxiii] و همکاران، ۲۰۲۱) و با افزایش ابعاد مسئله در این‌گونه مسائل، روش‌های قطعی کارایی خود را از دست داده است و باید از روش‌های ابتکاری و فراابتکاری کمک گرفت. یکی از عمومی‌ترین روش‌های ابتکاری که محققان برای حل مسائل این حوزه در سالیان گذشته به کار گرفته‌اند، روش ابتکاری ثابت‌سازی-بهینه سازی[xxxiv] است که در این پژوهش علاوه بر اجراکردن این روش به‌صورت تک‌بعدی، یک الگوریتم دوبعدی اجرا شده و کیفیت جواب‌های این الگوریتم با الگوریتم‌های تک‌بعدی مقایسه شده است. در ادامه، ضمن تشریح مبانی نظری مسئلۀ تعیین اندازۀ انباشته، مدل ریاضی مسئلۀ تعیین اندازۀ انباشته برای یک سیستم انعطاف‌پذیر تولیدی (FMS)، بدون محدودیت ظرفیت ارائه شده که محصولات آن با یکدیگر همبسته است[xxxv] (FMS-ULSP-Co). پس‌ازآن، مدل ارائه‌شده با سه الگوریتم اشاره‌شده به کمک داده‌های شبیه‌سازی‌شده حل و نتایج حاصل، تجزیه‌وتحلیل شده است.

 

۲-مبانی نظری مسائل تعیین اندازۀ انباشته

 پیچیدگی مسائل تعیین اندازۀ انباشته، به ویژگی‌هایی مثل بازۀ زمانی برنامه‌ریزی، تعداد سطوح، محدودیت منابع تولیدی، نوع تقاضا و ساختار راه‌اندازی بستگی دارد. در پیشینۀ موضوع، مدل‌های تعیین اندازۀ انباشته، دراساس به دو دستۀ مدل‌های ظرف زمانی بزرگ[xxxvi] و ظرف زمانی کوچک[xxxvii] تقسیم می‌شود. یکی از مسائلی که به‌جهت داشتن مفروضات اساسی کم، محققان بسیار به آن توجه کرده‌اند، مسئلۀ تعیین اندازۀ انباشته با محدودیت ظرفیت[xxxviii] (CLSP) نامیده می‌شود. یکی از فرضیات این مسئله بیان می‌کند که در هر پریود حداکثر، کلیۀ محصولات مختلف می‌تواند تولید شود. به این دلیل، به چنین بازۀ زمانی، بازۀ زمانی یا ظرف زمانی بزرگ گفته می‌شود. به‌علاوه، توالی تولید محصولات مختلف، توسط مسئلۀ تعیین اندازۀ انباشته با محدودیت ظرفیت تعیین نمی‌شود. همچنین، وضعیت راه‌اندازی (Setup state) در مرزهای بازه‌های زمانی مشخص نیست؛ بنابراین، آخرین آیتم در بازۀ زمانی t و اولین آیتم بازۀ زمانی 1t+ مشخص نیست. درنهایت، یک انباشتۀ تولید نمی‌تواند چندین بازۀ زمانی را به‌جهت ظرفیت محدود هر دوره پوشش دهد. اگرچه مسئلۀ تعیین اندازۀ انباشته با محدودیت ظرفیت نمی‌تواند توالی انباشته‌های تولیدی را تعیین کند؛ اما یک مدل اساسی برای نمایش خصوصیات کم‌وبیش عمومی مدل‌های زمان‌بندی و تعیین اندازۀ انباشتۀ هم‌زمان با بازه‌های زمانی بزرگ ارائه می‌دهد (کانگ[xxxix]، ۲۰۲۰).

 برخلاف CLSP، مسئلۀ زمان‌بندی و تعیین اندازۀ انباشتۀ گسسته[xl](DLSP)، زمان‌بندی و تعیین اندازۀ انباشتۀ هم‌زمان را اجازه می‌دهد. بر اساس این ساختار فلشمن[xli] (۱۹۹۰)، این مدل را مسئلۀ زمان‌بندی و تعیین اندازۀ انباشتۀ گسسته نامید که در آن مقادیر انباشته، فقط یک مقدار صحیح چندگانه از مقادیر تولید در یک دورۀ زمانی کامل است. ازآنجایی‌که DLSP فقط راه‌اندازی (تولید) یک آیتم در هر پریود را اجازه می‌دهد، این امر موجب می‌شود که به‌صورت خودکار، توالی انباشته‌های تولیدی تعیین شود؛ اما این محدودیت فقط در وضعیتی پذیرفتنی است که فاصله‌های زمانی به اندازۀ کافی کوتاه باشد. علت اینکه DLSP را مدل ظرف زمانی کوتاه می‌نامند نیز همین نکته است. بنابر تعریف همۀ مدل‌های ظرف زمانی کوتاه در یک بازۀ زمانی، حداکثر یک تغییر وضعیت راه‌اندازی را اجازه می‌دهد.

مسئلۀ عمومی زمان‌بندی و تعیین اندازۀ انباشته[xlii](GLSP) که فلشمن و مایر[xliii] (۱۹۹۷) ارائه دادند، یکی از اولین مدل‌هایی است که ظروف زمانی کوچک با طول متغیر را اجازه می‌دهد؛ بنابراین، یک ساختار زمانی دوسطحی تعریف می‌شود، دومرتبه محدودۀ زمانی برنامه‌ریزی به T ظرف زمانی تقسیم می‌گردد که ماکروپریود نامیده می‌شود؛ اما در این مدل، هر ماکروپریود به S ظرف زمانی کوچک تقسیم می‌گردد که میکروپریود نامیده می‌شود (شکل ۱).

 

شکل ۱- GLSP با دو ساختار زمانی

 

به‌طورکلی، مسائل مهم برنامه‌ریزی زنجیرۀ تأمین، به‌صورت یک مسئلۀ MIP مدل‌سازی می‌شود؛ بااین‌حال، الگوریتم‌های قطعی حل این مسائل، برای یافتن جواب بهینه برای مسائل در اندازۀ بزرگ، در یک زمان محاسباتی پذیرفتنی، کارایی لازم را ندارد. برای غلبه بر این محدودیت، روش‌های ابتکاری برای حل مسائل MIP امیدوارکننده، ظاهر شده‌ است (سل و بیلگن[xliv]، ۲۰۱۴). یک دسته از راه‌حل‌های ابتکاری که محققان برای مسائل تعیین اندازۀ انباشته و زمان‌بندی تولید ارائه کرده‌اند، راه‌حل‌های ابتکاری با منظور خاص[xlv] است که بیشتر برای مسائل تعیین اندازۀ انباشتۀ چندآیتمی تک‌سطحی ارائه شده‌ است. این راه حل‌های ابتکاری، یک دستورالعمل پریود به پریود را برای یافتن یک جواب ارائه می‌دهد و درصورتی‌که جواب ساخته‌شده امکان‌پذیر نباشد، یک مسیر بازخورد را برای تبدیل جواب، به یک جواب امکان‌پذیر ارائه می‌دهد (شولز[xlvi]،۲۰۱۱).

 از بین روش‌هایی که برای حل این دسته از مسائل ارائه‌شده، روش ثابت‌‌سازی- بهینه‌سازی یکی از مؤثرترین و عمومی‌ترین روش‌هاست. ایدۀ اساسی این رویکرد، این نکته را بررسی می‌کند که با توجه به مشکل‌بودن حل مسئلۀ اصلی با بازۀ زمانی طولانی، به‌جای آن یک مسئله با بازۀ زمانی کوتاه‌تر حل می‌گردد که پنجرۀ زمانی[xlvii] نامیده می‌شود. به‌جز متغیرهای درون پنجرۀ زمانی، سایر متغیرها از قید عدد صحیح‌بودن آزاد شده و متغیرهای پیوسته در نظر گرفته‌ شده است؛ بنابراین، مسئلۀ حاصل ساده‌تر حل می‌شود. در مراحل بعدی، متغیرهای پنجرۀ زمانی مرحلۀ فعلی، ثابت فرض می‌شود و این تکرار تا پایان بازۀ زمانی مدنظر ادامه می‌یابد. پنجره‌های زمانی را می‌توان با همپوشانی[xlviii] یا بدون همپوشانی[xlix] در نظر گرفت. تحقیقات نشان می‌دهد انتخاب پنجره‌های زمانی با همپوشانی، پاسخ‌های بهتر ارائه می‌کند؛ ولی زمان حل مسئله را نیز افزایش می‌دهد (فدرگرون[l] و همکاران، ۲۰۰۷).

روش ابتکاری ثابت‌سازی-بهینه‌سازی، معماری ساده و شفاف دارد و برای بسیاری از مسائل پیچیدۀ برنامه‌ریزی تولید، تعیین اندازۀ انباشته و مسائل زمان‌بندی در پیشینۀ موضوع، روشی کارآمد و مؤثر شناخته می‌شود. در روش ثابت‌سازی-بهینه‌سازی، استراتژی‌های مختلفی برای تجزیۀ مسئله بر پایۀ زمان، محصول و یا منابع می‌تواند مطرح باشد. هلبر و ساهلینگ[li] (۲۰۱۰)، روش‌های مختلف تجزیه در روش ثابت‌سازی_ بهینه‌سازی را برای حل مسئلۀ CLSP چندسطحی مطرح کرده‌اند. پژوهش‌ ژیائو[lii] و همکاران (۲۰۱۳)، روش ترکیبی رهاسازی-ثابت‌سازی[liii] با روش ثابت‌سازی-بهینه سازی و تجزیۀ زمان برای مسائل CLSP را بررسی کرده‌اند که شامل زمان آماده‌سازی تجهیزات وابسته به توالی است. ترکیبی از الگوریتم ژنتیک و الگوریتم ثابت‌سازی_ بهینه‌سازی، در تحقیقات گورن[liv] و همکاران (۲۰۱۲) و تولدو[lv] و همکاران (۲۰۱۳)، برای حل مدل تحقیق به کار رفته است. از الگوریتم‌های ابتکاری ثابت‌‌‌سازی–بهینه‌سازی مختلف، برای حل همین مسئله برای محصولات فاسدشدنی نیز در پژوهش علیپور و همکاران (۲۰۲۰) استفاده شده است.

 

۳-مدل پیشنهادی برای یک سیستم تولید همبستۀ انعطاف‌پذیر

فرض کنید که یک سیستم تولیدی، خانواده‌ای از محصولات را که با k اندیس‌گذاری می‌شود، به‌عنوان محصولات همبسته تولید می‌کند. در این سیستم تولیدی، محصول اصلی (برای سادگی مدل، محصول صفر، محصول اصلی در نظر گرفته می‌شود) و چندین محصول دیگر به‌عنوان محصول همبسته (محصولات یکم تا Kام) به‌نسبت  تولید می‌شود. تولید محصولات در این سیستم انعطاف‌پذیر، با تغییر وضعیت تولید[lvi]، متغیر است و به ازای هر یک از وضعیت‌های تولیدی m=1,…T، نسبت متفاوتی از محصولات تولید می‌شود. همچنین فرض کنید بازۀ برنامه‌ریزی، شامل T پریود است و تقاضای هر محصول (آیتم) در هر پریود معین است و برای محصول kام در پریود tام با  نشان داده می‌شود. در هر پریود زمانی یک هزینۀ راه‌اندازی ، درصورتی‌که تولیدی اتفاق بیفتد به هزینه‌ها اضافه می‌‌شود. علاوه بر این، هزینۀ متغیر تولید و نگهداری هر محصول kام در پریود t، به‌ترتیب با  و  نشان داده می‌شود. برای ساده‌سازی، مقدار تولید محصول اصلی در هر پریود t و هر وضعیت تولید m را  در نظر می‌گیریم. بدیهی است، نسبت تولید برای محصول اصلی در هر وضعیت تولید  فرض می‌شود. لیست علائمی که در ادامه استفاده می‌شود، عبارت است از:

 

اندیس‌ها

k=۰, …,K    

t=۱,…,T

m=۱,…,M  

محصولات

بازه‌های زمانی 

وضعیت‌های تولید

 

داده‌ها

 

تقاضای محصول k در پریود t

 

هزینۀ راه‌اندازی در پریود t در حالت تولید m

 

هزینۀ تولید هر واحد از محصول k در پریود t در وضعیت تولید m

 

هزینۀ نگهداری هر واحد از محصول k در پریود t

 

تقاضای محصول k بین پریود i و t درحالی‌که

 

ماکزیمم تقاضای کل همۀ محصولات بین پریود ۱ و t یا به‌عبارتی:
}

 

مقدار تولید محصول k به همراه تولید یک واحد از محصول اصلی در حالت تولید m

با این فرضیات، وضعیت تولید، مقدار و زمان تولید محصولات به‌گونه‌ای است که ضمن برآورده‌کردن تقاضاها، هزینه‌های کل تولید، شامل هزینه‌های راه‌اندازی، تولید و نگهداری را مینیمم کند، متغیرهای تصمیم مسئله است. متغیرهای تصمیم که در فرموله‌کردن مسئله استفاده می‌شود، عبارت است از:

 =۱، اگر راه‌اندازی در پریود t در وضعیت تولید m اتفاق بیفتد و در غیر این صورت صفر

  = مقدار تولید محصول k تولید شده در پریود t در وضعیت تولید m

= مقدار موجودی انبار محصول k در انتهای پریود t

همان‌طور که در بالا آمده است، متغیر  تقاضای محصول k از پریود i تا پریود t است یا به‌ عبارت ‌دیگر . با این اوصاف، مسئله به‌صورت یک مسئلۀ برنامه‌ریزی خطی عدد صحیح ترکیبی به‌صورت زیر فرموله می‌شود:

(1)

 

(2)

 

(3)

 

(4)

 

(5)

 

(6)

 

(7)

   

 

تابع هدف (۱)، مجموع هزینه‌های ثابت راه‌اندازی هر پریود و هزینه‌های متغیر تولید و نگهداری موجودی را کمینه می‌کند. محدودیت‌های(۲) که محدودیت‌های اجبار راه‌اندازی (Setup forcing constraints) است، اطمینان می‌دهد که یک محصول k در یک حالت تولید m در پریود t، فقط زمانی که در آن پریود در حالت تولید، راه‌اندازی انجام شده باشد ( )، می‌تواند تولید شود ( ). محدودیت‌های (۳) اطمینان می‌دهد در هر پریود حداکثر، فقط یک حالت تولید راه‌اندازی می‏شود. محدودیت‌های (۴)، محدودیت‌های موازنۀ موجودی
(Inventory balance constraints) است که برای هر محصول در هر پریود تعریف می‌شود و محدودیت‌های (۵)، اطمینان می‌دهد که موجودی هر محصول در ابتدای دورۀ برنامه‌ریزی صفر فرض می‌شود. محدودیت‌های (۶)، رابطۀ بین محصول اصلی و محصولات همبسته را نشان می‌دهد و محدودیت‌های آخر (۷)، محدودیت‌های نامنفی‌بودن متغیرهای تصمیم و باینری است.

 

 

۱-۳-ساده‌سازی مدل پیشنهادی

با توجه به اینکه در هر یک از وضعیت‌های تولید، میزان تولید محصولات همبسته به محصول اصلی بستگی دارد، می‌توان با استفاده از محدودیت‌های (۶)، متغیرهای  برای k=1,…K را از مدل حذف کرد. با توجه به اینکه تولید محصول اصلی در هر پریود t و هر وضعیت تولید m،  است؛ بنابراین، میزان تولید سایر محصولات در هر پریود t و هر وضعیت تولید m برابر  خواهد بود که در تابع هدف و سایر محدودیت‌ها جایگزین می‌شود. با این اوصاف، مدل فوق به‌صورت زیر ساده‌سازی خواهد شد:

 

(1)

 

(2)

 

(3)

 

(4)

 

(5)

 

(6)

   

از رابطه‌های (۴) و (۵) به‌سادگی می‌توان نشان داد که

 

 

به کمک این رابطه تابع هدف مدل را می‌توان به‌صورت زیر نوشت:

 

 

 

با توجه به اینکه عبارت  مقدار ثابتی است، می‌توان تابع هدف را برای سادگی مدل، بدون این عبارت در نظر گرفت. فقط باید دقت کرد تابع هدف مدل جدید، مقدار هزینۀ کل را نشان نمی‌دهد و باید برای محاسبۀ هزینۀ کل پس از محاسبۀ جواب بهینه، این مقدار ثابت را نیز لحاظ کرد. همچنین با توجه به حذف متغیرهای موجودی از مدل، برای جلوگیری از ایجاد کمبود (موجودی منفی) محدودیت‌های جدیدی به مدل اضافه می‌شود. با این اوصاف مدل ساده‌شده به‌صورت زیر خواهد بود:

(1)

 

(2)

 

(3)

 

(4)

 

(5)

 

 

برای حل مدل فوق، دانستن برخی روابط بین پارامترها و متغیرهای مدل می‌تواند کمک کند تا راه‌حل‌های کاراتری برای حل مدل انتخاب شود. یکی از این پارامترها، پارامتر B در محدودیت‌های اجبار راه‌اندازی است. این محدودیت‌ها متغیرهای باینری و پیوسته را به هم ارتباط می‌دهد. توجه کنید برای سمت راست، باید یک مقدار به‌اندازۀ کافی بزرگ انتخاب شود (مقدار B در اغلب مدل‌ها M بزرگ خوانده می‌شود، در این مقاله برای تمایز با متغیر وضعیت تولید، B فرض می‌شود) که به‌صورت ناخواسته مقدار تولید را محدود نکند. از طرف دیگر، این مقدار باید تا حد ممکن کوچک انتخاب شود تا موجب عملکرد بهتر سالورهای برنامه‌ریزی ترکیبی (MIP-solver) استاندارد شود. مقدار منطقی برای B، برای هر یک از آیتم‌ها، مقداری است که حداکثر تقاضای تولید ممکن در آن پریود را اجازه دهد. حداکثر مقدار تقاضای هر آیتم در هر پریود، برابر با  است. البته چون B فقط به‌منظور اطمینان از تولید، درصورت راه‌اندازی در محدودیت‌ها قرار گرفته می‌شود، می‌توان برای تمامی محصولات آن را یکسان و مساوی } در نظر گرفت.

 

۴-الگوریتم‌های پیشنهادی حل مسئله

در این مقاله با تعریف و تبیین سه الگوریتم ابتکاری، براساس محدودسازی بر روی متحرک‌های t=1,…T، وضعیت‌های تولیدی m=1,…M و محصولات تولیدی k=0,…K؛ همچنین، یک روش تلفیقی با رویکرد محدودسازی دوبعدی بر روی زمان (T) و وضعیت تولیدی(M) که از روش بهینه‌سازی- ثابت‌سازی، در حوزۀ برنامه‌ریزی خطی عدد صحیح استفاده می‌کند به‌دنبال حل مسئلۀ تعیین اندازۀ انباشته در سیستم تولیدی انعطاف‌پذیر با ارائۀ محصولات همبسته خواهیم بود که مراحل انجام پیاده‌سازی و روش حل به شرح ذیل ارائه می‌شود:

الگوریتم الف: محدودسازی بر روی متحرک زمان در برنامه‌ریزی‌های تولید

روش‌های ابتکاری محدودۀ زمانی متحرک، معمولاً در محیط‌های دینامیک و به‌خصوص در مسائل تعیین اندازۀ انباشته و زمان‌بندی استفاده می‌شود. در برنامه‌ریزی تولید پویا، تقاضا به‌تدریج در محدودۀ زمانی برنامه‌ریزی پدیدار می‌شود. درحالی‌که، تخمین تقاضاهای پریودهای اولیه تا حدود زیادی دقیق است؛ تقاضاهای پریودهای پایانی تقریبی است. به همین دلیل در این مسائل، با آزادسازی پریودهای پایانی می‌توان پیچیدگی مسئله را کاهش داد. اگر مسائل تعیین اندازۀ انباشتۀ تولیدی و زمان‌بندی، یک زیرمجموعه‌ای از پریودهای اولیه، شامل تصمیمات همراه با جزئیات در نظر گرفته شود و در پریودهای بعدی فقط تصمیمات کلان (به‌عنوان مقادیر تولید) و یا آزادسازی متغیرها در این پریودها لحاظ شود، پیچیدگی محاسبات کاهش می‌یابد.

استفاده از این روش برای حل مسائل با مقیاس بزرگ، می‌تواند با جایگزینی متغیرهای پیوسته به‌جای متغیرهای باینری در پریودهای آخر، باعث کاهش چشمگیری در محاسبات شود. این رویکرد حتی زمانی مفید است که تمامی پارامترها به‌طورکامل شناخته شده باشد. مسئله، متغیرهای باینری کمتری دارد و متغیرهای تصمیم، به‌صورت متناوب و تکرار تعیین می‌شود. براساس چارچوب مرس و فونتون، هر مرحله از رویکرد تکرارشوندۀ محدودۀ برنامه‌ریزی، به سه بخش (ابتدایی، مرکزی و نهایی) تقسیم می‌‍شود. برای هر تکرار مشخص k.

بخش اول که 1-k پریود را شامل می‌شود، براساس تکرار قبلی الگوریتم همه یا قسمتی از مقادیر متغیرهای تصمیم، براساس استراتژی انجماد انتخاب‌شده، تخصیص داده می‌‍شود.

بخش مرکزی شامل پریود k است. برای این پریود، مسئله به‌صورت کامل در نظر گرفته می‌شود؛ در این بخش، همۀ متغیرهای باینری به‌صورت باینری در نظر گرفته می‌شود.

بخش پایانی که شامل پریودهای باقیمانده از پریود 1+k تا پریود T است، با استراتژی آزادسازی (حذف محدودیت باینری متغیرهای باینری)، ساده‌سازی می‏شود.

در انتهای هر تکرار، k یک پریود به جلو حرکت می‌کند و الگوریتم وارد تکرار بعدی می‌شود. این الگوریتم تا رسیدن به پریود آخر ادامه پیدا می‏کند. در تکرار آخر این پروسه، همۀ متغیرهای تصمیم، برای همۀ محدوده برنامه‌ریزی مشخص می‌شود. شکل(۲) این الگوریتم تدریجی براساس محدودۀ متحرک، دو تکرار پی‌درپی را مشخص می‌کند.

 

شکل ۲- محدودسازی بر روی متحرک زمان

 

الگوریتم ب: محدودسازی بر روی متحرک وضعیت تولید

در این الگوریتم از روش بهینه‌سازی–محدودسازی با ثابت‌سازی، روی متحرک‌های وضعیت تولید، با همان روش تشریح‌‌‌شده در بخش قبلی، در شکل زیر مشخص شده است.

شکل ۳ - محدودسازی بر روی متحرک وضعیت تولید

 

الگوریتم ترکیبی دوبعدی (ج): با رویکرد محدودسازی هم‌زمان دو بعد زمان تولید و وضعیت تولید

با توجه به جنبه‌های اجرایی و اولویت‌های عملیاتی در برنامه‌های تولیدی، ترجیح برنامه‌ریزی تولید در برخی از صنایع تولیدی به‌ویژه حوزۀ نفت و گاز، استفاده از یک رویکرد بهینه‌سازی تلفیقی بر روی زمان و وضعیت تولید است که این موضوع، حل مسئله را به سمت ترکیبی از ثابت‌سازی و محدودسازی دربارۀ دو بعد زمان و وضعیت تولید سوق می‌دهد، در این راستا الگوریتم ریاضی بهینه‌سازی به‌صورت تلفیق دو الگوریتم یک و دو اجرا شده است.

 

شکل ۴- الگوریتم ترکیبی دوبعدی: با رویکرد محدودسازی بر روی دو بعد زمان تولید و وضعیت تولید

 

۵- نتایج عددی

در این بخش، برای ارزیابی عملکرد الگوریتم‌های پیشنهادی از داده‌های شبیه‌سازی‌شده، استفاده شده که به‌صورت تصادفی تولید شده است‌؛ همچنین، مسائلی در ابعاد مختلف طراحی شده و سه الگوریتم ثابت‌سازی- بهینه‌سازی مطرح‌شده در بخش قبلی، به آزمون گذاشته شده و عملکرد آن‌ها با یک الگوریتم دقیق (الگوریتم شاخه و کران) مقایسه شده است. به‌این‌منظور، سه دستۀ مسئله با اندازه‌های متفاوت در قالب ابعاد کوچک، متوسط و بزرگ طراحی شده و برای هر اندازۀ مسئله، ۲۱ نمونه دادۀ شبیه‌سازی‌شده، استفاده شده و میانگین نتایج برای هر دسته استخراج و با نتایج راه‌حل دقیق، مقایسه شده است.

 برای کد نویسی الگوریتم‌های این مقاله، از نرم‌افزار ۲۰۱۶ MATLAB استفاده شده و محاسبات عددی، با کامپیوتر شخصی با پروسسور GHz۹/۳@۷۱۰۰- ۳Core™i ، دارای حافظه داخلی ۸ گیگابایت انجام شده است.

 

الف-نتایج حل مسائل با ابعاد کوچک:

برای بررسی عملکرد الگوریتم‌های سه‌گانه، این مقاله در ابعاد کوچک، ۲۱ مسئله با ابعاد کوچک و با مقادیر ۴=K ،۴=M و ۸=T به کار گرفته شد. نتایج حاصل، در جدول ۱ ارائه شده است. در این جدول، ستون اول شمارۀ نمونۀ داده‌های شبیه‌سازی‌شده؛ ستون دوم، زمان رسیدن به جواب دقیق برحسب ثانیه با استفاده از الگوریتم شاخه و کران؛ ستون سوم و چهارم، مربوط‌به درصد انحراف تابع هدف با الگوریتم الف، نسبت‌به جواب دقیق و بهترین زمان رسیدن به جواب برحسب ثانیه و ستون‌های بعدی مشابه ستون‌های سوم و چهارم برای الگوریتم‌های ب و ج است.

 

جدول ۱- مقایسۀ بین الگوریتم‌های سه‌گانه و جواب دقیق برای مسائل با ابعاد کوچک (۸=T، ۴=M، ۴=K)

جواب‌ها

نمونه

زمان جواب دقیق

جواب الگوریتم الف

جواب الگوریتم ب

جواب الگوریتم ج

درصد انحراف تابع هدف

زمان الگوریتم

درصد انحراف تابع هدف

زمان الگوریتم

درصد انحراف تابع هدف

زمان الگوریتم

۱

۵۰/۰

%۷۱/۶

۸۶/۰

%۳۶/۶۱

۶۵/۰

%۶/۷

۶۷/۰

۲

۲۸/۰

%۴۹/۳

۵۶/۰

%۷۴/۸

۴۸/۰

%۱/۲

۶۳/۰

۳

۲۶/۰

%۳۷/۴

۵۳/۰

%۶۲/۱۰

۵۴/۰

%۵۲/۲

۵۸/۰

۴

۴۵/۰

%۳۲/۱۱

۶۰/۰

%۶۲/۶۶

۶۵/۰

%۱۸/۲۷

۵۵/۰

۵

۵۲/۰

%۲۲/۱۰

۷۶/۰

%۲۵/۵۸

۸۲/۰

%۱۰/۱۵

۶۱/۰

۶

۳۹/۰

%۵۳/۵

۶۷/۰

%۴۴/۶۸

۷۱/۰

%۶۳/۱۴

۵۶/۰

۷

۱۶/۰

%۴۵/۹۴

۶۱/۰

%۶۹/۳۸۹

۳۸/۰

%۹/۵۸

۳۹/۰

۸

۵۶/۰

%۴۹/۲

۷۸/۰

%۸۳/۶۴

۶۹/۰

%۶۳/۲

۶۳/۰

۹

۲۹/۰

%۴۰/۷

۵۲/۰

%۱/۶۴

۳۹/۰

%۲۳/۷

۶۳/۰

۱۰

۷۴/۰

%۶۸/۳

۷۶/۰

%۴۹/۱۲۳

۴۴/۰

%۴۰/۲۶

۷۷/۰

۱۱

۷۴/۰

%۶۸/۳

۷۸/۰

%۴۹/۱۲۳

۵۳/۰

%۴۰/۲۶

۶۹/۰

۱۲

۵۲/۰

%۸۲/۲

۸۳/۰

%۵۹/۶۰

۶۱/۰

%۲۶/۸

۷۵/۰

۱۳

۲۰/۰

%۹۸/۱۷

۴۰/۰

%۲۱/۱۲۶

۳۱/۰

%۴۱/۴۹

۳۷/۰

۱۴

۷۸/۰

%۸۸/۱۳

۱۰۹/۰

%۵۱/۶۸

۸۹/۰

%۱۶/۳۲

۸۶/۰

۱۵

۴۶/۰

%۱۷/۱

۷۳/۰

%۶۳/۳۶

۵۵/۰

%۸۳/۲

۶۴/۰

۱۶

۷۰/۰

%۱۳/۷

۸۹/۰

%۳۴/۸۵

۷۵/۰

%۲۷/۳۰

۸۳/۰

۱۷

۷۲/۰

%۱۵/۴

۷۶/۰

%۳۵/۸۵

۹۳/۰

%۲۸/۳۰

۸۳/۰

۱۸

۹۵/۰

%۱۴/۵

۸۴/۰

%۸۲/۸۸

۸۹/۰

%۷۲/۲۳

۸۷/۰

۱۹

۹۷/۰

%۱۲/۴

۹۶/۰

%۳/۸۸

۷۶/۰

%۵۳/۱۹

۸۶/۰

۲۰

۹۶/۰

%۸۵/۶

۹۹/۰

%۵۴/۹۶

۷۸/۰

%۷۷/۳۴

۹۴/۰

۲۱

۴۲/۰

%۹۵/۱

۶۳/۰

%۵۱/۷۲

۶۶/۰

%۳۶/۲۳

۵۳/۰

میانگین

۵۵/۰

%۷۴/۱۰

۷۳/۰

%۰/۸۸

۶۴/۰

%۵۶/۲۱

۶۷/۰

 

ب-نتایج حل مسائل با ابعاد متوسط:

برای بررسی عملکرد الگوریتم‌های سه‌گانه، این مقاله در ابعاد متوسط، ۲۱ مسئله با ابعاد متوسط و مقادیر ۶=K ،۶=M و ۱۲=T به کار گرفته شد. نتایج حاصل، در جدول ۲ ارائه شده است. در این جدول توضیح مقادیر مشابه جدول ۱ است.

 

جدول ۲- مقایسۀ بین الگوریتم‌های سه‌گانه و جواب دقیق برای مسائل با ابعاد متوسط (۱۲=T، ۶=M، ۶=K)

جواب ها

نمونه

زمان جواب دقیق

جواب الگوریتم الف

جواب الگوریتم ب

جواب الگوریتم ج

انحراف تابع هدف

زمان الگوریتم

انحراف تابع هدف

زمان الگوریتم

انحراف تابع هدف

زمان الگوریتم

۱

۲۶۵/۰

%۱۶/۳

۲۳۵/۰

%۵۹/۱۹۲

۲۰۳/۰

%۲۱/۳۰

۱۷۳/۰

۲

۳۱۰/۰

%۲۱/۷

۱۶۸/۰

%۵۸/۱۲۵

۱۶۲/۰

%۷۱/۴۱

۱۴۱/۰

۳

۲۱۴/۰

%۷۲/۵

۱۸۷/۰

%۳۳/۳۷۷

۱۵۳/۰

%۶۷/۴۴

۱۲۲/۰

۴

۳۱۰/۰

%۷۴/۲

۱۸۴/۰

%۱۴/۴۳۳

۱۳۵/۰

%۶۰/۸۹

۱۱۲/۰

۵

۷۱/۰

%۰/۰

۷۳/۰

%۴۰/۱۲

۶۹/۰

%۹۴/۱۹

۷۴/۰

۶

۲۲۳/۰

%۲۹/۲

۲۰۹/۰

%۵۱/۱۵۲

۱۴۵/۰

%۳۱/۲۳

۱۴۰/۰

۷

۲۲۰/۰

%۱۱/۳

۱۵۴/۰

%۹۷/۴۶۳

۹۴/۰

%۲۵/۴۵

۸۵/۰

۸

۳۴۸/۰

%۵/۳

۲۱۲/۰

%۳۵/۱۸۹

۱۶۸/۰

%۴/۳۰

۱۲۹/۰

۹

۱۱۳/۰

%۷۶/۹

۱۱۱/۰

%۸۷/۱۹۷

۱۵۹/۰

%۴۶/۲۳

۱۴۰/۰

۱۰

۲۹۶/۱

%۳۲/۵

۲۲۱/۰

%۶۶/۱۹۹

۱۶۲/۰

%۸۳/۱۸

۱۲۳/۰

۱۱

۲۵۹/۰

%۵۵/۴

۲۱۹/۰

%۱۹/۲۲۸

۱۷۶/۰

%۵۶/۴۳

۱۷۹/۰

۱۲

۲۶۷/۰

%۱۶/۳

۲۳۱/۰

%۸۰/۱۹۲

۱۹۷/۰

%۲۴/۳۰

۱۷۸/۰

۱۳

۴۵۵/۰

%۲۸/۵

۱۸۴/۰

%۶۲/۱۹۴

۱۶۸/۰

%۱/۳۸

۱۳۶/۰

۱۴

۲۶۲/۰

%۱۶/۳

۲۳۵/۰

%۵۳/۱۹۲

۱۸۹/۰

%۲۱/۳۰

۱۷۶/۰

۱۵

۲۵۹/۰

%۴۶/۲

۲۲۶/۰

%۹۱/۲۲۰

۱۹۵/۰

%۳۰/۳۱

۱۷۵/۰

۱۶

۲۶۱/۰

%۴۷/۳

۲۱۷/۰

%۶۵/۱۹۷

۱۹۱/۰

%۷۵/۳۱

۱۷۱/۰

۱۷

۳۳۷/۰

%۹۴/۳

۲۰۲/۰

%۸۵/۱۸۲

۱۶۴/۰

%۸۳/۳۰

۱۶۱/۰

۱۸

۳۳۳/۰

%۱۴/۶

۱۹۹/۰

%۲۵/۱۸۴

۱۴۹/۰

%۶۰/۲۵

۱۴۳/۰

۱۹

۲۳۲/۰

%۶۰/۲

۲۱۷/۰

%۳۶/۱۸۲

۱۶۴/۰

%۲۴/۳۸

۱۴۹/۰

۲۰

۱۱۲/۰

%۳۶/۲۰

۱۸۵/۰

%۳۰/۱۴۲

۱۵۶/۰

%۶۷/۲۴

۱۳۰/۰

۲۱

۲۶۴/۰

%۱۵/۳

۲۲۳/۰

%۶۱/۱۹۲

۱۹۴/۰

%۷۰/۲۹

۱۷۴/۰

میانگین

۳۰۷/۰

%۴۶/۴

۱۹۵/۰

%۵۰/۲۰۳

۱۶۲/۰

%۴۶/۲۸

۱۳۷/۰

 

ج)حل مسائل با ابعاد بزرگ

برای بررسی عملکرد الگوریتم‌های سه‌گانه، این مقاله در ابعاد بزرگ، ۲۱ مسئله با ابعاد بزرگ و با مقادیر ۱۲=K ،۱۵=M و ۱۵=T به کار گرفته شد. نتایج حاصل، در جدول ۳ ارائه شده است. در این جدول نیز توضیح مقادیر مشابه جدول ۱ است.

 

 

جدول ۳- مقایسۀ بین الگوریتم‌های سه‌گانه و جواب دقیق برای مسائل با ابعاد بزرگ (۱۵=T، ۱۵=M، ۱۲=K)

جواب ها

نمونه

زمان جواب دقیق

جواب الگوریتم الف

جواب الگوریتم ب

جواب الگوریتم ج

درصد انحراف تابع هدف

زمان الگوریتم

درصد انحراف تابع هدف

زمان الگوریتم

درصد انحراف تابع هدف

زمان الگوریتم

۱

۲۲۷/۱۵

%۸۱/۲۰

۳۷۸/۲

%۷/۹۵

۶۹/۲

%۲۲/۳۷

۴۱۱/۱

۲

۵۵۴/۸

%۱۴/۲۰

۴۸۱/۲

%۲۸/۹۳

۲۸۱/۲

%۹/۳۵

۴۷۶/۱

۳

۳۰/۱۵

%۸۸/۲۰

۹۰۰/۲

%۱۱/۹۵

۸۵/۲

%۲۴/۳۷

۳۹۷/۱

۴

۳۰/۱۵

%۸۴/۲۸

۳۵۰/۲

%۵۲/۱۱۰

۵۵/۲

%۱۲/۶۵

۴۱۵/۱

۵

۲۵۲/۱۵

%۸۱/۲۰

۸۵۶/۲

%۷/۹۵

۱۲۰/۲

%۲۲/۳۷

۴۱۹/۱

۶

۲۶/۱۵

%۸۶/۲۰

۳۹۳/۲

%۴۲/۹۵

۷۴/۲

%۴۰/۳۷

۴۰۴/۱

۷

۲۱۹/۱۵

%۸۹/۲۰

۴۴۰/۲

%۹۵/۸۶

۷۸/۲

%۵۰/۳۷

۴۰۷/۱

۸

۷۰۱/۷

%۴۷/۱۴

۴۰۷/۲

%۲۷/۷۹

۸۷۱/۱

%۸۷/۳۲

۴۲۸/۱

۹

۱۷۰/۱۵

%۶۶/۲۰

۳۹۲/۲

%۴/۹۴

۱۲۳/۲

%۹۹/۳۶

۴۱۴/۱

۱۰

۷۵۳/۶

%۰/۲۲

۳۱۲/۲

%۳۱/۱۲۳

۱۴۶/۲

%۵/۴۵

۴۹۶/۱

۱۱

۷۴۳/۱۱

%۳۳/۱۸

۶۲۷/۲

%۸۲/۱۰۲

۳۰۷/۲

%۵۸/۳۳

۴۵۲/۱

۱۲

۶۸۷/۸

%۳۸/۱۴

۳۷۶/۲

%۵۰/۹۳

۱۵۹/۲

%۸۲/۳۷

۴۳۰/۱

۱۳

۳۱۹/۷

%۵۱/۲۱

۵۳۲/۱

%۲۵/۱۰۸

۷۷۲/۰

%۳۷/۳۸

۶۱۵/۰

۱۴

۲۶۵/۸

%۲۱/۲۲

۳۶۴/۲

%۶۴/۹۹

۳۲۲/۲

%۷۰/۴۰

۳۶۹/۱

۱۵

۸۰۵/۱۳

%۷۶/۱۸

۴۳۷/۲

%۴۰/۹۳

۱۲۱/۲

%۶۴/۳۴

۴۲۰/۱

۱۶

۶۰۰/۱۰

%۳۴/۱۸

۵۶۷/۲

%۳۲/۱۶۷

۴۹/۲

%۷۵/۴۶

۵۰۰/۱

۱۷

۵۱/۸

%۶۶/۱۸

۵۷۲/۲

%۹۴/۸۲

۲۹۲/۲

%۹۷/۳۳

۶۷۸/۱

۱۸

۸۶۶/۱۳

%۸۹/۱۸

۶۴۷/۲

%۷۲/۹۸

۱۷۴/۲

%/۲/۳۳

۵۵۴/۱

۱۹

۳/۹

%۱۶/۱۲

۴۷۶/۲

%۰/۹۷

۱۹۰/۲

%۵۷/۳۳

۳۸۸/۱

۲۰

۷۹/۱۵

%۸۲/۲۰

۳۶۲/۲

%۱۷/۹۵

۱۴۲/۲

%۲۴/۳۷

۴۱۳/۱

۲۱

۷۵۹/۱

%۶۴/۷

۸۵۳/۰

%۴۱/۷۰

۵۲۸/۰

%۹۸/۲۹

۵۳۳/۰

میانگین

۲۹۲/۱۱

%۵۷/۱۸

۳۶۸/۲

%۱۵/۹۸

۹۹۶/۱

%۸۰/۳۶

۳۶۵/۱

 

۶- بحث

نتایج تحقیق در ابعاد مسائل کوچک (جدول ۱) نشان می‌دهد میانگین زمان رسیدن به جواب سه الگوریتم پیشنهادی، به‌ترتیب۷۳/۰، ۶۴/۰ و ۶۷/۰ ثانیه و میانگین زمان رسیدن به جواب دقیق با الگوریتم شاخه و کران ۵۵/۰ ثانیه است. همان‌گونه که انتظار می‌رود در ابعاد کوچک، راه‌حل‌های دقیق در زمان پذیرفتنی به جواب بهینه می‌رسد، در مسئلۀ این تحقیق نیز، نتایج با سایر تحقیقات مشابه همخوانی دارد. دربارۀ نزدیکی مقدار تابع هدف در ابعاد کوچک، الگوریتم‌های پیشنهادی تحقیق، به‌ترتیب ۷۴/۱۰، ۰/۸۸ و ۵۶/۲۱ درصد بیشتر از مقدار تابع هدف جواب دقیق مسئله است که به‌ترتیب، الگوریتم‌های الف، ج و ب کمترین فاصله را از جواب بهینه دارند.

نتایج تحقیق در ابعاد مسائل متوسط (جدول ۲) نشان می‌دهد میانگین زمان رسیدن به جواب سه الگوریتم پیشنهادی، به‌ترتیب ۱۹۵/۰، ۱۶۲/۰ و ۱۳۷/۰ ثانیه و میانگین زمان رسیدن به جواب دقیق با الگوریتم شاخه و کران ۳۰۷/۰ ثانیه است. مشاهده می‌شود با افزایش ابعاد مسئله، الگوریتم‌های پیشنهادی این تحقیق ازنظر زمان رسیدن به جواب، از راه‌حل دقیق (روش شاخه و کران) کیفیت بهتری دارد و در بین این سه الگوریتم، الگوریتم دوبعدی (الگوریتم ج) بهترین عملکرد زمانی را دارد. دربارۀ نزدیکی مقدار تابع هدف به مقدار بهینۀ دقیق مسائل، به‌ترتیب الگوریتم‌های الف، ج و ب کمترین فاصله را از جواب بهینه دارند. دربارۀ نزدیکی مقدار تابع هدف در ابعاد متوسط، الگوریتم‌های پیشنهادی تحقیق، به‌ترتیب ۴۶/۴، ۵۰/ ۲۰۳ و ۴۶/۲۸ درصد بیشتر از مقدار تابع هدف جواب دقیق مسئله‌اند که به‌ترتیب، الگوریتم‌های الف، ج و ب کمترین فاصله را از جواب بهینه دارند.

مشابه سایر پژوهش‌ها با افزایش ابعاد مسئله، روش‌های ابتکاری ثابت‌سازی-بهینه‌سازی، عملکرد زمانی بهتری را نشان می‌دهد. نتایج این تحقیق در ابعاد بزرگ (جدول ۳) نیز، نشان می‌دهد میانگین زمان رسیدن به جواب سه الگوریتم پیشنهادی، به‌ترتیب ۳۶۸/۲، ۹۹۶/۱ و ۳۶۵/۱ ثانیه و میانگین زمان رسیدن به جواب دقیق با الگوریتم شاخه و کران ۲۹۲/۱۱ ثانیه است. مشاهده می‌شود با افزایش ابعاد مسئله، الگوریتم‌های پیشنهادی این تحقیق ازنظر زمان رسیدن به جواب، از راه‌حل دقیق (روش شاخه و کران) کیفیت بهتری دارد و در بین این سه الگوریتم، الگوریتم دوبعدی (الگوریتم ج) بهترین عملکرد زمانی را دارد. دربارۀ نزدیکی مقدار تابع هدف به مقدار بهینۀ دقیق مسائل، به‌ترتیب الگوریتم‌های الف، ج و ب کمترین فاصله را از جواب بهینه دارند.

 

۷-نتیجه‌گیری

در این مقاله، سیستم‌های تولیدی همبستۀ انعطاف‌پذیر بررسی و یک مدل ریاضی برای تعیین اندازۀ انباشتۀ آن‌ها ارائه شد. ازآنجایی‌که، تعداد متغیرها و محدودیت‌های یک مدل برنامه‌ریزی خطی عدد صحیح، اثر چشم‌گیری در سرعت الگوریتم‌های حل این‌گونه مسائل دارد، در ادامه سه دستۀ مسئله با ابعاد کوچک، متوسط و بزرگ به کمک داده‌های تصادفی شبیه‌سازی شد؛ سپس این مسائل، با سه الگوریتم مختلف مطرح‌شده، ثابت‌سازی_بهینه‌سازی حل و نتایج آن‌ها مقایسه و تحلیل شد.

نتایج نشان می‌دهد که ثابت سازی_بهینه‌سازی روی متغیر زمان (الگوریتم الف) کیفیت جواب‌های بهتری (ازنظر نزدیکی به مقدار تابع هدف دقیق مسئله) دارد و با افزایش ابعاد مسئله، زمان حل این روش نیز افزایش می‌یابد؛ ولی در مقایسه با زمان محاسبۀ جواب دقیق مسئله به روش شاخه و کران، برتری خود را به راه حل‌های دقیق نشان می‌دهد. بررسی نتایج عملکرد الگوریتم ب که ثابت‌سازی روی وضعیت تولیدی را اعمال می‌کند، ازنظر کیفیت جواب و زمان رسیدن به جواب، از الگوریتم الف ضعیف‌تر است و نشان می‌دهد در عمل، برتری نسبت‌به الگوریتم الف ندارد؛ ولی در مقایسه با راه‌حل دقیق مسئله با افزایش ابعاد مسئله، عملکرد این الگوریتم نیز درخور توجه است.

نتایج تحقیق دربارۀ الگوریتم ج که الگوریتم پیشنهادی این مقاله، برای مسئلۀ مدنظر است و ثابت‌سازی را در دو بعد زمان و وضعیت تولیدی به‌صورت هم‌زمان اعمال می‌کند، حاکی از برتری چشمگیر این الگوریتم ازنظر زمان رسیدن به جواب، نسبت‌به دو الگوریتم دیگر است؛ البته ازنظر کیفیت جواب در مسائل بررسی‌شده، اندکی از جواب‌های الگوریتم اول ضعیف‌تر است؛ ولی به‌صورت چشمگیری از الگوریتم دوم بهتر است. در بسیاری از مسائل واقعی، با توجه به اینکه پارامترهای هزینه‌ای در وضعیت‌های مختلف تولیدی (مانند در صنایع پایین‌دستی نفت، گاز و پتروشیمی) نزدیک به یکدیگر است و درعمل، تعیین وضعیت‌های تولیدی متناسب با سایر پارامترها همچون تقاضا، فارغ از هزینه‌های تولید مدنظر است، کارایی الگوریتم پیشنهادی در این مقاله بیشتر به چشم خواهد آمد.

در انجام این پژوهش مهم‌ترین محدودیت، نبود داده‌های واقعی برای یک سیستم تولیدی انعطاف‌پذیر با محصولات همبسته است؛ به همین دلیل، برای اعتبارسنجی مدل و آزمودن الگوریتم‌های پیشنهادی، از داده‌های شبیه‌سازی‌شده استفاده شد. محققان برای تحقیقات آتی می‌توانند با استفاده از داده‌های واقعی، مطالعات موردی را براساس مدل و الگوریتم‌های ارائه‌شده در این مقاله، انجام دهند و سایر ویژگی‌هایی همچون محدودیت ظرفیت تولید و مجاز بودن کمبود را به مدل بیافزایند. همچنین در مدل ارائه‌شده، پارامترهای مدل به‌صورت قطعی در نظر گرفته شد که می‌توان در تحقیقات بعدی تقاضاهای احتمالی را نیز در نظر گرفت. علاوه بر این محققان می‌توانند به کمک این مدل، مسائل واقعی را مدل‌سازی و حل کنند.

 

[i] Muckstadt, , & Sapra

[ii] Co-production

[iii] Kalay, & Taşkın

[iv] Wiedemann

[v] Flexible manufacturing system

[vi]  Shivanand

[vii] Remanufacturing

[viii] Cunha

[ix] Taş

[x] Tavaghof-Gigloo, & Minner,

[xi] van Pelt & Fransoo

[xii] Jauhari, & Laksono

[xiii] Wu

[xiv] de Armas, , & Laguna

[xv] Vincent

[xvi] Carvalho, & Nascimento

[xvii] Ben Ammar

[xviii] Bayley

[xix] Gören, & Tunali

[xx] Carvalho, & Nascimento

[xxi] Service-level constraints

[xxii] Batch Ordering

[xxiii] Stadtler, & Meistering

[xxiv] Cardona-Valdés

[xxv] Prasad & Jayswal

[xxvi] Eimaraghy

[xxvii] Groover

[xxviii] Co-products

[xxix] Ağralı

[xxx]  Suzanne

[xxxi] Cunha

[xxxii] Devoto

[xxxiii] Bo

[xxxiv]  Fix and Optimize Heuristic

[xxxv]  Flexible Manufacturing System Uncapacitated Lot sizing Problem with Co-production

[xxxvi] Large-time bucket

[xxxvii] Small-time bucket

[xxxviii] Capacitated Lot-sizing Problem

[xxxix] Kang

[xl] Discrete Lot-sizing and Scheduling Problem

[xli]  Fleischmann

[xlii] The General Lot-sizing and Scheduling Problem

[xliii]  Fleischmann and Meyr

[xliv] Sel, & Bilgen

[xlv] Special-purpose heuristics

[xlvi] Schulz

[xlvii] Time window

[xlviii] Overlapping

[xlix] Non-overlapping

[l]  Federgruen

[li]  Helber and Sahling

[lii]  Xiao

[liii] Relax&Fix

[liv] Goren

[lv] Toledo

[lvi] Production status, Production Mode

References

Ağralı, S. (2012). A dynamic uncapacitated lot-sizing problem with co-production. Optimization Letters, 6(6), 1051-1061.
Alipour, Z., Jolai, F., Monabbati, E., & Zaerpour, N. (2020). General lot-sizing and scheduling for perishable food products. RAIRO-Operations Research, 54(3), 913-931.
Bayley, T., Süral, H., & Bookbinder, J. H. (2018). A hybrid Benders approach for coordinated capacitated lot-sizing of multiple product families with set-up times. International Journal of Production Research, 56(3), 1326-1344.
Ben Ammar, H., Ayadi, O., & Masmoudi, F. (2020). An effective multi-objective particle swarm optimization for the multi-item capacitated lot-sizing problem with set-up times and backlogging. Engineering Optimization, 52(7), 1198-1224.
Bo, V., Bortolini, M., Malaguti, E., Monaci, M., Mora, C., & Paronuzzi, P. (2021). Models and algorithms for integrated production and distribution problems. Computers & Industrial Engineering, 154, 107003.
Cardona-Valdés, Y., Nucamendi-Guillén, S., Peimbert-García, R. E., Macedo-Barragán, G., & Díaz-Medina, E. (2020). A New Formulation for the Capacitated Lot Sizing Problem with Batch Ordering Allowing Shortages. Mathematics, 8(6), 878.
Carvalho, D. M., & Nascimento, M. C. (2021). Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup. arXiv preprint arXiv:2101.04677.
Carvalho, D. M., & Nascimento, M. C. (2018). A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over. Computers & Operations Research, 100, 43-53.
Cunha, J. O., Kramer, H. H., & Melo, R. A. (2021). On the computational complexity of uncapacitated multi-plant lot-sizing problems. Optimization Letters, 15(2), 803-812.
Cunha, J. O., Kramer, H. H., & Melo, R. A. (2019). Effective matheuristics for the multi-item capacitated lot-sizing problem with remanufacturing. Computers & Operations Research, 104, 149-158.
de Armas, J., & Laguna, M. (2020). Parallel machine, capacitated lot-sizing and scheduling for the pipe-insulation industry. International Journal of Production Research, 58(3), 800-817.
Devoto, C., Fernández, E., & Piñeyro, P. (2021). The economic lot-sizing problem with remanufacturing and inspection for grading heterogeneous returns. Journal of Remanufacturing, 11(1), 71-87.
Ebrahimi, M., Amiri, M. (2017). Developing and Solving a Two Level Lot Sizing Problem. Journal of Industrial Management Perspective, 7(Issue 2, Summer 2017), 109-137.
ElMaraghy, H. A. (2005). Flexible and reconfigurable manufacturing systems paradigms. International journal of flexible manufacturing systems, 17(4), 261-276.
Federgruen, A., Meissner, J., & Tzur, M. (2007). Progressive interval heuristics for multi-item capacitated lot-sizing problems. Operations Research, 55(3), 490-502.
Fleischmann, B. (1990). The discrete lot-sizing and scheduling problem. European Journal of Operational Research, 44(3), 337-348.
Fleischmann, B., & Meyr, H. (1997). The general lotsizing and scheduling problem. Operations-Research-Spektrum, 19(1), 11-21.
Gholamrezaii rahimi, M., Khademi zareh, H. (2015). A Model of Production Planning with Multi-product, Multi time period and Multi-Objective with Fuzzy Parameters. Journal of Production and Operations Management, 6(1), 61-78.
Gicquel, C., & Cheng, J. (2018). A joint chance-constrained programming approach for the single-item capacitated lot-sizing problem with stochastic demand. Annals of Operations Research, 264(1), 123-155.
Gören, H. G., & Tunali, S. (2018). Fix-and-optimize heuristics for capacitated lot sizing with setup carryover and backordering. Journal of Enterprise Information Management.
Goren, H. G., Tunali, S., & Jans, R. (2012). A hybrid approach for the capacitated lot sizing problem with setup carryover. International Journal of Production Research, 50(6), 1582-1597.
Groover, M. P. (2020). Fundamentals of modern manufacturing: materials, processes, and systems. John Wiley & Sons.
Helber, S., & Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123(2), 247-256.
Hossein Mirzaei, A., Nakhai Kamalabadi, I., Zegordi, S. (2011). A New Algorithm for Solving the Inventory Routing Problem with Direct Shipment. Journal of Production and Operations Management, 2(1), 1-28.
Jauhari, W. A., & Laksono, P. W. (2017, November). A joint economic lot-sizing problem with fuzzy demand, defective items and environmental impacts. In IOP Conference Series: Materials Science and Engineering (Vol. 273, No. 1, p. 012018). IOP Publishing.
Kalay, S., & Taşkın, Z. C. (2021). A branch-and-price algorithm for parallel machine campaign planning under sequence dependent family setups and co-production. Computers & Operations Research, 135, 105430.
Kang, J. (2020). Capacitated Lot-Sizing Problem with Sequence-Dependent Setup, Setup Carryover and Setup Crossover. Processes, 8(7), 785.
Khosravi, S., Mirmohammadi, S. (2018). S‌T‌O‌C‌H‌A‌S‌T‌I‌C D‌Y‌N‌A‌M‌I‌C L‌O‌T- S‌I‌Z‌I‌N‌G P‌R‌O‌B‌L‌E‌M W‌I‌T‌H T‌O‌T‌A‌L Q‌U‌A‌N‌T‌I‌T‌Y D‌I‌S‌C‌O‌U‌N‌T. Sharif Journal of Industrial Engineering & Management, 34.1(1.1), 39-50. doi: 10.24200/j65.2018.5546
Muckstadt, J. A., & Sapra, A. (2010). Principles of inventory management: When you are down to four, order more. Springer Science & Business Media.
Prasad, D., & Jayswal, S. C. (2019). A review on flexibility and reconfigurability in manufacturing system. In Innovation in Materials Science and Engineering (pp. 187-200). Springer, Singapore.
Roshani, A., Giglio, D., & Paolucci, M. (2017). A relax-and-fix heuristic approach for the capacitated dynamic lot sizing problem in integrated manufacturing/remanufacturing systems. IFAC-PapersOnLine, 50(1), 9008-9013.
Sel, Ç., & Bilgen, B. (2014). Hybrid simulation and MIP based heuristic algorithm for the production and distribution planning in the soft drink industry. Journal of Manufacturing systems, 33(3), 385-399.
Schulz, T. (2011). A new Silver–Meal based heuristic for the single-item dynamic lot sizing problem with returns and remanufacturing. International Journal of Production Research, 49(9), 2519-2533.
Shivanand, H. K., Benal, M. M., & Koti, V. (2006). Flexible manufacturing system. New Age International.
Stadtler, H., & Meistering, M. (2019). Model formulations for the capacitated lot-sizing problem with service-level constraints. OR Spectrum, 41(4), 1025-1056.
Suzanne, E., Absi, N., Borodin, V., & van den Heuvel, W. (2020). A single-item lot-sizing problem with a by-product and inventory capacities. European Journal of Operational Research, 287(3), 844-855.
Taş, D., Gendreau, M., Jabali, O., & Jans, R. (2019). A capacitated lot sizing problem with stochastic setup times and overtime. European Journal of Operational Research, 273(1), 146-159.
Tavaghof-Gigloo, D., & Minner, S. (2020). Planning approaches for stochastic capacitated lot-sizing with service level constraints. International Journal of Production Research, 1-21.
Toledo, C. F. M., De Oliveira, R. R. R., & França, P. M. (2013). A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging. Computers & Operations Research, 40(4), 910-919.
Tolio, T. (2008). Design of flexible production systems. Springer.
Vejdani, M., Dolati, A. (2015). Multi-Level Lot Sizing Problem with Deterioration Inventory and Disposal Costs. Journal of Production and Operations Management, 6(2), 55-78.
van Pelt, T. D., & Fransoo, J. C. (2018). A note on “Linear programming models for a stochastic dynamic capacitated lot sizing problem”. Computers & Operations Research, 89, 13-16.
Vincent, B., Duhamel, C., Ren, L., & Tchernev, N. (2020). A population-based metaheuristic for the capacitated lot-sizing problem with unrelated parallel machines. International Journal of Production Research, 58(21), 6689-6706.
Wiedemann, S. G., Ledgard, S. F., Henry, B. K., Yan, M. J., Mao, N., & Russell, S. J. (2015). Application of life cycle assessment to sheep production systems: investigating co-production of wool and meat using case studies from major global producers. The International Journal of Life Cycle Assessment, 20(4), 463-476.
Wu, T., Xiao, F., Zhang, C., He, Y., & Liang, Z. (2018). The green capacitated multi-item lot sizing problem with parallel machines. Computers & Operations Research, 98, 149-164.
Xiao, J., Zhang, C., Zheng, L., & Gupta, J. N. (2013). MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem. International Journal of Production Research, 51(16), 5011-5028.

Files

Share

How to cite

Statistics