حل یک مسأله زمانبندی چند هدفه جدید در سیستم تولید سلولی با استفاده از یک الگوریتم تلفیقی

1. مقدمه

در جهان رقابتی حاضر، تعیین توالی و زمانبندی مؤثر محصولات تولیدی ضرورتی برای بقا در فضای بازار است. زمانبندی ابزاری برای استفاده بهینه از منابع در دسترس است. منابع و کارها در زمانبندی ممکن است انواع گوناگونی داشته باشد و با توسعه جهان صنعتی، منابع مربوطه بحرانی‌تر می‌شود (آدامز و همکاران، 1988). زمانبندی این منابع به افزایش کارایی و بهره‌برداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتاٌ افزایش سوددهی یک سازمان منجر می­شود. زمانبندی مؤثر منابع مانند ماشین‌ها و نیروی انسانی در محیط رقابتی امروز یک باید است (توکلی مقدم و همکاران، 2010).

اهمیت توالی کارها بر روی گروهی از ماشین‌ها، با هدف تمرکز بر هزینه‌ها از آن جهت مورد توجه است که در محیط کسب و کار امروز، رقابت شرکت‌های تولیدی از طریق قابلیت آن‌ها برای پاسخگویی سریع به تغییرات سریع در زمینه تجاری و تولید محصولات با کیفیت بالاتر و هزینه‌های کمتر تعیین می‌شود. شرکت‌های تولیدی در تلاش هستند تا این قابلیت‌ها را از طریق اتوماسیون و مفاهیم جدید مدیریت تولید، مانند تولید به موقع^[1] (JIT) به دست آورند. این مفاهیم به بسیاری از شرکت‌ها در به‌دست آوردن سود اقتصادی کمک کرده است. در سیستم‌های تولید بموقع کارها نباید زودتر و نه دیرتر تکمیل شوند که به مسایل با هزینه‌های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می‌شود. در یک بازار بسیار رقابتی دیرکرد تحویل محصول با توجه به موعد تحویل آن‌ها یک مقیاس عملکرد بسیار مهم برای واحدهای تولیدی در بازار رقابت است، همچنین، زودکرد کارها موجب افزایش هزینه نگهداری می‌شود.

این مقاله، به حل مسأله تولید سلولی چند هدفه با اهداف کمینه کردن حداکثر زمان تکمیل کارها، کمینه کردن هزینه دیرکرد و کمینه کردن هزینه زودکرد با استفاده از الگوریتم تلفیقی بر پایه بهینه­سازی ذرات انبوه^[2] (PSO) و الگوریتم ژنتیک^[3] (GA) می‌پردازد. مسأله زمانبندی تولید سلولی عبارت است از یافتن توالی بهینه انجام عملیات کارهای مختلف و مرتبط با هر ماشین بر روی آن ماشین در سلول‌ها و تعیین توالی سلول‌ها. مسأله زمانبندی تولید سلولی یک مسأله چندجمله­ای نامعین سخت (NP-hard) است و جزو سخت‌ترین و مطرح‌ترین مسایل بهینه‌سازی ترکیبی است (لوگندران و اسریسکاندراجاه، 1993). به سبب پیچیدگی ذاتی مسایل بهینه‌سازی ترکیبی و بخصوص مسأله زمانبندی تولید سلولی، استفاده از روش‌های ابتکاری برای حل چنین مسایلی، بهبودهای موثری در تولید جواب‌های قابل قبول ایجاد کرده است؛ چرا که با افزایش ابعاد مسأله، عملاً روش‌های سنتی تعیین جواب بهینه به دلیل زمان بر بودن کارایی خود را از دست می‌دهند.

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

2. مرور ادبیات موضوع

یوشیدا و هیتومی (1979) الگوریتمی برای حل بهینه مسأله زمانبندی فلوشاب دو ماشینه ارایه داده‌اند که در آن زمان راه‌اندازی در نظر گرفته شده است. یانگ و لیااو (1996) مسأله زمانبندی سلولی را با دو سلول و حرکت بین سلولی در نظر گرفتند و آن را با استفاده از تکنیک شاخه و حد و یک الگوریتم ابتکاری حل نمودند. سلیمانپور و همکاران (2004) مسأله زمانبندی سلولی را با احتساب زمان راه‌اندازی در نظر گرفتند و الگوریتم حلی ارائه نمودند. در این مقاله یک سیاست دو مرحله ای در نظر گرفته شد: در مرحله اول توالی کارها در هر سلول و در مرحله دوم توالی سلول‌ها با توجه به ماشین‌های گلوگاه^[4] و مقایسات جفتی مشخص شد. در نهایت، مدل خود را از طریق الگوریتم دو مرحله ای SVS حل کرده است و نتایج به‌دست آمده را با الگوریتم LN-PT مقایسه کرده و به این نتیجه رسیده است که الگوریتم SVS کاراتر از الگوریتم LN-PT است. لو و یوآن (2007) مسأله دسته بندی تک ماشینه با زمان‌های راه‌اندازی خانواده قطعات مساوی را به منظور کمینه کردن حداکثر دیرکرد را در نظر گرفته و حل کردند.

