ارائه الگوریتم فراابتکاری ترکیبی بهبود‌یافته برای حل زمان‌بندی کار کارگاهی انعطاف‌پذیر

مقدمه

با پیشرفت تولید و صنعت، برنامه‌ریزی تولید به یک مشکل مهم برای شرکت‌های تولیدی تبدیل شده است (آن^[1] و همکاران، 2021). از طرفی، در جهان رقابتی حاضر تعیین توالی و زمان‌بندی مؤثر ضرورتی برای بقا در فضای بازار است (حاجی‌بابایی و بهنامیان، 1401). برای زنده ماندن در بازار رقابتی مدرن، که به هزینه کمتر و چرخه عمر محصول کوتاه‌تر نیاز دارد، یک شرکت باید سریع و دقیق به خواسته‌های مشتری پاسخ دهد. برنامه‌ریزی و زمان‌بندی مؤثر، نقش مهمی در این سازگاری دارند (بانهارنساکان^[2] و همکاران، 2012). شرکت‌ها از سوی محیط تحت فشار بوده و زمان و برآورده‌سازی نیازهای مشتری برای حفظ رضایت در برنامه‌ریزی تولید نقش مهمی ایفا می‌کنند (کانداکچی و کولاک^[3]، 2016). به‌طوری‌که با افزایش تقاضا برای کالاهای شخصی و سفارشی‌شده، تغییرات سریع و پیش‌بینی‌نشده‌ای را در فرایند تولید شرکت‌ها ایجاد کرده است. برای رقابتی ماندن، شرکت‌های تولیدی باید برای واکنش سریع به این تغییرات غیرمنتظره در تقاضا، کالاها را با هزینه‌های کاهش‌یافته تولید کنند که این امر به‌واسطه تولید انعطاف‌پذیر و فردی انجام می‌شود (دینگ و گئو^[4]، 2020).

برنامه‌ریزی و کنترل تولید، تصمیم‌گیری شفاف و سطح بالا در زمان کوتاه‌تری در واکنش به بروز خطاها و حوادث غیرمترقبه را ممکن می‌سازد. برنامه‌ریزی تولید مدرن و استراتژی‌های کنترل به بهینه‌سازی مداوم نیازمندند (دِنکِنا^[5] و همکاران، 2021). ازآنجایی‌که زمان همواره یک منبع محدود بوده، فعالیت‌ها باید به‌گونه‌ای زمان‌بندی شوند تا از مصرف بهینه این منبع اطمینان حاصل شود. زمان‌بندی یک فرایند تصمیم‌گیری است که بهینه‌سازی یک یا چند معیار را بر عهده دارد (باکر^[6]، 1974). زمان‌بندی تأثیر زیادی بر افزایش کارایی و تحقق اهداف دارد، به‌نحوی‌که زمان‌بندی مؤثر سبب بهبود معیارهای عملکردی خط تولید نظیر خروجی خط، هزینه‌های تولید، درصد استفاده از ایستگاه گلوگاه و رضایتمندی مشتریان خواهد شد (اسدی گَنگِراج و نهاوندی، 2014). در محیط‌های رقابتی، برنامه‌ریزی مؤثر یک ضرورت برای بقا در بازار محسوب می‌گردد (سینگ و ماهاپاترا^[7]، 2016). بنگاه‌های تولیدی باید به بهبود راندمان تولید خود ادامه داده و زمان‌بندی معقول کارگاهی می‌تواند کارایی تولید و تحویل محصول را بهبود بخشد. همچنین زمان‌بندی مناسب از طریق کاهش زمان بیکاری ماشین‌ها، هزینه‌های مصرف انرژی را کاهش دهد (لئو^[8] و همکاران، 2021).

برنامه‌ریزی زمان‌بندی یک فرایند تصمیم‌گیری حیاتی در صنایع تولید و خدمات است. هدف اصلی برنامه‌ریزی، تخصیص منابع محدود در دسترس برای انجام یک گروه از وظایف در طی یک دوره زمانی به‌منظور بهینه‌سازی برخی از شاخص‌های عملکرد است (ماریچِلوام و گیتا^[9]، 2021). منابع و کارها در زمان‌بندی ممکن است انواع گوناگونی داشته باشد و با توسعه جهان صنعتی، منابع مربوطه بحرانی‌تر می‌شود. زمان‌بندی این منابع به افزایش سوددِهی یک سازمان منجر می‌شود (حاجی‌بابایی و بهنامیان، 1401). سیستم‌های تولید مدرن که در آن ماشین‌آلات پیشرفته وجود دارند، قادر به انجام بیش از یک نوع کار هستند و زمان‌بندی کار کارگاهی انعطاف‌پذیر را به وجود می‌آورند (فان^[10] و همکاران، 2021). یافتن راه‌حل بهینه برای مسائل با اندازه متوسط و بزرگ در یک زمان مناسب برای آن امکان‌پذیر نبوده و به‌صورت کلی تعداد حالات ممکن در آن بسیار زیاد است. محققان نه‌تنها به دلیل پیچیدگی بلکه به دلیل کاربرد مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر در پیِ شناخت و درک فزاینده نسبت به آن هستند (بیسولی^[11] و همکاران، 2021).

