بهینه‌سازی بر مبنای شبیه‌سازی تعداد ماشین‌آلات در مسئلۀ زمان‌بندی تولید کارگاهی در شرایط عدم قطعیت و محدودیت بودجه و فضا

1- مقدمه

مسئلۀ تولید کارگاهی نوعی از مسائل توالی عملیات است که در آن کارها از ماشین‎‍های مشخص، ولی متمایز عبور می‎‍کنند. به عبارت دیگر، در این مسئله هر کاری که وارد سیستم می‎‍شود، باید ماشین‎‍های مشخص و از پیش تعیین شده‎‍ای را ملاقات کند و این ترتیب برای کارهای مختلف، با هم فرق می‎‍کند (پیندو[i]، 2012). با نگاهی عمیق‎‍تر به سیستم تولید کارگاهی، متوجه می‌شویم که پویایی و عدم قطعیت از ویژگی‎‍های بارز این نوع سیستم تولید است. برای مقایسه باید اختلاف بین تولید کارگاهی را با روش خط تولید‌ مقایسه کرد. در روش خط تولید، یکسری از محصولات با ترتیب مشخص و یکسان و به‌صورت انبوه تولید می‌شوند، به‌طوری که در بیشتر موارد حتی برای تولید محصولات ‌جدید،‌ به دریافت سفارش نیاز نیست و محصولات تولید‌شده در انبار برای پاسخ به تقاضاهای آتی ذخیره می‎‍شوند که به این حالت، تولید برای ذخیره گفته می‎‍شود. در حالی که در سیستم‎‍های تولید کارگاهی، بیشتر با تولید محصولاتی مواجهیم که حالت پروژه‎‍ای دارند و هر محصول باید فرآیندهای منحصر به خود را برای تولید طی کند. به‌علاوه در بیشتر مواقع بعد از سفارش محصول جدید، اقدام به تولید آن در چنین سیستم‎‍هایی می‎‍شود (تولید برای سفارش).

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

تعیین بهینۀ توالی کارها در تولید کارگاهی کسب و کارهای کوچک و متوسط، در بهره‌وری ماشین‌آلات، هزینه‌های مربوط به دیرکرد و زودکرد تحویل کارها تأثیر‌گذار است. برخلاف دیگر روش‌های بهینه‌سازی، در شبیه‌سازی به ایجاد یک مدل ریاضی دقیق نیازی نیست، بلکه با یک مدل مفهومی ریاضی به نتایج مطلوبی دست می‌یابیم و این کار، حل مسائل بهینه‌سازی پیچیده را در صورتی تسهیل می‌کند که بتوان آن را به مدل شبیه‌سازی‌شده تبدیل کرد (سجادی و شهبازی[ii]، 2017).

در مسئلۀ زمان‌بندی تک‌ماشین، با تولید دسته‌ای و خرابی تصادفی ماشین با تابع هدف مسئله، حداقل‌سازی مجموع حداکثر زودکرد و حداکثر دیرکرد مورد انتظار کارها، برای حل این مسئله از مدل‌سازی مسئلۀ زمان‌بندی تک‌ماشین با تولید دسته‌ای و خرابی تصادفی و حل آن به‌وسیلۀ روش شاخه و کران استفاده شده است (ملایی و همکاران[iii]، 2022).

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

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

2- مبانی نظری و پیشینۀ پژوهش