لین و همکاران، (2009) سه روش فراابتکاری برجسته (یعنی الگوریتم ژنتیک، شبیه­سازی تبرید^[5] (SA) و جستجوی ممنوع^[6] (TS)) برای مسأله زمانبندی تولید سلولی با زمان راه‌اندازی خانواده قطعات وابسته به توالی بکار برد. ایشان در این مقاله نشان می‌دهد عموماً بهبود ایجاد شده توسط زمانبندی غیر ترتیبی در برابر زمانبندی ترتیبی برای معیار کارایی مبتنی بر زمان تحویل بهتر است. هندی‌زاده و همکاران (2008) یک روش فراابتکاری مبتنی بر الگوریتم جستجوی ممنوع برای زمانبندی قطعات و کارها در جهت کمینه کردن زمان کل ساخت در سیستم  تولید سلولی با توجه به زمان‌های آماده‌سازی خانواده قطعات وابسته به توالی ارایه کرده‌اند. در این مقاله، کارایی و اثربخشی روش فراابتکاری جستجوی ممنوع پیشنهاد شده در برابر سایر الگوریتم‌های ابتکاری و فراابتکاری معرفی شده برای حل این مسأله مقایسه شد و نتایج محاسباتی نشان داد که الگوریتم جستجوی پراکنده پیشنهادی در کمینه­سازی زمان کل ساخت در یک زمان پردازش معقول، کاملاً اثربخش است.

مانکمن و همکاران (2008) در یک کارخانه مونتاژ قطعات الکترونیکی یک روش ابتکاری سه مرحله ای برای زمانبندی مونتاژ گروهی با خطوط مونتاژ موازی و مجزا با معیار کمینه سازی هزینه راه‌اندازی ارایه کرده اند. فرآیند الگوریتم ابتکاری، شامل قدم‌های تخصیص، توالی و زمانبندی با یک رویکرد بهینه‌سازی برای هر قدم است. برای پیچیده‌ترین مرحله، یعنی مرحله‌ توالی رویه‌ای با نام رویه جستجوی تطابقی تصادفی توانمند^[7] (GRASP) ارایه شده است. با توجه به هزینه‌های راه‌اندازی وابسته به توالی و کاربرد رویه جستجوی تطابقی تصادفی توانمند نتایج تجربی یک کاهش 49 درصدی در هزینه‌های راه‌اندازی را نشان می‌دهد. توکلی­مقدم و همکاران، (2010) روش فراابتکاری جستجوی پراکنده را برای مسأله زمانبندی سیستم تولید سلولی چند معیاره با معیارهای هزینه­های راه­اندازی، ساخت، جابجایی بین سلولی بررسی کردند و نشان دادند که روش جستجوی پراکنده در کمینه سازی معیارهای فوق در یک زمان پردازش معقول، کاملاً اثربخش است.