زمان‌بندی کار کارگاهی انعطاف‌پذیر یکی از مسائل ترکیبی تولید بوده که به دلیل کاربردهای عملی آن در سیستم‌های تولیدی جدید و در حال ظهور باهدف مدل‌سازی و بهینه‌سازی موقعیت‌های پیچیده‌تر نیازهای صنعت حائز اهمیت است (سِرنا^[12] و همکاران، 2021) و پیوسته محققان تلاش می‌کنند بهبود عملکرد الگوریتم‌های فراابتکاری مورد استفاده برای حل مسئله کار کارگاهی انعطاف‌پذیر را بهبود بخشند که این اقدام موجب افزایش کارایی تولید، کاهش هزینه‌ها، بهبود زمان تحویل محصول و کاهش مصرف انرژی را در برخواهد داشت (احمدیان و همکاران، 2021؛ محمدی، 2015). با تغییر سریع صنعت در مقیاس بزرگ، نیاز به یک سیستم چندعاملی پیچیده که قادر به حل مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر باشد، آشکار می‌گردد (یوآن^[13] و همکاران، 2023). افزودن دانش به الگوریتم‌های هوشمند راه خوبی برای حل مسائل زمان‌بندی پیچیده و سخت در زمان معقول و قابل قبول است (لی^[14] و همکاران، 2021). در دنیای واقعی نیز به دلیل پیچیدگی‌های موجود بهتر قابل‌استفاده بوده و محققان به‌صورت پیوسته با ایجاد تغییر در روش‌های فراابتکاری به دنبال یافتن روش‌های بهبودیافته و جواب‌های بهینه هستند. به‌عبارت‌دیگر، الگوریتم‌های فراابتکاری یک رویکرد بسیار مناسب برای حل مسائل بهینه‌سازی هستند، به‌ویژه به‌عنوان مثال بهینه‌سازی NP-hard مانند برنامه‌ریزی بهینه شبکه زنجیره تأمین (رضایی و پیله‌وری، 1401)، مسئله فروشنده دوره‌گرد (صالحی و معصومی، 2020)، مسئله حداکثرسازی نفوذ در شبکه‌های اجتماعی (صالحی و معصومی، 2020) و ... .

توجه به موضوع زمان‌بندی کار کارگاهی انعطاف‌پذیر در صنایع و به‌خصوص در بحث مدیریت زنجیره تأمین نیز مورد توجه جدی قرار گرفته است. چراکه هدف زنجیره تأمین ایجاد پایداری در ساختار تولید است و به‌زعم محققان مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر به‌عنوان یک ساختار عملیات‌ساز می‌تواند این جریان پایدارساز را تسهیل و تقویت نماید (فتحی^[15] و همکاران، 2021). همین مطلب نیز در صنایع دفاعی مطرح است. به‌ویژه اینکه صنعت دفاعی نیازمند یک مدیریت لجستیک قوی، آماده، پیشگامانه و همه‌جانبه است تا بتواند نیازهای پشتیبانی لازم را در مواقع مورد نیاز ارائه دهد (کونووالِنکو و لودویگ^[16]، 2022) و به تعبیری بتواند شوک‌های لحظه‌ای وارده به صنعت را با تولید به‌موقع و زمان‌بندی دقیق کنترل و مدیریت کند (کازرونی و همکاران، 1403). زمان‌بندی کار کارگاهی انعطاف‌پذیر این قابلیت را دارد که بتواند در صنایع دفاعی و کمک به مدیریت پایدار زنجیره تأمین آنان نقش عملیاتی‌تری را بر عهده بگیرد (رولف^[17] و همکاران، 2023).

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

1. مبانی نظری

