الگوریتم دوبعدی ثابت‌سازی–بهینه‌سازی برای حل مسئلۀ تعیین اندازۀ انباشته در سیستم‌های تولیدی انعطاف‌پذیر با محصولات همبسته

۱-مقدمه

یکی از شایع‌ترین و مهم‌ترین مسائل همیشگی در بیشتر صنایع، مدیریت موجودی‌هاست. مغازه‌های خرده‌فروشی با مقادیر زیادی از کالاها انباشته شده‌اند؛ صنایع تولیدی نیز، با موجودی‌های کلانی از مواد خام، محصولات نیم‌ساخته و کالاهای نهایی و همچنین: تجهیزات، ماشین‌آلات، قطعات یدکی و نیروی انسانی مواجه‌اند. به‌طورکلی، علت وجود موجودی‌ها، عدم تعادل بین تأمین یک کالا در یک محل با فروش یا مصرف آن است. این عدم تعادل می‌تواند به علل متعددی همچون فنی، اقتصادی، اجتماعی و طبیعی بروز کند. چهار سؤال اساسی که دربارۀ موجودی‌ها مطرح است، عبارت است از: چه آیتم‌هایی در سیستم باید ذخیره شود؟ این آیتم‌ها کجا باید ذخیره شود؟ چه مقدار از هر آیتم و در چه زمانی باید سفارش داده یا تولید شود؟ در بیشتر تحقیقاتی که درزمینۀ مدیریت موجودی انجام می‌شود، پژوهشگران با ارائۀ یک مدل ریاضی از مسئله، به دنبال یافتن راه حلی برای پاسخ به یک یا چند سؤال از سؤالات مذکوراند (موکستادت و اسپارا^[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 را  در نظر می‌گیریم. بدیهی است، نسبت تولید برای محصول اصلی در هر وضعیت تولید  فرض می‌شود. لیست علائمی که در ادامه استفاده می‌شود، عبارت است از:

اندیس‌ها

داده‌ها

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

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

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

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

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

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

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

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

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

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

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

برای حل مدل فوق، دانستن برخی روابط بین پارامترها و متغیرهای مدل می‌تواند کمک کند تا راه‌حل‌های کاراتری برای حل مدل انتخاب شود. یکی از این پارامترها، پارامتر 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