جرالد و همکاران (2005) به زمانبندی در سیستم تولیدی انعطاف­پذیر^[8] (FMS) با به کارگیری الگوریتم بهینه سازی ذرات انبوه پرداختند. همچنین، برای مقایسه کارایی این الگوریتم از سایر تکنیک­های فرا­ابتکاری از قبیل الگوریتم ژنتیک، شبیه­سازی تبرید و الگوریتم ممتیک^[9] استفاده نمودند. توابع هدف در نظر گرفته شده شامل کمینه ساختن زمان بیکاری ماشین و کمینه ساختن هزینه جریمه کل است که برای برآورده نمودن موعد تحویل محصول در نظر گرفته شده است. نتایج حاصل از اعمال و پیاده سازی الگوریتم بهینه­سازی ذکر شده، حاکی از این است که الگوریتم بهینه سازی ذرات انبوه نسبت به سایر الگوریتم­ها جواب بهتر و در زمانی مناسبتر ارائه داده است. تاسگترین و همکاران (2007) از الگوریتم بهینه سازی ذرات انبوه برای مدل تولید خطی استفاده نمودند. آنها با فرموله کردن مسأله به صورت یک مدل دودویی، ابتدا مدل پیشنهادی را توسط الگوریتم بهینه­سازی ذرات انبوه دودویی حل کرده و سپس نتایج حاصل را با جواب‌های الگوریتم ژنتیک مقایسه نمودند. در 20 مورد مسأله حل شده، الگوریتم بهینه­سازی ذرات انبوه موفق به یافتن 19 مورد از جواب‌های بهینه گردید در حالیکه الگوریتم ژنتیک تنها توانست 14 مورد از جواب‌های بهینه را به‌دست آورد. ونگ و لیو (2008) به ارایه روشی برای زمانبندی در سیستم تولید انعطاف پذیر با وجود محدودیت منابع بر مبنای الگوریتم بهینه­سازی ذرات انبوه و الگوریتم شبیه سازی تبرید پرداختند. در مقاله مذکور ابتدا یک مسأله زمانبندی در سیستم تولید انعطاف پذیر با وجود محدودیت منابع در نظر گرفته شد و از آن یک تابع هزینه ایجاد گردید. سپس یک الگوریتم تلفیقی از الگوریتم بهینه­سازی ذرات انبوه و الگوریتم شبیه سازی تبرید برای دستیابی به جواب بهینه پیاده شد. نتایج الگوریتم شبیه سازی تبرید نشان می­دهد که الگوریتم پیشنهادی توانایی گریز از بهینگی نسبی و جهت گیری به سوی بهینه کلی را دارد و در مقایسه با سایر روش­ها کاراست. لطفی و همکاران (2008) به زمانبندی سیستم تولیدی توسط یک الگوریتم ژنتیک جدید که از الگوریتم بهینه­سازی ذرات انبوه و همچنین از یک الگوریتم ژنتیک معمولی الهام گرفته شده، برای شناسایی پتانسیل مفاهیم الگوریتم بهینه­سازی ذرات انبوه در بهبود عملکرد الگوریتم ژنتیک، پرداختند. در الگوریتم ژنتیک تغییر یافته، کروموزوم­های اولیه، مانند ذرات در الگوریتم بهینه­سازی ذرات انبوه ایجاد می­شوند و برای نسل­های بعدی از عملگر­های الگوریتم ژنتیک معمولی استفاده می­شود. همچنین، همانند الگوریتم بهینه­سازی ذرات انبوه، هریک از کروموزوم­ها بهترین تجربه شخصی خود و بهترین تجربه کلیه کروموزوم­ها را حفظ می­نمایند. نتایج به‌دست آمده نشان می­دهد که الگوریتم ارایه شده از عملکرد بهتری برخوردار است.

3. مسأله زمانبندی سیستم تولید سلولی چند هدفه

1-3. تشریح مسأله

در یک مسأله زمانبندی سیستم تولید سلولی، m ماشین و n قطعه موجود است. باید توجه داشت که این m ماشین در c سلول مستقر بوده؛ از هر کدام یک عدد موجود است. هر کار یا قطعه دارای یک فرآیند خاص است و توالی انجام عملیات مختلف به منظور تکمیل آن کار مشخص است. هر عملیات یک قطعه بر روی هر ماشین، دارای زمان خاص خود است. در این مسأله، عملیات مربوط به پردازش هر قطعه بر روی ماشین‌های مورد نیاز برای پردازش در سلولی که ماشین مستقر است، زمانبندی می‌گردد. هدف از حل این مسأله مشخص کردن توالی انجام کارها در هر سلول و همچنین تعیین توالی سلول‌هاست. به طوریکه: 1) کاهش حرکت بین سلولی و 2) کاهش هزینه زودکرد قطعات و 3) کاهش هزینه دیرکرد قطعات، بهینه شود. در این مسأله n قطعه وجود دارد که هر یک از آن‌ها در یک زمان واحد باید روی m ماشین یا کمتر پردازش شوند. هر کار از یک توالی از پیش تعیین شده‌ای پیروی کرده و زمان پردازش مشخصی دارد. ترتیب ماشین‌ها برای کارهای مختلف متفاوت است. برای درک بیشتر مفهوم توالی بین سلول­ها مفروضات در نظر گرفته شده برای این مدل عبارتند از:

• زمان عملیات تمامی ‌قطعات روی هر نوع ماشین قطعی است.
• تعداد قطعات مشخص و ثابت است.
• تعداد ماشین‌های موجود در سیستم مشخص و ثابت است.
• تعداد سلول‌های موجود در سیستم مشخص و ثابت است.
• ماشین‌های موجود در هر سلول مشخص است.
• هر نوع ماشین می‌تواند تنها یک نوع عملیات را انجام دهد و هر عملیات نیز تنها می‌تواند توسط یک ماشین انجام شود.
• مسافت بین سلول‌ها ثابت نیست.
• زمان شکست برای ماشین‌ها نخواهیم داشت.
• راندمان ماشین‌ها 100% است.
• تمامی ‌ماشین‌ها در ابتدای دوره‌ها برای استفاده در دسترس هستند.
• زمان‌های راه‌اندازی برای هر یک از ماشین‌ها صفر است.

2-3. اندیس‌ها

j: اندیس ماشین، j={1,…,M}

i: اندیس قطعات، i={1,…,P}

c: اندیس سلول، c={1,…,C}

k: اندیس توالی قطعات، k={1,…,K}

b:اندیس توالی سلول، b={1,…,KC}

3-3. پارامترها

t_ij: زمان لازم برای پردازش قطعه i بر روی ماشین j

       1 اگر قطعه i به ماشین j جهت پردازش نیاز داشته باشد،