هرچه از زمان‌های قدیمی‌تر به زمان حال حرکت می‌نماییم تعداد عواملی که در حوزه رقابت نقش ایفا می‌کنند، افزایش می‌یابد. در جهان رقابتی کنونی، بهینه‌سازی زمان‌بندی سیستم‌های تولیدی در محیط کار کارگاهی نیز به‌منظور افزایش توان رقابتی مورد توجه قرار می‌گیرد. امروزه با پیشرفت روزافزون تکنولوژی، متنوع‌شدن نیازها و خواسته‌های مشتریان، حرکت به‌سوی ساخت و تولید بر اساس سفارش مشتری، محیط رقابتی را در بین شرکت‌های تولیدی ایجاد و مشکلاتی را گریبان‌گیر آن‌ها کرده است. افزایش انتظارات مشتری و پیشرفت‌های تکنولوژیکی منجر به افزایش پیچیدگی تولید شده و شرکت‌ها با اختلالات تصادفی روبه‌رو می‌شوند و این امر موجب استفاده غیرمتقارن از ظرفیت تولید می‌گردد. بنابراین تولید مؤثر و کارآمد، برنامه‌ریزی و کنترل به یک مزیت حیاتی در رقابت تبدیل می‌گردد (دِنکِنا و همکاران، 2021). سازمان‌ها باید به تعهدات خود در خصوص زمان تحویل به مشتریان متعهد باشند. زیرا عدم موفقیت انجام این کار ممکن است باعث از بین رفتن قابل‌توجهی از حُسن نیت شود (سینگ و ماهاپاترا، 2016). تولیدکنندگان به دنبال سیستم‌های تولیدی هستند که نیازهای مشتریان نظیر کاهش قیمت، تنوع محصولات، دقت و کیفیت بالا را برآورده سازند. ازاین‌رو، اهمیت به‌کارگیری روش‌هایی کارا جهت استفاده مؤثر از منابع بیشتر از گذشته نیاز می‌شود تا سازمان‌ها بتوانند قدرت پاسخ‌گویی سریع به نیازهای مشتریان را داشته باشند. به نقل از «فرانچا»^[18] و همکاران (2005)، با ادامه فرایند صنعتی‌شدن جهان، منابع بیشتری حالت بحرانی به خود می‌گیرند. امروزه ماشین‌آلات، نیروی انسانی و تسهیلات به‌عنوان منابع بحرانی در تولید و فعالیت‌های خدماتی در نظر گرفته می‌شوند. زمان‌بندی این منابع منجر به ارتقا کارایی، بهره‌وری و در نهایت سودآوری می‌شود. به‌طورکلی، می‌توان گفت که زمان‌بندی، فرایند تخصیص منابع محدود به فعالیت‌ها در طول زمان است که هدف آن بهینه‌سازی یک و یا چند تابع هدف با تخصیص منابع مشخص در یک دوره زمانی معین است (کاسِرس گِلوِز^[19] و همکاران، 2024). مسائل زمان‌بندی و برنامه‌ریزی تولید به دلیل کاربردهای صنعتی متنوع آن‌ها به‌طور گسترده به‌عنوان مسائل بهینه‌سازی موردمطالعه قرارگرفته است. در طول گذشته، محققان توجه ویژه‌ای به ادغام مشکلات زمان‌بندی محیط‌های تولید و سیستم‌های توزیع برای اتخاذ مفروضات واقعی‌تر داشته‌اند. مسائل برنامه‌ریزی تولید، برای کاربردهای صنعتی مختلف مانند تزریق پلاستیک، فرایندهای شیمیایی، صنعت نفت، برنامه‌ریزی خدمات پزشکی، تعمیر و نگهداری، تولید مواد غذایی و تولید دارویی و مشکل مسیریابی وسیله نقلیه در بخش خدمات مناسب است (اِبرو^[20] و همکاران، 2021). برنامه‌ریزی و کنترل تولید، تصمیم‌گیری شفاف و سطح بالا را در زمان کوتاه‌تری در واکنش به بروز خطاها و حوادث غیرمترقبه ممکن می‌کند (دِنکِنا و همکاران، 2021).

مسائل زمان‌بندی در محیط‌های تولیدی به سه دسته مسئله جریان کارگاهی، کار کارگاهی و کار کارگاهی باز تقسیم می‌شوند (روح‌بخش و همکاران، 1402). مسائل زمان‌بندی کار کارگاهی از زمان‌بندی‌های مربوط به شرکت‌های تولیدی مدرن ناشی می‌گردد (ژی^[21] و همکاران، 2022). مسئله زمان‌بندی کار کارگاهی عبارت است از یافتن توالی بهینه انجام عملیات کارهای مختلف و مرتبط با هر ماشین بر روی آن ماشین، این مسئله معمولاً با هدف کمینه کردن طول برنامه زمان‌بندی مورد بررسی قرار می‌گیرد (شجاعی برجوئی و همکاران، 1399). زمان‌بندی کار کارگاهی انعطاف‌پذیر بسط‌یافته زمان‌بندی کار کارگاهی است. هنگامی‌که هر عملیات از یک کار می‌تواند روی یک ماشین از مجموعه ماشین‌های در دسترس برای پردازش آن انجام شود (پزِلا^[22] و همکاران، 2008). با توجه به اهمیت زیاد و ارتباط با صنعت مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر موجب برانگیختن مطالعات گسترده‌ای از دیدگاه‌های مختلف در این زمینه شده است (یوآن و همکاران، 2023).

زمان‌بندی کار کارگاهی انعطاف‌پذیر بسیار مشکل‌تر از زمان‌بندی کار کارگاهی بوده، زیرا شامل مسئله اختصاص عملیات به ماشین‌ها نیز است. زمان‌بندی کار کارگاهی انعطاف‌پذیر برای اولین بار در سال 1990 توسط براکر و شِلی معرفی گردید (براکر و شِلی^[23]، 1990). مسئله زمان‌بندی کار کارگاهی منعطف از معروف‌ترین مسائل زمان‌بندی است. در این سیستم تولیدی، تعداد n کاربر، m ماشین با لحاظ کردن توالی معین برای هر کار اجرا می‌شوند. هر کار از تعدادی از عمل‌های مختلف تشکیل شده است. عمل‌های هر کار دارای توالی معینی هستند. هدف از پژوهش در محیط کار کارگاهی منعطف، تعیین زمان‌بندی شروع عمل‌ها و مشخص ساختن توالی آن‌ها بر تجهیزات با هدف کمینه‌سازی زمان تولید است (نیکوئی و همکاران، 1403). مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر به‌عنوان یکی از مسائل ترکیبی به دلیل کاربردهای عملی آن در سیستم‌های تولیدی جدید در حال ظهور به‌منظور مدل‌سازی و بهینه‌سازی موقعیت‌های پیچیده‌تر که نیازهای فعلی صنعت را بهتر منعکس می‌کند به‌طور گسترده مورد مطالعه قرار گرفته است (سِرنا و همکاران، 2021). تحقیقات چند دهه اخیر نشان می‌دهد که به‌طورکلی گرایش محققان در بررسی مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر به سمت روش‌های فراابتکاری است. همچنین جهت حل مسائل زمان‌بندی کار کارگاهی انعطاف‌پذیر در ابعاد بزرگ که نیاز ضروری جامعه فعلی است چاره‌ای جز استفاده از الگوریتم‌های فراابتکاری نیست (کوماری^[24] و همکاران، 2023). با توجه به شرایط پیچیده در کارگاه، اکثر الگوریتم‌های زمان‌بندی مرسوم، الزامات فوری، پیچیدگی و پویایی را در مسائل زمان‌بندی کارگاهی برآورده نمی‌کنند. در مقایسه با الگوریتم‌های استاتیک، الگوریتم‌های زمان‌بندی پویا، بهتر می‌توانند الزامات را در موقعیت‌های واقعی برآورده کنند (لئو و همکاران، 2015). برای به دست آوردن راه‌حل‌های با کیفیت بالا در زمان‌های محاسباتی قابل قبول، رویکرد ترکیبی، از استراتژی‌های جستجوی محلی در الگوریتم‌های فراابتکاری باعث بهبودهای قابل ‌توجهی در الگوریتم‌ها می‌شود (اِبرو و همکاران، 2021). روش ترکیب الگوریتم‌ها منجر به تولید الگوریتم‌های کارآمدتر و قدرتمندتر می‌گردد (دفرشا و موحد^[25]، 2018). جمعیت اولیه یکی از ویژگی‌های الگوریتم‌های فراابتکاری (تکاملی) است که بر سرعت هم‌گرایی و کیفیت راه‌حل نهایی تأثیر می‌گذارد (بهشتی‌نیا و قاضی وکیلی، 1394).