مسئلۀ تولید کارگاهی در حالت قطعی و ایستا، با بیش از دو ماشین NP-Hard به حساب می‎‍‎‍آید (پیندو، 2012) و وارد‎‍‎‍کردن عوامل ایجاد عدم قطعیت بر پیچیدگی مسئله می‎‍افزاید. بر این اساس، با استفاده از تکنیک‎‍های معمولی تحقیق در عملیات، نمی‌توان‌ به مدل‎‍سازی و یافتن جواب بهینه برای این مسئله اقدام کرد. بیشتر مسائلی که در این زمینه مدل‎‍سازی شده‌اند، با استفاده از فرض‌های محدودکننده، به ساده‌سازی مسئله اقدام کرده‎‍اند که این امر باعث فاصله‌گرفتن از حالات واقعی می‎‍شود (ویرا و همکاران[iv]، 2000). روش‎‍های حل مسائل تولید کارگاهی به دستۀ تکنیک‎‍های ریاضی و تقریب‎‍زنی تقسیم می‌شود (جین و میران‌[v]، 1999). تکنیک‎‍های ریاضی جذابیت فراوانی در فرموله‎‍کردن و حل مسائل تولید کارگاهی دارند؛ با این حال این روش‌ها کارایی خود را در مسائل بزرگ‌مقیاس از دست می‎‍دهند. تکنیک‎‍های تقریب‌زنی روش‎‍های مناسبی‌ برای حل مسائل تولید کارگاهی با کیفیت جواب پذیرفتنی و در زمان مناسب‌اند، ولی رسیدن به جواب بهینه را تضمین نمی‎‍کنند. دربارۀ این مسئله از شبیه‎‍سازی استفاده می‌شود. گفتنی است که با شبیه‎‍سازی، سیستم‌ با تمام پویایی‎‍هایش در نظر گرفته می‌شود، ولی این روش به‌تنهایی متدی برای رسیدن به جواب بهینه نیست (بانکز و نلسون[vi]، 2010). شبیه‎‍سازی در‌واقع رویکردی برای تحلیل حساسیت سیستم و مقایسۀ بین راه‌حل‎‍های ممکن است. افزایش قدرت محاسباتی رایانه‎‍های امروزی، سبب شده است تا انجام این کار برای مسائل پیچیده‎‍تر و با تکرارهای زیاد امکان‎‍پذیر باشد. تعیین پارامترهای کنترلی مناسب برای مدل شبیه‎‍سازی‌شده، به بهبود عملکرد سیستم و رسیدن به جواب بهینه منجر می‌شود. برای این منظور با ترکیب روش‎‍های بهینه‎‍سازی با شبیه‎‍سازی، در عین در نظر‎‍‎‍ گرفتن پویایی مدل، جواب مناسبی برای آن تولید می‌شود. روش‎‍های بهینه‎‍سازی براساس شبیه‎‍سازی به‌ جای آنکه بر فرمول یا گراف تمرکز کنند، بر شیء تمرکز می‎‍کنند و می‌کوشند مسئله را از این طریق بهینه کنند. این روش حل مسئله، علاوه بر انعطاف‌پذیری بالا،‌ دقت زیادی هم دارد.

مهم‌ترین پارامتر تغییردادنی در بهینه‎‍سازی مسائل زمان‌بندی بر‌اساس شی‌ء، چگونگی اولویت‎‍دهی به کارها در صف ماشین‎‍هاست. در این روش جواب قطعی بهینه برای مسئله به دست نمی‎‍آید، ولی سیاست مناسبی برای اولویت‎‍دادن به کارها در پشت صف ماشین‎‍ها پیشنهاد می‎‍شود. در مرجع (بلک استون‌ و همکاران[vii]، 1982‌) قوانین پیشنهادشده برای اولویت‎‍‎‍‎‍دهی به کارها در پشت صف ماشین‎‍ها، برای سیستم تولید کارگاهی بررسی و طبقه‎‍بندی‌ و با استفاده از شبیه‎‍سازی، حالت‎‍های موجود برای سیستم ارزیابی شده است. این مقاله جزء اولین مقالات در زمینۀ طبقه‎‍بندی قوانین اولویت‎‍دهی به کارهاست. در سال‌های اخیر مقالات زیادی در این زمینه ارائه شده است؛ برای مثال در آثار چان و همکاران[viii] (2003) و ‌ونگ و رن[ix] (2006)، روش‎‍های جدیدتری برای این کار پیشنهاد شده است. روش‎‍های به کار گرفته شده برای بهینه‌سازی، بر‌اساس شبیه‎‍سازی به پنج دسته روش‎‍های جست‌وجوی شیب، تقریبی تصادفی، بهینه‎‍سازی مسیر نمونه، متد پاسخ سطح و روش‎‍های ابتکاری و فرا‎‍ابتکاری تقسیم می‎‍شوند (آزادیور[x]، 1999).

با ترکیب شبیه‎‍سازی، قوانین اولویت‎‍دهی و روش‎‍های جست‌وجوی تصادفی، جواب مناسبی برای سیستم تولیدی به دست می‌آید؛ به این صورت که پس از مدل‎‍سازی سیستم با شبیه‎‍سازی، یک بردار کنترلی برای مسئله تعریف می‎‍شود که این بردار به‌صورت تصادفی تولید و به‌عنوان متغیر کنترلی به شبیه‎‍سازی داده‌ و نتایج حاصل از آن ‌مقدار تابع هدف مسئله در نظر گرفته می‎‍شود؛ سپس با کمک روش‎‍های جست‌وجو، تغییراتی در این بردار ایجاد و سعی می‎‍شود نتایج مناسب‎‍تری برای مسئله حاصل شود.