a_ij:

       0  در غیر اینصورت.

           1 اگر ماشین j به سلول c تعلق داشته باشد،

m_jc:

            0  در غیر این صورت.

T_ic: زمان حرکت بین سلولی برای قطعه i در سلول c

L_i: هزینه دیرکرد قطعه i

E_i: هزینه زودکرد قطعه i

d_i: زمان تحویل قطعه i

4-3. متغیرهای تصمیم‌گیری

        1   اگر قطعه i به سلول c اختصاص یابد،

X_ic:

       0  در غیر این صورت.

        1   اگر سلول c به توالی b اختصاص یابد،

Y_cb:

        0  در غیر این صورت.

         1 اگر قطعه i در توالی kام سلول c واقع شده باشد،

Z_ikc:

        0  در غیر اینصورت.

C_kjcb: زمان تکمیل قطعه واقع در توالی kام روی ماشین j در سلول c که سلول c در توالی b واقع است.

C_i: زمان تکمیل قطعه i

C_max: حداکثر زمان تکمیل کارها

5-3.  مدل ریاضی

مدل ریاضی سه هدفه پیشنهادی به ‌صورت زیر ارایه می‌شود:

تابع هدف اول (1)، حداکثر زمان تکمیل کارها را کمینه می­کند. تابع هدف دوم (2)، هزینه زودکرد تولید قطعات و تابع هدف سوم (3)، هزینه دیرکرد تولید قطعات را کمینه می­کند.

معادله (4) هریک از قطعات را به یک سلول تخصیص می‌دهد. رابطه (5) تضمین می‌کند که به هر توالی فقط یک سلول اختصاص یابد. معادله (6) تضمین می‌کند که هر سلول تنها به یک توالی اختصاص یابد. رابطه (7) هر یک از قطعات تخصیص داده شده به هر سلول را به یک توالی در آن سلول اختصاص می‌دهد. معادله (8) تضمین می‌کند که هر توالی در یک سلول حداکثر به یک قطعه اختصاص یابد. رابطه (9) زمان تکمیل قطعه اختصاص داده شده به اولین توالی بر روی اولین ماشین در سلولی که در توالی اول قرار گرفته را برابر با مجموع زمان پردازش قطعه مشخص شده روی ماشین اول در سلول مشخص شده قرار می‌دهد.

معادله (10) زمان تکمیل قطعه اختصاص داده شده به توالی k(k ≥ 2)روی ماشین اول در سلولی که در توالی اول قرار گرفته را برابر با مجموع زمان تکمیل در توالی قبلی و زمان پردازش در توالی فعلی قرار می‌دهد. رابطه (11) زمان تکمیل قطعه اختصاص داده شده به توالی اول روی ماشین اول در سلول‌هایی که در سایر توالی‌ها(b ≥ 2) غیر از توالی اول قرار دارند را برابر با مجوع زمان تکمیل در توالی آخر سلول قبلی و زمان پردازش قطعه در توالی فعلی روی ماشین اول قرار می­دهد. معادله (12) زمان تکمیل اختصاص داده شده به توالیkروی ماشین اول در سلولی که در سایر توالی‌ها غیر از توالی اول قرار دارند را برابر با مجموع زمان تکمیل توالی قبلی و زمان پردازش قطعه مشخص شده در توالی فعلی روی ماشین اول قرار می‌دهد. رابطه (13) زمان تکمیل قطعه اختصاص داده شده به توالی اول روی ماشین j(غیر از ماشین اول) در سلولی که به توالی اول اختصاص دارد را برابر با مجموع زمان تکمیل این قطعه روی ماشینj-1در همان توالی و زمان پردازش قطعه در همان توالی روی ماشینjقرار می‌دهد.

معادله (14) زمان تکمیل قطعه اختصاص داده شده به توالی اول روی ماشین j(غیر از ماشین اول) در سلولی که به توالی غیر از توالی اول اختصاص داده شده است را برابر مجموع بیشترین زمان تکمیل این قطعه روی ماشین قبلی (j-1) در سلول فعلی و زمان تکمیل توالی آخر سلول قبلی (b-1)روی ماشینj  با زمان پرازش قطعه توالی اول در سلول فعلی(b)روی ماشینjقرار می‌دهد. رابطه (15) زمان تکمیل قطعه اختصاص داده شده به توالیk(غیر از توالی اول) روی ماشینj(غیر از ماشین اول) در سلولcکه به توالی bاختصاص دارد را برابر با مجموع بیشترین زمان تکمیل توالی قبلی (k-1) روی ماشینj و زمان تکمیل توالی فعلی (k)روی ماشین قبلی (j-1) با زمان پردازش قطعه مشخص شده در توالی فعلی روی ماشینj  قرار می‌دهد.