2. پیشینه‌ پژوهش

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

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

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

جدول 1: جایگاه تحقیق پیشِ‌رو نسبت به تحقیقات پیشین

در جدول زیر مروری بر یافته‌های مطالعات داخلی و خارجی مرتبط با زمینه پژوهش انجام شده است.

جدول 2: مروری بر مطالعات داخلی و خارجی

3. مفروضات مسئله

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

مفروضات مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر:

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

4. روش‌شناسی

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

5. مراحل اجرای الگوریتم ژنتیک

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

6. الگوریتم جستجوی ممنوعه

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

6-1. ساختار کلی الگوریتم جستجوی ممنوعه

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

6-2. الگوریتم پیشنهادی TS-GA

برای حل مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر یک الگوریتم ترکیبی با نام TS-GA که حاصل از ادغام دو الگوریتم قبلی است ارائه شده است. الگوریتم پیشنهادی TS-GA مهم بودن و اثرگذاری جمعیت اولیه را در جواب الگوریتم فراابتکاری را مد نظر قرار داده و روش جدیدی برای ایجاد جمعیت اولیه الگوریتم ژنتیک پیشنهاد داده و آثار آن را مورد بررسی قرار داده است. در الگوریتم پیشنهادی در ابتدا مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر از طریق الگوریتم جستجوی ممنوعه حل‌شده و پس از رسیدن به جواب بهینه، لیست ممنوعه تشکیل‌شده در این الگوریتم بر اساس بهترین جواب‌ها مرتب‌سازی شده و در ادامه این لیست (به تعداد مورد نیاز کروموزوم‌های تعریف‌شده در الگوریتم ژنتیک) به‌عنوان جمعیت اولیه وارد الگوریتم ژنتیک شده و این الگوریتم فعال گردیده و مجدد مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر را حل و جواب بهینه نهایی پس از گذر از دو الگوریتم فراابتکاری حاصل می‌گردد. با توجه به اینکه اعضای لیست ممنوعه مجموعه‌ای از جواب‌های بهینه هستند که با یافتن هر جواب بهتر، جواب قبلی به داخل این لیست هدایت می‌شود و این لیست با هر حرکت و رسیدن به جواب بهتر بعدی به‌روزرسانی می‌گردد. پس در این لیست مجموعه‌ای از جواب‌هایی وجود دارد که در مواقعی در جستجوی همسایگی الگوریتم جستجوی ممنوعه جواب بهینه برای مسئله بوده است. حال می‌توان ادعا نمود که مجموعه لیست ممنوعه که به‌عنوان جمعیت اولیه الگوریتم ژنتیک قرار گرفته و به‌جای اینکه جمعیت اولیه به‌صورت تصادفی ایجاد گردد، به‌صورت خالص و اصلاح‌شده تولید می‌گردد و نتیجه بهتری ارائه خواهد نمود. مراحل طراحی و پیاده‌سازی الگوریتم پیشنهادی TS-GA در شکل (1)، نشان داده شده است.

شکل 1: فلوچارت و مراحل طراحی الگوریتم TS-GA

در این قسمت برای ارزیابی کارایی الگوریتم پیشنهادی، عملکرد آن را براساس بهترین جواب ممکن با سایر الگوریتم‌ها از طریق حل 5 نمونه مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر مقیاس کوچک و متوسط و حل 4 نمونه مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر مقیاس بزرگ که جزئیات آن در جداول (3) و (4)، نشان داده شده مورد بررسی قرارگرفته‌اند. همچنین برای بررسی بیشتر الگوریتم پیشنهادی علاوه بر الگوریتم‌های پایه از دو الگوریتم بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها نیز در آزمایش‌های عددی استفاده شده است. آزمایشات براساس دیتاست‌های استاندارد اجرا شده‌اند که اطلاعات بیشتر را می‌توان در آدرس (http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html) مطالعه کرد.

جدول 3: نمونه مسائل زمان‌بندی کار کارگاهی انعطاف‌پذیر استفاده‌شده

 (مقیاس کوچک و متوسط)