در این زمینه در اثر ‌کلمت و همکاران[xi] (2009) با ترکیب شبیه‎‍سازی با روش‎‍های جست‌وجوی محلی، از‌جمله قبول آستانه‎‍ای، شبیه‎‍سازی تبریدی، جست‌وجوی حریصانه و دیگر الگوریتم‎‍ها، اقدام به اولویت‎‍دهی به کارها در یک سیستم دارای زمان، آماده‎‍سازی شده است.

دوآمارال و همکاران[xii] (2022) در مقاله‌ای با عنوان «بهینه‌سازی شبیه‌سازی مبتنی بر متامدل: مروری بر ادبیات سیستماتیک»، با بررسی شکاف‌ها، فرصت‌ها و چشم‌اندازهای آینده، که در طول توسعۀ این تحقیق پیدا شده است، نشان می‌دهند که این حوزۀ تحقیقاتی در 15 سال گذشته، در حال رشد بوده‌ و توانسته است با تحلیل سناریوهای تصمیم‌گیری، کمک‌های شایانی به مدیریت بکند.

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

شهبازی و همکاران[xiii] (2017) در پژوهشی، یک مدل بهینه‌سازی مبتنی بر‌ شبیه‌سازی را برای مدیریت و زمان‌بندی پروژه‌های توسعۀ محصول جدید در مراکز تحقیق و توسعه ارئه دادند. نتایج این تحقیق نشان می‌دهد‌ روش اولویت‌دهی به فعالیت‌ها، با کمک FCFS دارای بیشترین مقدار تابع هدف (سود زودکرد منهای هزینۀ دیرکرد) است و‌ تفاوت معنی‎‍داری با دیگر روش‎‍ها دارد. پس از استخراج بهترین روش، سناریوهای مختلف مربوط به تعداد منابع در ایستگاه‎‍های کاری که‌ زمان انتظار طولانی داشتند‌،‌ تحلیل شد. این امر‌ نشان می‎‍دهد دو‌برابر‌کردن تعداد منابع در این ایستگاه‎‍ها‌، موجب بهبود تابع هدف و مثبت‌کردن آن می‌شود.

دمیر و اردن[xiv] (2020) از دو روش فراابتکاری الگوریتم ژنتیک و الگوریتم بهینه‌سازی کلونی مورچه‌ها، برای حل مسئلۀ برنامه‌ریزی و زمان‌بندی برای کارهایی که به‌صورت تصادفی و با تاریخ تحویل مشخص به کارگاه می‌رسند، با هدف به حداقل رساندن زودکرد و دیرکرد کارها استفاده کرده‌اند. نتیجه نشان داد‌ الگوریتم کلونی مورچه‌ها بهتر از الگوریتم ژنتیک عمل می‌کند. علاوه بر این، پیشنهاد شده است که رویکردهای یکپارچه کارایی بیشتری را نسبت‌به رویکردهای فردی فراهم می‌کنند.

آیاسی و همکاران[xv] (2020) در مقاله‌ای با عنوان «طراحی یک مدل بهینه‌سازی مبتنی بر شبیه‌سازی چند هدفۀ تصادفی به‌منظور برنامه‌ریزی فروش و عملیات در حالت تولید مبتنی بر سفارش»، با استفاده از رویکرد بهینه‌سازی مبتنی بر شبیه‌سازی، یک مدل چند هدفه را طراحی‌ و فضای شدنی راه‌حل‌ها را برای مقادیر نزدیک به بهینه، به‌منظور مدیریت و کنترل سطح موجودی و نسبت انعطاف‌پذیری در ساختارهای فروش و عرضه، بررسی کرده‌اند.

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

آکل و همکاران[xvi] (2022) در مقاله‌ای با عنوان «بهینه‌سازی هم‌زمان برنامه‌ریزی استراتژیک نیروی انسانی و برنامه‌ریزی نگه‌داری پیشگیرانه: رویکرد شبیه‌سازی-بهینه‌سازی»، یک چارچوب شبیه‌سازی-بهینه‌سازی را پیشنهاد می‌کنند‌ که در آن یک سیستم نگهداری از دارایی‌های با ارزش بالا از‌طریق مدل شبیه‌سازی رویداد گسسته در مقیاس بزرگ مدل‌سازی می‌شود.

احمدیان و همکاران[xvii] (2021) دربارۀ مسئلۀ تولید به‌موقع (JIT) در حالت مسئلۀ زمان‌بندی کارگاهی که در آن هر عملیات ‌ یک سررسید مشخص دارد و هرگونه انحراف از زمان اتمام عملیات از سررسید آن، مستلزم جریمۀ زودهنگام یا تأخیر است، یک الگوریتم جست‌وجوی همسایگی متغیر (VNS) را برای حل JIT-JSS ارائه دادند.