معادله (16) زمان تکمیل هر قطعه را محاسبه می‌کند. رابطه (17)C_maxرا برابر باحداکثر زمان تکمیل قرار می‌دهد. رابطه (18) متغیرهای 0 و 1 را معرفی می‌کند و در نهایت، رابطه (19) متغیر‌های غیر منفی را معرفی می‌کند.

همانطور که اشاره شد، تابع هدف اول مدل کمینه­سازی حداکثر زمان تکمیل کارهاست و هدف در مسأله زمانبندی سلولی تعیین توالی قطعات در سلول­ها و تعیین توالی سلول­هاست. بدین معنی که در شرایطی که چند قطعه به یک ماشین اختصاص می‌یابند، ابتدا قطعه­ای روی آن ماشین پردازش می شود که سلول آن دارای شماره توالی کمتری بوده و توالی آن قطعه در سلول خود نیز دارای کمترین شماره توالی باشد و متناسب با این رویکرد سایر قطعات بر روی ماشین پردازش می­شوند. برای درک بیشتر از مفهوم توالی بین سلول­ها در این قسمت از مقاله، مثالی ارایه می­شود. یک شرکت تولیدی که شامل واحدهای مختلفی است، در واحد رنگ آن شرکت، چهار نوع قطعه تولیدی رنگ می­شود. این واحد دارای دو سلول تولیدی بوده که پنج ماشین آن در این دو سلول مستقر شده­اند. جدول شماره 1 ماتریس مسیر ساخت قطعات بوده که نشان دهنده ماشین­های مورد نیاز برای پردازش بر روی قطعات است. همان‌طور که مشخص است، قطعه 1 به ماشین­های 1، 2 و 3 نیاز دارد. جدول شماره 2 زمان پردازش هر یک از قطعات را نشان می­دهد. همان‌طور که مشخص است، زمان پردازش قطعه 1 روی ماشین 1، 2 و 3 به ترتیب 4، 5 و 12 است. و در نهایت، تعلق ماشین­های واحد رنگ شرکت به هر یک از دو سلول در جدول شماره 3 امده است.

جدول 1. ماتریس مسیر ساخت قطعات (a_ij)

جدول 2. زمان پردازش قطعات بر روی ماشین­ها (t_ij)

جدول 3. ماتریس تخصیص ماشین­ها به سلول­ها (m_jc)

با توجه به مسأله مطرح شده و حل مدل با در نظر گرفتن تابع هدف اول که حداقل­سازی حداکثر زمان تکمیل کارها است، بهترین توالی به‌دست آمده با استفاده از نرم افزار Lingo 11 در شکل 1 نشان داده شده است.

 مدت زمان کل ساخت برای این مسأله‏ 27 بوده (27C_max =) و با توجه به تخصیص قطعات، یک حرکت بین سلولی وجود دارد. با توجه به نتایج حل، قطعات 1 و 2 به سلول 1 و قطعات 3 و 4 به سلول 2 اختصاص یافته­اند و نهایت توالی سلول­ها بدین صورت است که سلول 2 در توالی اول بوده و سلول 1 در توالی دوم. حال در صورتی که توالی سلول­ها تغییر یابد؛ یعنی سلول 2 در توالی اول قرار گیرد و سلول 1 در توالی دوم، مدت زمان کل ساخت 48 می­شود. نمایی شماتیک از زمانبندی صورت گرفته برای این توالی در شکل 2 آمده است.

شکل 1. شمایی از توالی قطعات و سلول‌ها در شرایط اول از آزمون ارایه شده

شکل 2. شمایی از توالی قطعات و سلول‌ها در شرایط دوم از آزمون ارایه شده

4. طراحی الگوریتم بهینه سازی ذرات انبوه برای حل مدل پیشنهادی

در این مقاله، یک الگوریتم بهینه­سازی ذرات انبوه چند هدفه مبتنی بر آرشیو پارتو که با عملگرهای ژنتیک و جستجوی همسایگی متغیر ترکیب شده، برای حل مسأله زمانبندی سلولی پیشنهاد شده است. شکل 3 ساختار کلی طراحی شده برای الگوریتم بهینه­سازی ذرات انبوه چند هدفه را نشان می­دهد.

شکل3. ساختار کلی الگوریتم پیشنهادی

1-4. نحوه نمایش جواب‌ها

در تمام الگوریتم­های فراابتکاری، به دلیل نیاز به حل شدنی در شروع کار، لازم است حل شدنی را طبق ساختار مشخصی ذخیره کنیم که به این ساختار، نحوه نمایش جواب می­گویند. در اینجا برای نمایش جواب از ساختار ماتریسی استفاده شده است. نمایش جواب در این مسأله، شامل دو ماتریس است که یکی برای نمایش توالی سلول­ها و دیگری برای نمایش توالی کارها در سلول­ها طراحی شده است. شکل شماره­های 2 و 3 به ترتیب ماتریس سطری(برداری) و ماتریس دو بعدی را نشان می دهد. در شکل 4، C_j نشان دهنده شماره سلولی است که در خانه jام توالی زمانبندی شده است. در شکل شماره 5،  A_ijشماره کاری است که در سلول iام در خانه jام توالی زمانبندی شده است.