جدول 4: نمونه مسائل زمان‌بندی کار کارگاهی انعطاف‌پذیر استفاده‌شده (مقیاس بزرگ)

6-3. تنظیم پارامترهای الگوریتم

هر سه الگوریتم با استفاده از نرم‌افزار Matlab کدنویسی شده‌اند. همچنین تمام آزمایشات در سیستم با مشخصات Intel core i7 1.80GH و 8GB RAM  و ویندوز 10 اجرا شده است. هر الگوریتم به‌صورت مجزا 30 بار برای هر مسئله اجرا شده است و نتایج در جداول (6) و (7)، گزارش شده است. شرط توقف Iteration=200 در نظر گرفته شده و طراحی پارامترها برای این تحقیق در جدول (5)، دیده می‌شود.

جدول 5: تنظیم پارامترهای تمام الگوریتم‌ها

7. تجزیه‌وتحلیل یافته‌ها

جدول (6)، شامل بهترین جواب ممکن و مقدار میانگین جواب‌ها برای مسائل کوچک و متوسط و جدول (7)، شامل بهترین جواب ممکن و مقدار میانگین جواب‌ها برای مسائل بزرگ بوده و نتایج مشخص می‌کند الگوریتم ترکیبی پیشنهادی جواب بهتری ارائه داده و رتبه اول را کسب نموده است. از بررسی جدول (6)، مربوط به مسائل کوچک و متوسط در یک مورد مربوط به مسئله 67 کار و 17 ماشین مشاهده می‌شود. الگوریتم بهینه‌سازی ذرات نتیجه بهتری داشته و الگوریتم پیشنهادی رتبه دوم را کسب کرده است. همچنین از بررسی جدول (7)، مربوط به مسائل بزرگ در یک مورد مربوط به مسئله 543 کار و 230 ماشین الگوریتم بهینه‌سازی ذرات نتیجه بهتری داشته و الگوریتم پیشنهادی در مکان دوم ایستاده است. اشکال (2) و (3)، نشان‌دهنده نمودار مربوط به بهترین جواب به‌دست‌آمده از میان 30 بار حل برای مسئله 14 کار و 5 ماشین و مسئله 24 کار و 8 ماشین توسط هر یک از الگوریتم‌ها هستند. از روی این اشکال به‌خوبی می‌توان دریافت که الگوریتم پیشنهادی در تمام مراحل تست نسبت به سایر الگوریتم‌های مقایسه شده برتری داشته است.

شکل (4)، نشان‌دهنده نمودار مربوط به بهترین جواب به‌دست‌آمده برای مسئله 67 کار و 17 ماشین است. از روی این شکل به‌خوبی می‌توان دریافت که الگوریتم پیشنهادی در رتبه دوم و الگوریتم بهینه‌سازی ازدحام ذرات در مکان اول قرار گرفته است. اشکال (5) و (6) نشان‌دهنده نمودار مربوط به بهترین جواب به‌دست‌آمده برای مسئله 97 کار و 34 ماشین و مسئله 127 کار و 50 ماشین هستند. از روی این اشکال به خوبی می‌توان دریافت که الگوریتم پیشنهادی در تمام مراحل تست نسبت به سایر الگوریتم‌های مقایسه شده برتری خیلی خوبی داشته است. اشکال (7) و (8)، برای مسئله 326 کار و 120 ماشین و مسئله 462 کار و 165 ماشین از مسائل بزرگ هستند. این اشکال به‌خوبی نشان می‌دهند الگوریتم پیشنهادی در مکان اول ایستاده است. شکل (9)، مربوط به مسئله 543 کار و 230 ماشین بوده و نشان می‌دهد در این مورد الگوریتم بهینه‌سازی ذرات رتبه اول و الگوریتم پیشنهادی رتبه دوم را کسب نموده است.

شکل (10)، مربوط به مسئله 584 کار و 250 ماشین بوده که در این مسئله الگوریتم پیشنهادی برتری کامل نسبت به سایر الگوریتم‌ها داشته است. در کلیه اشکال به‌خوبی می‌توان دریافت که ترکیب ارائه شده در الگوریتم پیشنهادی که منجر به اصلاح جمعیت اولیه در الگوریتم ژنتیک می‌گردد به‌صورت مشهودی نتایج بهتری نسبت به الگوریتم‌های پایه ترکیب ارائه می‌نماید و در مقایسه با الگوریتم بهینه‌سازی ذرات و کلونی مورچه‌ها فقط در دو مورد الگوریتم بهینه‌سازی ذرات در مکان اول و الگوریتم پیشنهادی در مکان دوم ایستاده است.

جدول 6: نتایج اجرای الگوریتم‌ها برای دیتاست‌های مختلف در مقیاس کوچک و متوسط

*(عدد داخل پرانتز مقدار میانگین است)

جدول 7: نتایج اجرای الگوریتم‌ها برای دیتاست‌های مختلف در مقیاس بزرگ

*(عدد داخل پرانتز مقدار میانگین است)

شکل (2)، نمودار حاصل از حل مسئله 14 کار در 5 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول را کسب نموده است. الگوریتم بهینه‌سازی ازدحام ذرات رتبه دوم، کلونی مورچه‌ها رتبه سوم، ژنتیک رتبه چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند.

شکل 2: بهترین جواب ممکن برای 14 کار در 5 ماشین توسط الگوریتم‌های مختلف