امیرخانی و همکاران[xviii] (2017) در مقاله‌ای با عنوان «رویکرد شبیه‌سازی- بهینه‌سازی برای یافتن توالی بهینه در مسئلۀ پویای تولید کارگاهی دارای خرابی و دوباره‌کاری»، ادغام شبیه‌سازی و الگوریتم ژنتیک رویکردی را پیشنهاد کردند تا بتوان از آن در هر مسئلۀ تولید کارگاهی استفاده کرد که قابلیت مدل‌شدن با شبیه‌سازی را داشته باشد. در رویکرد پیشنهادی برای در نظر گرفتن محدودیت‌های مسئله، از مدل شبیه‌سازی و برای بهینه‌سازی از الگوریتم ژنتیک استفاده می‌شود.

در مرجع (طالبی و غزالی[xix]، 2009) الگوریتم‌های فراابتکاری از الگوریتم‌های تصادفی‌اند که برای یافتن پاسخ بهینه به کار می‌روند. روش‌ها و الگوریتم‌های بهینه‌سازی به دو دستۀ الگوریتم‌های دقیق و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند. ازنظر دوکراوغلو و همکاران[xx] (2019)، الگوریتم‌های دقیق قادر به یافتن جواب بهینه به‌صورت دقیق‌اند، اما دربارۀ مسائل بهینه‌سازی سخت، کارایی کافی را ندارند و زمان اجرای آنها متناسب با ابعاد مسائل به‌صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت‌‌اند. دو مشکل اصلی الگوریتم‌های ابتکاری، گیر‌افتادن آنها در نقاط بهینۀ محلی، همگرایی زودرس به این نقاط است. الگوریتم‌های فراابتکاری برای حل‌ مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در‌واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی‌‌اند که دارای راهکارهای برون‌رفت از نقاط بهینۀ محلی‌اند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند. الگوریتم جست‌وجوی پراکنده یکی از این روش‌هاست.

در مرجع (نادری و رویز[xxi]، 2014) جست‌وجوی پراکنشی یک الگوریتم فراابتکاری تکاملی مبتنی بر جمعیت است که از ‌مجموعه جواب‌های مرجع استفاده می‌کند و با ترکیب آنها، جواب‌های جدیدی می‌سازد. این روش با ساخت یک جمعیت اولیه به نام Pop شروع می‌کند. این جمعیت اولیه باید معیارهای تنوع و کیفیت را برآورده کند؛ سپس با استفاده از جواب‌های خوب جمعیت اولیه‌، یک مجموعه مرجع (RefSet) با اندازۀ متوسط ساخته می‌شود. جواب‌های انتخاب‌شده از جمعیت اولیه با یکدیگر ترکیب می‌شوند تا جواب‌هایی برای شروع بهبود در یک الگوریتم فراابتکاری مبتنی بر جمعیت ایجاد کنند. در این روش، مجموعۀ مرجع و همچنین جمعیت جواب‌ها به‌روز‌رسانی می‌شوند تا همواره دارای کیفیت بالا و تنوع کافی باشند.

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

3- روش‌شناسی پژوهش

3-1 مدل مفهومی ریاضی

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

مجموعه‌ها‌:

 : مجموعه ماشین‌ها

 : مجموعه کار‌ها

: : مجموعه عملیات‌ها

 : مجموعه نوبت‌ها

پارامترها‌:

: هزینۀ هر واحد زمانی زودکرد

: هزینۀ هر واحد زمانی دیرکرد

: تاریخ تحویل کار ام

: میانگین مدت‌زمان انجام عملیات  ام از کار  ام

: انحراف معیار مدت‌زمان انجام عملیات  ام از کار  ام

: عملیات  ام از کار  ام

: تعداد ماشین‌ها

: تعداد کارها

: زمان پردازش احتمالی عملیات که‌ توزیع آماری مختص به خورد را دارد؛ برای مثال توزیع نرمال با میانگین و واریانس زیر:

: یک عدد بزرگ

متغیرهای این مدل عبارت‌اند از:

: میزان واحد زمانی زودکرد کار ام

: میزان واحد زمانی زودکرد ام

: تاریخ تکمیل کار ام

: متغیر باینری 0 یا 1 . اگر عملیات  بر ماشین در نوبت  انجام شود، برابر 1 و در غیر این صورت 0.

: زمان شروع عملیات