شکل4. ماتریس برداری نمایش توالی سلول­ها

شکل5. ماتریس دو بعدی نمایش توالی کارها در سلول‌ها

2-4. نحوه تولید جواب‌های اولیه

در این مقاله، از یک روش جستجوی ممنوع نخبه­گرا^[10] برای تولید جواب‌های آغازین استفاده می‌شود. هدف اصلی به کارگیری این روش، تولید جواب‌های اولیه­ای است که از نظر کیفیت^[11] جواب و پراکندگی^[12]، از سطح مطلوب مناسبی برخوردار باشند. جواب آغازین می­تواند هر یک از جواب‌های حاصل از بهینه­سازی هر یک از توابع هدف در زمان متوقف شدن نرم افزار لینگو  باشد (نقطه آرمانی پویا). روش پیشنهادی در ابتدا، جواب موجود را در یک فهرست مجازی ذخیره کرده، سپس با استفاده از یک رویکرد حرکت مناسب به جستجوی جواب مطلوب دیگری که شرط (شرایط) پذیرش را دارا باشد، در مجاورت جواب می­پردازد. این فرایند تا دستیابی الگوریتم به شرط پایانی ادامه پیدا می­کند. رویکرد حرکت مورد استفاده، عملگر شیفت به راست است، به این صورت که دو اندیس بصورت تصادفی تولید شده و توالی بین این دو اندیس به سمت راست به صورت چرخشی شیفت داده می­شوند. رویکرد حرکت طراحی شده از استراتژی هوشمند روش جستجوی ممنوع، مبتنی بر پرهیز از بازگشت به جواب‌هایی که در تکرارهای قبلی به‌دست آمده­اند، از طریق بکارگیری یک فهرست مجازی حافظه به نام فهرست ممنوع استفاده می‌کند. فهرست ممنوع مورد استفاده در اینجا، به مسیر جستجو وابسته بوده، از تکرار یک حرکت در طول دوره ممنوعیت^[13] جلوگیری می­کند. برای دستیابی به جواب‌های مطلوب از نظر کیفیت و پراکندگی در مسیر جستجو، از رابطه (20) استفاده می­گردد.  

f_i، مقدار iامین تابع هدف توالی تولید، F_i، مقدار iامین مؤلفه نقطه آرمانی پویا وw_i ، وزن تخصیص یافته به iامین تابع هدف است. هدف از به کارگیری تابع فوق بر پایه این حقیقت استوار است که اگر تابع فوق به ازای یک مجموعه از وزن­های w_i برای یک جواب کمینه گردد، آن جواب متعلق به جواب‌های پارتو است.

برای تعیین شرط پذیرش جواب جدید، متغیر  به صورت زیر تعریف می­گردد:

در رابطه (21)، A جواب موجود و B جوابی است که توسط روش جستجوی ممنوع و با به کارگیری رویکرد حرکت به‌دست آمده است. بنابراین شرایط پذیرش بصورت یکی از موارد زیر است:

1) اگر  و حرکت در فهرست ممنوع یافت نشود، جواب B جایگزین جواب A می­گردد.

2) اگر  و حرکت در فهرست ممنوع یافت شود، از استراتژی تنفس استفاده شده و جواب B جایگزین جواب A می­گردد.

3) اگر  و حرکت در فهرست ممنوع یافت نشود، جواب B در صورتی جایگزین جواب A می‌شود که توسط آن مغلوب نشده باشد.

4) اگر  و حرکت در فهرست ممنوع یافت شود، جواب A بدون تغییر باقی خواهد ماند.

استراتژی تنفس^[14] در این مقاله به این صورت پیاده­سازی شده است که اگر جواب به‌دست آمده توسط هیچ یک از جواب‌های پذیرفته شده مغلوب نشود، پذیرفته خواهد شد.

روش جستجوی ممنوع نخبه­گرا پس از ×Nα تکرار متوقف می­گردد. پس از اجرای الگوریتم جستجوی ممنوع نخبه­گرا، ×Nα جواب پراکنده که تا حد امکان به مرز بهینه نزدیک شده­اند، وجود دارد. از طرفی تعداد جواب‌ها در هر تکرار روش الگوریتم بهینه­سازی ذرات انبوه چند هدفه، برابر با N است. بنابراین باید از بین ×Nα جواب موجود، N جواب به عنوان توالی­های تولید اولیه الگوریتم بهینه­سازی ذرات انبوه انتخاب گردند. در این مقاله، انتخاب جمعیت اولیه جواب‌ها، بر اساس یک روش سریع مرتب کردن جواب‌های غیرمغلوب که توسط دب (2002) شرح داده شده است، صورت می­گیرد. این روش به این صورت عمل می­کند که ×Nα جواب موجود با الگوریتمی که توسط دب (2002) طراحی شده است، مرتب و سطح­بندی می­شوند؛ شماره هر سطح، کیفیت جواب‌های موجود در آن را نشان می‌دهد. در نهایت N جواب که دارای بالاترین کیفیت و پراکندگی هستند، مطابق با قانون دب انتخاب می‌شوند.