شکل (3)، نمودار حاصل از حل مسئله 24 کار در 8 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول الگوریتم بهینه‌سازی ازدحام ذرات رتبه دوم، کلونی مورچه‌ها رتبه سوم، ژنتیک رتبه چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند.

شکل 3: بهترین جواب ممکن برای 24 کار در 8 ماشین توسط الگوریتم‌های مختلف

شکل (4)، نمودار حاصل از حل مسئله 67 کار در 17 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم بهینه‌سازی ازدحام ذرات رتبه اول الگوریتم پیشنهادی رتبه دوم، کلونی مورچه‌ها رتبه سوم، ژنتیک رتبه چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند.

شکل 4: بهترین جواب ممکن برای 67 کار در 17 ماشین توسط الگوریتم‌های مختلف

شکل (5)، نمودار حاصل از حل مسئله 97 کار در 34 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول الگوریتم بهینه‌سازی ازدحام ذرات رتبه دوم، کلونی مورچه‌ها رتبه سوم، ژنتیک رتبه چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند. در این نمودار در تمام مراحل تکرار الگوریتم پیشنهادی رتبه اول را کسب نموده است. این نمودار نشان می‌دهد الگوریتم جستجوی ممنوعه در Iteration بالای 140 نسبت به الگوریتم ژنتیک عملکرد بهتری داشته است.

شکل 5: بهترین جواب ممکن برای 97 کار در 34 ماشین توسط الگوریتم‌های مختلف

شکل (6)، نمودار حاصل از حل مسئله 127 کار در 50 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار در تمام مراحل تکرار الگوریتم پیشنهادی رتبه اول را کسب نموده است. کلونی مورچه‌ها رتبه دوم، بهینه‌سازی ازدحام ذرات رتبه سوم، ژنتیک رتبه چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند.

شکل 6: بهترین جواب ممکن برای 127 کار در 50 ماشین توسط الگوریتم‌های مختلف

شکل (7)، نمودار حاصل از حل مسئله 326 کار در 120 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول را کسب نموده است. بهینه‌سازی ازدحام ذرات رتبه دوم، کلونی مورچه‌ها رتبه سوم، جستجوی ممنوعه چهارم و ژنتیک رتبه پنجم را کسب نموده‌اند. این نمودار نشان می‌دهد الگوریتم بهینه‌سازی ازدحام ذرات در Iteration بالای 120 عملکرد نزدیک الگوریتم پیشنهادی داشته است.

شکل 7: بهترین جواب ممکن برای 326 کار در 120 ماشین توسط الگوریتم‌های مختلف

شکل (8)، نمودار حاصل از حل مسئله 462 کار در 165 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول را کسب نموده است. کلونی مورچه‌ها رتبه دوم، بهینه‌سازی ازدحام ذرات رتبه سوم، ژنتیک چهارم و جستجوی ممنوعه رتبه پنجم را کسب نموده‌اند. این نمودار نشان می‌دهد الگوریتم کلونی مورچه‌ها در Iteration بالای 160 عملکرد نزدیک الگوریتم پیشنهادی داشته است و همچنین در Iteration بالای 60 الگوریتم‌های ژنتیک و جستجوی ممنوعه عملکرد مشابهی داشته‌اند.

شکل 8: بهترین جواب ممکن برای 462 کار در 165 ماشین توسط الگوریتم‌های مختلف

شکل (9)، نمودار حاصل از حل مسئله 543 کار در 230 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی و بهینه‌سازی ازدحام ذرات عملکرد مشابهی داشته‌اند. همچنین عملکرد کلونی مورچه‌ها و ژنتیک نیز مشابه بوده است و جستجوی ممنوعه رتبه آخر را کسب نموده است.

شکل 9: بهترین جواب ممکن برای 543 کار در 230 ماشین توسط الگوریتم‌های مختلف

شکل (10)، نمودار حاصل از حل مسئله 584 کار در 250 ماشین را نشان می‌دهد که در 30 بار تکرار این مسئله بهترین جواب توسط الگوریتم‌های پیشنهادی، جستجوی ممنوعه، ژنتیک، بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها در این شکل نمایش داده شده است. در این نمودار الگوریتم پیشنهادی رتبه اول و بهینه‌سازی ازدحام ذرات رتبه دوم را کسب نموده است. الگوریتم کلونی مورچه‌ها و ژنتیک عملکرد مشابهی داشته و به ترتیب مکان‌های سوم و چهارم را کسب نموده و جستجوی ممنوعه در مکان آخر است. با توجه به نتایج مربوط به بهترین جواب‌ها که در اشکال 2 تا 10 نشان داده شده و همچنین مقادیر میانگین جواب‌ها در جدول (6) و (7) که حاصل از 30 بار حل برای هر مسئله است، می‌توان دریافت که مدل ارائه‌شده از پایایی خوبی برخوردار است.

شکل 10:بهترین جواب ممکن برای 584 کار در 250 ماشین توسط الگوریتم‌های مختلف

7-1. پیچیدگی زمانی