: زمان شروع کار ماشین در نوبت

: تعداد عملیات‌های اختصاص‌یافته به ماشین

 با توجه به مجموعه‌ها، پارامترها و متغیرهای مسئله به‌صورت زیر مدل‎‍سازی می‌شود‌:

رابطۀ 1 بیانگر تابع هدف است که حداقل‌کردن مجموع هزینه‎‍های دیرکرد و زودکرد است و رابطۀ 2 میزان زودکرد هر کار را تعریف می‌کند. رابطۀ 3 میزان دیرکرد هر کار و رابطۀ 4 زمان تکمیل هر کار را تعریف می‎‍‌کند. همچنین رابطۀ 5، محدودیت‎‍های پیش‎‍نیازی را معرفی می‌کند. این محدودیت زمان شروع هر عملیات را به اتمام عملیات قبلی، از همان کار محدود می‎‌کند. رابطۀ 6 این الزام را به وجود می‎‍آورد که ‌یک ماشین ‌ در صورتی کار در نوبت  را انجام می‌دهد که کار آن ماشین در نوبت k به اتمام رسیده باشد .‌رابطه‌های 7 و 8 این الزام را به وجود می‎‍آورند که در صورتی یک عملیات ‌ شروع می‌شود که هم محدودیت پیش‎‍نیازی (‌عملیات قبلی آن به اتمام رسیده باشد) و هم محدودیت ماشین (ماشین مورد نیاز آن بیکار باشد) رعایت شده باشند. رابطۀ 9 موجب می‌شود که برای یک عملیات، تنها یک نوبت از بین نوبت‎‍های ممکن انتخاب شود. رابطۀ 10 موجب می‎‍شود که برا‌ی هر عملیات از ماشین اختصاص‌یافته به آن عملیات، نوبت اجرای عملیات تعیین شود. رابطه‌های 11 و 12 نوع متغیرها را معرفی می‎‍کنند.

در مسئلۀ جاری علاوه بر روابط بالا، دو محدودیت زیر نیز افزوده می‌شود‌:

الف- محدودیت مربوط به بودجه‌:

که در رابطۀ فوق  هزینۀ خرید ماشین  و  کل بودجه در دسترس است.

ب- محدودیت مربوط به فضا

که در رابطۀ فوق  فضای مورد نیاز ماشین  و  کل فضای در دسترس است.

3-2 اعتبار‌سنجی مدل ریاضی

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

3-3 روش شبیه‌سازی برای حل مسئله

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

3-4 روش‎‍های اولویت‎‍دهی

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

در این مقاله از هفت قانون اولویت‎‍دهی متداول استفاده شده است که مطابق جدول 1 عبارت‌اند از‌:

                                                                           i.            جدول 1- روش‌های اولویت‌دهی به کار گرفته شده

1.Table 1- Prioritization methods

برای تولید زمان اتمام مورد انتظار برای استفاده در قانون زودترین زمان اتمام مورد انتظار کار، از روش کل محتوای کار استفاده می‎‍شود که از رابطۀ زیر به دست می‎‍آید:

‌ در این رابطه شمارۀ کار،  زمان مورد انتظار تخمین‌زده برای تحویل کار ، زمان ورود کار ام و زمان پردازش کار بر ماشین  ام است.

برای به دست آوردن نرخ بحرانی از رابطۀ زیر استفاده می‎‍شود‌:

برای به دست آوردن متوسط زمان تأخیر در تحویل کالا (SLACK) از رابطۀ زیر استفاده می‎‍شود‌:

3-5 معرفی نرم‌افزار شبیه‌سازی ارنا (Arena)

نرم‌افزار ارنا بستۀ نرم‌افزاری برای شبیه‌سازی سیستم‌های گسستۀ پیشامد است که‌ شرکت systems modeling آن را به بازار ارائه کرده و نرم‌افزاری کامل برای انجام مطالعات شبیه‌سازی است و تمام قدم‌های یک مطالعۀ شبیه‌سازی را پشتیبانی می‌کند. این نرم‌افزار قابلیت مدل‌سازی شی‌ءگرا را نیز دارد و در عین حال به‌راحتی با سیستم‌عامل ویندوز پشتیبانی می‌شود. ارنا نرم‌افزاری کاربردی، با قابلیت مدل‌سازی بالا و ابزاری قدرتمند برای شبیه‌سازی است که به کاربران اجازه می‌دهد تا مدل شبیه‌سازی را ایجاد و روی آن آزمایش انجام دهند و در عین حال رابط کاربری آسانی دارد.

3-6 مدل شبیه‌سازی شده در نرم افزار Arena 14