برای به روز رسانی مقادیر مؤلفه­های نقطه آرمانی پویا، فرآیند زیر در انتهای هر تکرار روش پیشنهادی انجام می­شود: N مقدار به‌دست آمده برای هر یک از سه تابع هدف، جداگانه و به صورت صعودی مرتب می­شوند. اگر کوچکترین مقدار به‌دست آمده برای تابع هدف iام از مؤلفه متناظرش در نقطه آرمانی پویا کوچکتر باشد، این مقدار جایگزین می­گردد و در غیر این صورت مؤلفه مورد نظر تغییر نمی­کند.

3-4. آرشیو جواب‌های پارتو

از آنجا که در حل مسایل چندهدفه به دلیل وجود تناقض بین اهداف، جواب واحدی که همه اهداف درآن بهینه باشند، وجود ندارد، در نهایت مجموعه­ای از جواب‌های غالب به عنوان جواب‌های بهینه (نزدیک بهینه)، ارایه خواهند شد که به آنها آرشیو جواب‌های پارتو گویند. در اینجا که از یک روش مبتنی بر آرشیو پارتو برای حل استفاده شده است، کیفیت جواب‌های موجود در آرشیو، بسیار اهمیت دارد. لذا در این مقاله، این آرشیو در هر تکرار الگوریتم پیشنهادی به روز خواهد شد. روش به روز کردن آن در اینجا به گونه­ای طراحی شده است که در آن جواب‌هایی که دارای کمترین فاصله با مرز بهینه و همچنین بالاترین پراکندگی هستند، در این آرشیو نگهداری می­شوند. برای پیاده سازی این تابع از روش تخصیص برازندگی دانه دانه ریز شده ^[15] همراه با روش تخمین چگالی و یک تابع بهبود یافته برش^[16] آرشیو پارتو استفاده شده است (زیتزلر و همکاران، 2001). در این روش، سایز آرشیو ثابت بوده، به همه جواب‌ها، چه جواب‌های غالب و چه مغلوب، اهمیت داده می­شود.

4-4. تعیین p_i و p_g اولیه

برای هر کدام از جواب‌ها بهترین جوابی را که تا به حال به آن رسیده، به عنوان p_i تعیین می­کنیم و p_g بهترین نقطه یا جوابی است که همه جواب‌ها یا ذرات به آن رسیده اند.

5-4. روش بهبود جواب‌ها به وسیله جستجوی همسایگی متغیر (VNS)

هر کدام از ذرات یا جواب‌ها که در جمعیت جواب‌ها موجود است، توسط این رویکرد بهبود داده می­شوند. این رویکرد با یک جواب اولیه شروع می‌کند که در این کار برای هر کدام از جواب‌ها اجرا می­شود. از آنجایی که روش جستجوی همسایگی متغیرهر جواب ورودی را بواسطه ساختارهای مختلف جستجوی همسایگی بهبود می­دهد، چهار ساختار جستجوی همسایگی (NSS) برای رویکرد جستجوی همسایگی متغیرتعریف می­شود:

1- در جستجوی همسایگی اول، دو اندیس (برای هر دو ماتریس) بطور تصادفی ایجاد شده و برای ماتریس اول (یک بعدی) خانه با اندیس اول قبل از خانه با اندیس دوم درج می­شود و برای ماتریس دوم (دو بعدی) ستون با اندیس اول قبل از ستون با اندیس دوم درج می­شود.

2- در جستجوی همسایگی دوم، چهار اندیس بطور تصادفی تولید شده و دو اندیس اول قبل از دو اندیس دوم درج می­شوند.

3- در جستجوی همسایگی سوم، شش اندیس بطور تصادفی تولید شده و سه اندیس اول قبل از سه اندیس دوم درج می­شوند.

4- در جستجوی همسایگی چهارم، دو اندیس چندین بار تولید می­شود و در هر تکرار خانه‌های این دو اندیس جابه­جا می­شوند.

در رویکرد جستجوی همسایگی متغیرکه در آن ساختارهای جستجوی همسایگی مختلف استفاده شده­اند، پس از هر عملگر جستجوی همسایگی، یک عملگر آشفتگی^[17] بر روی جواب خروجی جستجوی همسایگی اعمال می­شود. علت استفاده از عملگر آشفتگی این است که در بهینه محلی گیر نکنیم. این عملگر بر اساس ویژگی‌های بهترین جوابی است که تا به حال یافت شده است. این ویژگیها در یک ماتریس احتمالی ذخیره می­شوند.

6-4. به روز رسانی مکان ذرات یا جواب‌ها

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