پیچیدگی زمانی الگوریتم‌ها برای 5 مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر در مقیاس کوچک و متوسط و 4 مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر در مقیاس بزرگ در جداول (8) و (9) آمده است. به‌طور طبیعی الگوریتم پیشنهادی از نوع ترکیبی است و طراحی این الگوریتم بدین‌صورت است که ابتدا الگوریتم جستجوی ممنوعه باید کامل اجرا شده تا لیست ممنوعه این الگوریتم تشکیل گردیده و به‌عنوان ورودی جمعیت اولیه الگوریتم ژنتیک قرارگرفته و سپس الگوریتم ژنتیک اجرا شده و به پایان برسد. بنابراین طولانی‌شدن زمان حل یک امر طبیعی بوده و بنابراین باید زمان حل الگوریتم پیشنهادی بیشترین مقدار را داشته باشد. ولی همان‌گونه که در جداول مشاهده می‌گردد؛ این اتفاق در خیلی از موارد آزمایش عملی نشده و الگوریتم پیشنهادی نسبت به چهار الگوریتمی که با آن‌ها مقایسه شده زمان حل بهتری داشته است و این نشان می‌دهد جمعیت اولیه خالص و اصلاح شده در کوتاه کردن زمان حل نیز مؤثر است.

جدول 8: نتایج پیچیدگی زمانی حاصل از اجرای الگوریتم‌ها برای دیتاست‌های مختلف مقیاس کوچک و متوسط بر حسب ثانیه

*(عدد داخل پرانتز مقدار میانگین است)

جدول 9: نتایج پیچیدگی زمانی حاصل از اجرای الگوریتم‌ها برای دیتاست‌های مختلف مقیاس بزرگ بر حسب ثانیه

*(عدد داخل پرانتز مقدار میانگین است)

7-2. تحلیل آماری فریدمن

با توجه به مقادیر اعداد حاصله و ثبت‌شده در جداول شماره (6) و (7) رتبه‌بندی الگوریتم‌ها برای اعتبارسنجی برتری GA-TS پیشنهادی از نظر آماری، تحلیل آمار فریدمن انجام شد. همان‌گونه که جدول (10)، نشان می‌دهد الگوریتم پیشنهادی بر اساس تحلیل آماری فریدمن، رتبه اول را کسب نموده و سایر الگوریتم‌ها رتبه‌های دوم تا پنجم را به شرح جدول کسب نموده‌اند.

جدول 10: رتبه‌بندی الگوریتم‌های تحقیق بر اساس تحلیل آماری فریدمن

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

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

«ماتی و ژی»^[28] (2005) ثابت کرده‌اند که مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر در گروه مسائل N.P-hard قرار دارد. پیچیدگی این مسئله به‌مراتب از پیچیدگی مسئله زمان‌بندی کار کارگاهی بیشتر است. مدل به کار رفته در این تحقیق را می‌توان در تمامی سیستم‌های برنامه‌ریزی تولید به کار برد، چون این مدل به‌صورت عمومی نوشته شده است و با هر صنعتی که بتوان فرایند آن را به صورت کار، ماشین و عملیات تعریف کرد سازگار است. همچنین این مدل می‌تواند جواب‌های بهینه مناسبی برای سیستم تولید با توجه به تابع هدف مورد نظر به دست آورد. به‌طور خلاصه، الگوریتم‌های فراابتکاری به‌عنوان یک ساختار الگوریتمی در نظر گرفته می‌شود که در انواع مسائل بهینه‌سازی فقط با چند تغییر برای سازگاری با مسئله داده شده اعمال می‌شوند. الگوریتم‌های فراابتکاری دارای یک ویژگی‌های اساسی هستند و آن این است که برای مسئله خاصی طراحی نشده‌اند و در کلیه مسائل کاربرد دارند.

الگوریتم بهبودیافته پیشنهادی برای تولید جمعیت اولیه پالایش‌شده و بهبودیافته گروهی ابتدا مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر را با استفاده از الگوریتم جستجوی ممنوعه حل و لیست ممنوعه تشکیل‌شده را به‌عنوان جمعیت اولیه برای الگوریتم ژنتیک استفاده می‌کند. لیست ممنوعه تشکیل‌شده که شامل جواب‌های بهینه است به‌عنوان یک جمعیت اولیه گروهی مناسب و اصلاح‌شده که به‌صورت یکجا تولیدشده وارد الگوریتم ژنتیک می‌گردد. ترکیب الگوریتم‌ها به این شکل برای اولین بار انجام شده است. الگوریتم‌های فراابتکاری شامل الگوریتم‌های ژنتیک، جستجوی ممنوعه، بهینه‌سازی ازدحام ذرات، کلونی مورچه‌ها و الگوریتم پیشنهادی برای حل مسئله زمان‌بندی کار کارگاهی انعطاف‌پذیر در اندازه‌های مختلف شامل 5 مسئله کوچک و متوسط و 4 مسئله بزرگ به‌کار گرفته شده و در این مقایسه هر مسئله 30 بار حل شده است. در نهایت پس از مقایسه نتایج حاصل‌شده به‌خوبی مشخص شده با استفاده از روش ترکیبی معرفی شده، الگوریتم ترکیبی پیشنهادی با تمرکز بر بهبود و اصلاح جمعیت اولیه گروهی در الگوریتم ژنتیک نسبت به سایر الگوریتم‌ها برتری مناسبی داشته است. به‌طوری‌که در تمام مراحل حل مسئله بهترین جواب را نسبت به الگوریتم‌های پایه (یعنی جستجوی ممنوعه و ژنتیک) ارائه نموده و همچنین در مقایسه با دو الگوریتم بهینه‌سازی ازدحام ذرات و کلونی مورچه‌ها همیشه نسبت به کلونی مورچه‌ها برتری داشته و به ‌غیر از دو مورد به الگوریتم بهینه‌سازی ذرات نیز برتری داشته است. به‌عبارت‌دیگر اصلاح جمعیت اولیه در الگوریتم ژنتیک (که یک جمعیت اولیه گروهی است) توسط ترکیب ارائه‌شده تأثیر بسزایی در حل مسئله و ارائه جواب بهتر داشته است.