شبیه‌سازی، بیان رفتار پویای یک سیستم در حالت پایدار به‌واسطۀ حرکت آن از یک وضعیت به وضعیت دیگر براساس قواعد عملیاتی تعریف شده است. اصولاً در شبیه‌سازی، از کامپیوتر برای ارزیابی عددی یک مدل استفاده می‌شود و در آن داده‌ها به‌جهت تخمین ویژگی‌های مدنظر مدل جمع‌آوری می‌شوند. شبیه‌سازی کامپیوتری در عام‌ترین معنایش، فرایند طراحی مدلی ریاضی- منطقی از سیستم واقعی و آزمایش این مدل با کامپیوتر است. در این تحقیق نیز، پس از مدل‎‍سازی سیستم مربوط به مسئلۀ تولید کارگاهی، آن را در نرم‌افزار Arena 14 پیاده‎‍سازی می‌کنیم و سپس پس از بررسی صحت و اعتبار مدل با دادن داده‎‍های ورودی به مسئله و همچنین تغییر قوانین اولویت‎‍دهی به کارها، به مقدار بهینۀ مدنظر نزدیک می‎‍شویم. شکل 1 بخشی از مدل شبیه‎‍سازی‌شدۀ مسئله را نشان می‎‍دهد.

شکل 1- بخشی از مدل شبیه‎‍سازی‌شدۀ زمان‌بندی تولید کارگاهی

Figure 1- Part of the simulated job shop production scheduling model

3-7 اعتبارسنجی مدل شبیه‌سازی

شایان ذکر است که دربارۀ اعتبار‌سنجی مدل شبیه‌سازی‌شده، مدل در حالت اولیه بدون محدودیت‌های فضا و بودجه و در حالت پایۀ FIFO اجرا‌ و با توجه به خروجی به دست آمده دربارۀ زمان تکمیل قطعات و مقایسۀ آن با شرایط واقعی در کارگاه تولیدی‌، تأیید شد؛ برای مثال تابع هدف مسئله که بیانگر حداقل‌کردن مجموع هزینه‎‍های دیرکرد و زودکرد انجام کارهاست، در حالت پایۀ شبیه‌سازی (اولویت براساس زمان ورود کارها و تعداد موجود هر تجهیز، 1 عدد و اجرای 100 بار شبیه‌سازی در هر تکرار) برابر حداقل 25/8870 و حداکثر 95/9315 واحد پولی است که در حالت واقعی کارگاه این عدد 9214واحد پولی بوده است (این نتایج در جدول 5 و بخش مثال عددی‌ مشاهده‌شدنی است). گفتنی است موضوع محدودیت‌های بودجه و فضا به‌منظور محاسبۀ تعداد تجهیزات در ماژول OptQuest اضافه و اجرا می‌شود که نتایج آن را تصمیم‌گیران بررسی می‌کنند.

4- مثال عددی

به‌منظور نشان‌دادن مکانیزم، کارکرد مدل یک کارگاه تولیدی در نظر گرفته شده است که در آن چهار نوع قطعۀ 1، 2 ، 3 و 4 تولید می‎‍شود. در این مدل درصد تولید روزانۀ هر قطعه مشخص است. هر‌یک از قطعات، موعد تحویل مشخصی دارند. قطعات بر ماشین‎‍ها بر‌اساس قوانین زمان‌بندی مشخصی قرار می‎‍گیرند. در این کارگاه پنج سلول تولیدی داریم. توالی قطعات و زمان عملیات هر قطعه در هر سلول بر هر ماشین مطابق جدول 2 است:

                                                                                ii.            جدول 2- اطلاعات مربوط به مثال عددی

1. Table 2- Information related to numerical example

زمان بین دو ورود قطعات متوالی (‌تمامی انواع‌) دارای توزیع نمایی با میانگین 10 دقیقه است. اولین قطعه در زمان صفر وارد می‎‍شود. به‌طور پیش‌فرض، سلول 1 ،2 ،4 و 5 هر‌کدام شامل یک ماشین است. سلول شمارۀ 3 دارای دو ماشین است. (ماشین دستی و ماشین خودکار‌ که ماشین خودکار در 70درصد زمان ماشین دستی، فرایند عملیاتی را انجام می‌دهد‌). زمان انتقال بین سلول‎‍ها 5/1 دقیقه فرض شده است. قطعات تولیدی ایستگاه پنجم به احتمال 3درصد‌ به دوباره‎‍کاری نیاز دارند و بعد از آن سالم می‎‍شوند. ماشین دستی سلول 3 خرابی با توزیع پواسون با نرخ 1 بار در ساعت دارد و زمان تعمیر آن دارای توزیع یکنواخت 5 الی 10 دقیقه است. هزینة دیرکرد هر کار، 20 واحد پول و هزینة زودکرد هر کار 5 واحد پول است.