: جواب iام در تکرار k+1ام.

 : جواب iام در تکرار kام.

: بهترین جوابی که جوابiام به آن رسیده است.

: بهترین جوابی که در تکرار kام الگوریتم پیدا کرده است.

'-' : عملگر تقاطعی^[18] است که برای طراحی این عملگر از یک عملگر ox استفاده شده است.

: نشان دهنده عملگر جهش^[19] بر روی جواب است. در این مقاله، برای پیاده­سازی این عملگر از یک جستجوی همسایگی تکرار شونده به همراه جهش هدایت شده استفاده شده است (رحیمی واحد و همکاران، 2008).

'+' : عملگر انتخاب جواب از بین سه جواب  و و  است.

در پایان هر تکرار، PSO مقادیر p_i و p_g به روز رسانی می­شوند.

5. نتایج محاسباتی     

در این بخش، روش پیشنهادی بر روی مسایل با اندازه­های کوچک و بزرگ اجرا گردیده است. برای اثبات کارایی روش پیشنهادی، نتایج حاصل از آنها با جواب‌های تولید شده توسط الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II) مقایسه شده است.

1-5. مفروضات کلی الگوریتم­ها

در هر دو گروه از مسایل، مفروضات کلی زیر در نظر گرفته می­شود:

برای هر یک از مسایل تولید شده، هر یک از الگوریتم­ها پنج بار اجرا گردیده، نتایج به صورت متوسط مقدار حاصل از این اجراها بیان می­گردد.

• مقدار α برابر با سه در نظر گرفته می­شود.
• تعداد تکرارهای محلی (Local_iteration) برابر با پنج در نظر گرفته می­شود.
• زمان‌های پردازش برای مسایل کوچک در بازه ]40,1[ و مسایل با اندازه بزرگ در بازه ]100,1[ بصورت تصادفی تولید می­گردند.
• فاصله زمانی بین سلول‌ها به صورت تصادفی در [0.2p_mean , 0.3p_mean] تولید می­شوند. که p_mean میانگین زمان‌های پردازش کارها بر روی ماشین­هاست.
• هزینه مربوط به دیرکرد و زودکرد به طور تصادفی در بازه ]20,1[ تولید می­شوند.
• موعد تحویل کارها بر اساس روش ارایه شده توسط لوکیل (2005) تولید گردیده است. هر کدام از مسایل با مقادیر فاکتورهای r,t که برابرند با r=0.6 , t=0.4، حل گردیده­اند.

2-5. شاخص­های مقایسه^[20]

برای ارزیابی کیفیت و پراکندگی الگوریتم­های فراابتکاری چند هدفه، شاخص­های متعدد و متنوعی وجود دارند. در این مقاله، برای انجام مقایسه دو شاخص زیر مورد توجه قرار خواهند گرفت.

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

2) شاخص پراکندگی: این شاخص برای تعیین میزان جواب‌های غیرمغلوب یافت شده بر روی مرز بهینه استفاده می­گردد. تعریف شاخص پراکندگی به صورت زیر است:

در رابطه (23)،  نشان دهنده فاصله اقلیدسی بین دو جواب مجاور  و  بر روی مرز بهینه است.

3-5. نتایج مقایسه­ای مسایل با اندازه­های کوچک و بزرگ

مفروضات روش الگوریتم بهینه­سازی ذرات انبوه - الگوریتم ژنتیک:

• در مسایل با اندازه­های کوچک و بزرگ اندازه جمعیت به ترتیب برابر با 50 و 200 درنظر گرفته می­شود.
• اندازه آرشیو پارتو در مسایل با اندازه­های کوچک و بزرگ به ترتیب برابر با 50 و 200 فرض شده است.
• تعداد تکرار در الگوریتم 100 بار در نظر گرفته می­شود.

مفروضات روش الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II):

• تعداد تکرارهای محلی (Local_iteration) برابر با پنج و تعداد تکرار الگوریتم 150 در نظر گرفته می­شود.
• نرخ عملگر جهش 2/0 و عملگر تقاطع 8/0 در نظر گرفته شده است.
• اندازه جمعیت در این روش در مسایل کوچک و بزرگ به ترتیب برابر با 50 و 200 فرض می­شود.

در انتها، عملکرد روش الگوریتم بهینه­سازی ذرات انبوه - الگوریتم ژنتیک (GA-PSO) چند هدفه و الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II) برای حل مسایل طراحی شده، تجزیه و تحلیل می‌گردد. هر کدام از مسایل کوچک و بزرگ برای هر ترکیب r,t ، پنج بار اجرا گردیده­اند. جداول 4 و 5 نتایج حاصل از اجرای دو الگوریتم را نشان می­دهد.

جدول 4. مقایسه نتایج به‌دست آمده برای مسایل کوچک

جدول 5. مقایسه نتایج به‌دست آمده برای مسایل بزرگ