با توجه به نتایج حاصل از 30 بار حل برای هر 9 مسئله که در این نتایج، الگوریتم پیشنهادی در رتبه اول قرار گرفته است می‌توان دریافت که مدل ارائه شده از پایایی خوبی برخوردار است. نمودارهای نشان داده شده در شکل‌های (2) الی (10) دو مورد دیگر از دستاوردهای تحقیق را به شرح ذیل نشان می‌دهد:

انتخاب و تنظیم پارامترهای یک الگوریتم در به دست آوردن نتایج حاصل از اجرای آن بر روی مسائل مختلف بهینه‌سازی از اهمیت بالای برخوردار است. زیرا مجموعه پارامترهای مشخص شده برای یک الگوریتم بهینه‌سازی بر روی یک مسئله خاص می‌تواند منجر به نتایج بهتری نسبت به مقادیر دیگر پارامترها باشد. این به این دلیل است که اکثر الگوریتم‌ها هنگام آزمایش روی مسائل عمومی تقریباً یکسان عمل می‌کنند، که از آن به‌عنوان نظریه The No Free Lunch Theory یاد می‌شود. از روی نمودارها می‌توان دید جواب‌های الگوریتم‌ها در iteration های بالای 160 همگرا شده‌اند و جواب‌های مشابه تولید نموده‌اند که نشان از تنظیم مناسب پارامترها است؛ با تنظیم مناسب پارامترها هم جواب بهینه‌ای می‌توان ایجاد نمود و هم‌زمان حل را کوتاه‌تر کرد. به‌عبارت‌دیگر، iteration های بالای 200 نه‌تنها جواب بالایی تولید نخواهد کرد بلکه زمان حل الگوریتم‌ها را نیز افزایش خواهد داد.

همچنین این نمودارها نشان می‌دهند که از iteration یک الی 200 در تمام نقاط، الگوریتم پیشنهادی نسبت به الگوریتم‌های پایه (جستجوی ممنوعه و ژنتیک) جواب بهینه‌ای تولید نموده است و این بدین معنا است که استفاده از جمعیت اولیه مناسب بجای جمعیت اولیه تصادفی در الگوریتم ژنتیک باعث بهینه شدن جواب‌ها از ابتدای حل (iteration=1) تا پایان الگوریتم می‌شود و مختص یک نقطه خاص نیست.

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

پیشنهادهای پژوهش

برخی از کاربردهای بهینه‌سازی برای مدیران از طریق الگوریتم پیشنهادی ارائه شده به شرح ذیل قابل انجام است:

• طراحی بهینه تجهیزات و کارخانه‌های فراوری شیمیایی؛
• تخصیص منابع یا خدمات در میان چندین فعالیت برای به حداکثر رساندن سود؛
• کنترل زمان انتظار و بیکاری و صف‌بندی در خطوط تولید برای کاهش هزینه‌ها؛
• افزایش کارایی و اثربخشی فعالیت‌های زنجیره تأمین؛
• یافتن مسیرهای بهینه وسایل نقلیه فضایی؛
• ایجاد بهینگی در مسائل جنگی و دفاعی؛

پیشنهادهایی برای تحقیقات آتی

در این بخش پیشنهادهای قابل ذکر برای انجام تحقیقات آتی در زمینه ساختار مدل پیشنهادی و همچنین الگوریتم حل، ارائه شده است که در ادامه تشریح می‌گردند.

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

• بررسی مسئله به‌صورت چندهدفه با اهداف متضاد مانند منظور نمودن تغییر در سرعت ماشین که باعث کاهش زمان تکمیل گردیده ولی در مقابل مصرف انرژی را افزایش می‌دهد؛
• استفاده از سایر الگوریتم‌های فراابتکاری در ترکیب به‌منظور ارائه ترکیبات جدید با هدف رسیدن به جواب‌های بهتر؛
• ارائه راهکار جدید جهت اصلاح جمعیت اولیه الگوریتم‌های فراابتکاری با هدف رسیدن به جواب‌های بهتر؛
• بررسی درصد ترکیب را در میزان اثربخشی الگوریتم بهبودیافته به‌طوری‌که بخشی از جمعیت اولیه تصادفی و بخشی از طریق مدل ارائه‌شده ایجاد گردد و بهترین درصد میزان ترکیب بررسی گردد؛
• تغییر در ساختار الگوریتم‌های فراابتکاری با هدف رسیدن به جواب‌های بهتر.

[1]. An

[2]. Banharnsakun

[3]. Kundakcı & Kulak

[4]. Ding & Gu

[5]. Denkena

[6]. Baker

[7]. Singh & Mahapatra

[8]. Liu

[9]. Marichelvam & Geetha

[10]. Fan

[11]. Bissoli

[12]. Serna

[13]. Yuan

[14]. Li

[15]. Fathi

[16]. Konovalenko & Ludwig

[17]. Rolf

[18]. França

[19]. Cáceres-Gelvez

[20]. Abreu

[21]. Xie

[22]. Pezzella

[23]. Brucker & Schlie

[24]. Kumari

[25]. Defersha & Movahed

[26]. Tang

[27]. Kaya

[28]. Mati & Xie