همچنین قیمت هر ماشین مطابق جدول زیر است:

                                                                           iii.            جدول 3- اطلاعات مربوط به هزینه‌های ماشین

1. Table 3- Information about the costs of the Machine

تعداد ماشین‌های سلول 1 ، 2 ،4 و 5 حداقل 1 و حداکثر 3 ماشین است. دربارۀ سلول 3، تعداد ماشین خودکار حداقل 1 و حداکثر 3 و ماشین دستی حداقل 1 و حداکثر 3 ماشین در نظر گرفته شده است. بودجۀ تأیید‌شده برای آنها حداکثر 8500 واحد پول است.

رابطۀ ریاضی محدودیت فوق در ارنا به شرح زیر است:

فضای مورد نیاز برای هر ماشین نیز مطابق جدول زیر است‌:

                                                                            iv.            جدول 4- اطلاعات مربوط به مساحت ماشین

1. Table 4- Information about the area of the Machine

حداکثر فضای در دسترس برای ماشین‌آلات 800 متر مربع است.

رابطۀ ریاضی محدودیت فوق در ارنا به شرح زیر است:

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

5- تحلیل یافته‎‍های پژوهش با کمک طراحی آزمایش‎‍ها

5-1 نتایج اجرای شبیه‎‍سازی

همان‎‍طور که در قسمت شرح مسئله بیان شد، مدل ریاضی‌ بررسی‌شده در این تحقیق دارای تابع هدف بر مبنای مجموع هزینه‎‍های دیرکرد و زود کرد است. برای حل این مسئله پس از شبیه‎‍سازی در نرم‌افزار Arena 14، در سلول‎‍ها قوانین اولویت‎‍دهی کارها در نظر گرفته شده است که در صورت ایجاد صف یکی از قوانین برای صف (در تمام سلول‌ها به‌طور مشترک) در نظر گرفته شود. نتایج به دست آمده برای مسئلۀ عددی مطرح‌شده پس از 4 بار آزمایش با تکرار 100 مرتبه به ازای هر قانون، اولویت‎‍بندی برای حالت بدون محدودیت‌های بودجه و فضا و همچنین اجرای شبیه‌سازی با کمک الگوریتم جست‌وجوی پراکنده در حالت داشتن محدودیت‌های بودجه و فضا، به شرح جدول 5 است:

                                                                               v.            جدول 5- نتایج به دست آمده از شبیه‌سازی

1. Table 5- Simulation results

6- بحث

به‌منظور بررسی نتایج به دست آمده از مدل شبیه‌سازی‌شده و مثال عددی، بحث دربارۀ در نظر گرفتن ماشین‌آلات پیش‌فرض مدل و همچنین تعداد بهینۀ پیشنهادی تعداد ماشین‌آلات توسط مدل، به شرح زیر ارائه می‌شود:

6-1 طراحی آزمایش‌ها به کمک تحلیل واریانس برای حالت پیش‌فرض تعداد ماشین‌آلات

به‌منظور تعیین بهترین توالی، ابتدا آنالیز واریانس به‌منظور بررسی تساوی میانگین بر‌ داده‌های فوق انجام گرفته است‌:

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

با توجه به جدول 6، چون مقدار P-value کوچک‌تر از 05/0 است، بنابراین فرض صفر رد می‌شود و بین میانگین‌ها اختلاف معنی‌دار وجود دارد.

                                                                                               vi.            جدول 6- آنالیز واریانس

1. Table 6- Analysis of variance

به‌منظور دسته‌بندی گروه‌های متفاوت از روش توکی استفاده شده و نتایج در جدول 7 به دست آمده است:

                                                                          vii.            جدول7- دسته‌بندی نتایج با کمک روش توکی

1. Table 7- Classification of results using Tukey's method

همان‌طور که در جدول 7 مشاهده می‌شود، دو گروه ایجاد شده است و چون تابع هدف بر مبنای هزینه است، بنابراین گروه دوم پذیرش می‌شود که‌ هزینۀ کمتری دارد‌‌. به‌عبارتی روش LPT دارای کمترین هزینه است، ولی از‌لحاظ آماری، نتایج روش‎‍های FIFO، LIFO،EDD و SLACK نیز پذیرفتنی است.

6-2 مقایسۀ نتایج با فرض تعداد پیش‌فرض ماشین‌آلات و تعداد بهینۀ ماشین‌آلات

با توجه به نتایج حاصل‌شده در دو مرحلۀ قبل، با در نظر گرفتن تعداد پیش‌فرض ماشین‌آلات، روش LPT با توجه به تابع هدف حداقل‌‌کردن مجموع هزینه‎‍های دیرکرد و زودکرد انجام کارها، با حداقل عدد برابر 94/8710 واحد پولی، بهترین پاسخ را‌ می‌دهد؛ اما اگر بخواهیم با افزودن تعداد ماشین‌آلات، هزینۀ دیرکرد و زودکرد را حداقل کنیم، روش LPT و CR بهترین نتیجه را با کمک استفاده از الگوریتم جست‌وجوی پراکنده در شبیه‌سازی برای تابع هدف به ما خواهند داد که در این نتایج، محدودیت‌های هزینه و فضا نیز رعایت شده است، این عدد برای هر دو روش 64/4769 واحد پولی است.

7- نتیجه‌گیری و پیشنهادها

در این تحقیق ابتدا مدل مفهومی ریاضی مسئلۀ تعیین توالی کارها در تولید کارگاهی، با هدف حداقل‌کردن هزینه‌های زودکرد و دیرکرد و با محدودیت‌های اضافی فضا و بودجه بیان شد. در ادامه، مدل شبیه‌سازی مسئله طراحی و سپس با یک مثال عددی با کمک نرم‌افزار ارنا اجرا و بررسی و تحلیل شد، همچنین توالی نزدیک به بهینه نیز، به‌منظور حداقل‌کردن هزینه با کمک نرم‌افزار Minitab و آنالیز واریانس مشخص شد که روش LPT با توجه به تعداد ماشین‌های پیش‌فرض و روش‌های LPT و CR با توجه به تعداد بهینۀ ماشین‌آلات با در نظر گرفتن محدودیت هزینه و فضا و استفاده از الگوریتم جست‌وجوی پراکنده، کمترین هزینه را دارند. در حالت ماشین‌آلات‌ پیش‌فرض، از‌لحاظ آماری نتایج روش‌های FIFO، LIFO،EDD و SLACK نیز پذیرفتنی است. همان‌طور که مشاهده شد، یکی از ویژگی‌های بارز شبیه‌سازی این است که با حداقل فاصلۀ مسئله با دنیای واقعی (یعنی‌ حذف‌نکردن محدودیت‌ها و پیچیدگی‌ها برای ‌حل مسئله که معمولاً حذف واقعیات در دیگر روش‌های حل مسئله، به‌منظور کاهش پیچیدگی‌ و امکان حل مسئله، انجام می‌شود)، نسبت‌به حل مسئله و همچنین اعمال سناریوهای تصمیم‌گیری اقدام می‌شود که این موضوع کمک شایانی تصمیم‌گیری مدیران می‌کند. به‌طور کلی بیشتر اوقات مطالعۀ فیزیکی سیستم‌ها بسیار مشکل و هزینه‌بر و یا حتی ناممکن است؛ بنابراین در این شرایط باید از مدل جایگزین برای مطالعۀ سیستم استفاده کرد. در صورتی که مدل ساده باشد، از روش‌های تحلیلی برای حل مدل استفاده می‌شود، در مدل‌های پیچیده یا مدل‌هایی که امکان مدل‌سازی آن به روش‌های تحلیلی وجود نداشته باشد، از شبیه‌سازی استفاده می‌شود. استفاده از شبیه‌سازی علاوه بر زمان‌بندی تولید کارگاهی در دیگر فرایندهای تولیدی نظیر Flow Shop و ... نیز استفاده می‌شود. همچنین برای زمان‌بندی مسائل حمل و نقل زمینی و هوایی نیز، از این تکنیک استفاده می‌شود.

[i] Pinedo

[ii] Sajadi & Shahbazi

[iii] Molaee et al.

[iv] Vieira et al.

[v] Jain & Meeran

[vi] Banks & Nelson

[vii] Blackstone et al.

[viii] Chan et al.

[ix] Weng & Ren

[x] Azadivar

[xi] Klemmt et al.

[xii] Do Amaral et al.

[xiii] Shahbazi et al.

[xiv] Demir & Erden

[xv] Aiassi et al.

[xvi] Akl et al.

[xvii] Ahmadian et al.

[xviii] Amirkhani et al.

[xix] Talbi & Ghazali

[xx] Dokeroglu et al.

[xxi] Naderi & Ruiz