نوع مقاله : مقاله پژوهشی- فارسی
نویسندگان
1 دانشجوی دکتری مهندسی صنایع دانشگاه آزاد اسلامی واحد علوم و تحقیقات تهران
2 استاد پردیس دانشکده‌های فنی دانشگاه تهران
3 استادیار گروه مدیریت، واحد قائم‌شهر، دانشگاه آزاد اسلامی
4 دانش آموخته کارشناسی ارشد مهندسی صنایع دانشگاه آزاد اسلامی واحد تهران جنوب
5 استاد گروه مهندسی صنایع، دانشگاه علم و صنعت ایران
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [English]
In this paper a novel mathematical model has been proposed for multi-objective scheduling problem in a cellular manufacturing system (CMS) with the aim of minimizing the maximum completion time of jobs (i.e., makespan or Cmax), the earliness cost and the tardiness cost. Due to the complexity of such a hard problem, a hybrid algorithm, based on a genetic algorithm (GA) and particle swarm optimization (PSO), has been proposed to solve the presented model in a reasonable computational time. Furthermore, non-dominated sorting genetic algorithm (NSGA-II) as a well-known multi-objective evolutionary algorithm has been used to analyze and highlight the efficiency of the proposed hybrid algorithm. The associated results of the algorithms have been compared and analyzed. Finally, conclusions have been made and suggestions for further study have been presented.
کلیدواژه‌ها [English]
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 ماشین یا کمتر پردازش شوند. هر کار از یک توالی از پیش تعیین شده‌ای پیروی کرده و زمان پردازش مشخصی دارد. ترتیب ماشینها برای کارهای مختلف متفاوت است. برای درک بیشتر مفهوم توالی بین سلولها مفروضات در نظر گرفته شده برای این مدل عبارتند از:
2-3. اندیس‌ها
j: اندیس ماشین، j={1,…,M}
i: اندیس قطعات، i={1,…,P}
c: اندیس سلول، c={1,…,C}
k: اندیس توالی قطعات، k={1,…,K}
b:اندیس توالی سلول، b={1,…,KC}
3-3. پارامترها
tij: زمان لازم برای پردازش قطعه i بر روی ماشین j
1 اگر قطعه i به ماشین j جهت پردازش نیاز داشته باشد،
aij:
0 در غیر اینصورت.
1 اگر ماشین j به سلول c تعلق داشته باشد،
mjc:
0 در غیر این صورت.
Tic: زمان حرکت بین سلولی برای قطعه i در سلول c
Li: هزینه دیرکرد قطعه i
Ei: هزینه زودکرد قطعه i
di: زمان تحویل قطعه i
4-3. متغیرهای تصمیمگیری
1 اگر قطعه i به سلول c اختصاص یابد،
Xic:
0 در غیر این صورت.
1 اگر سلول c به توالی b اختصاص یابد،
Ycb:
0 در غیر این صورت.
1 اگر قطعه i در توالی kام سلول c واقع شده باشد،
Zikc:
0 در غیر اینصورت.
Ckjcb: زمان تکمیل قطعه واقع در توالی kام روی ماشین j در سلول c که سلول c در توالی b واقع است.
Ci: زمان تکمیل قطعه i
Cmax: حداکثر زمان تکمیل کارها
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)Cmaxرا برابر باحداکثر زمان تکمیل قرار میدهد. رابطه (18) متغیرهای 0 و 1 را معرفی میکند و در نهایت، رابطه (19) متغیرهای غیر منفی را معرفی میکند.
همانطور که اشاره شد، تابع هدف اول مدل کمینهسازی حداکثر زمان تکمیل کارهاست و هدف در مسأله زمانبندی سلولی تعیین توالی قطعات در سلولها و تعیین توالی سلولهاست. بدین معنی که در شرایطی که چند قطعه به یک ماشین اختصاص می‌یابند، ابتدا قطعهای روی آن ماشین پردازش می شود که سلول آن دارای شماره توالی کمتری بوده و توالی آن قطعه در سلول خود نیز دارای کمترین شماره توالی باشد و متناسب با این رویکرد سایر قطعات بر روی ماشین پردازش میشوند. برای درک بیشتر از مفهوم توالی بین سلولها در این قسمت از مقاله، مثالی ارایه میشود. یک شرکت تولیدی که شامل واحدهای مختلفی است، در واحد رنگ آن شرکت، چهار نوع قطعه تولیدی رنگ میشود. این واحد دارای دو سلول تولیدی بوده که پنج ماشین آن در این دو سلول مستقر شدهاند. جدول شماره 1 ماتریس مسیر ساخت قطعات بوده که نشان دهنده ماشینهای مورد نیاز برای پردازش بر روی قطعات است. همانطور که مشخص است، قطعه 1 به ماشینهای 1، 2 و 3 نیاز دارد. جدول شماره 2 زمان پردازش هر یک از قطعات را نشان میدهد. همانطور که مشخص است، زمان پردازش قطعه 1 روی ماشین 1، 2 و 3 به ترتیب 4، 5 و 12 است. و در نهایت، تعلق ماشینهای واحد رنگ شرکت به هر یک از دو سلول در جدول شماره 3 امده است.
جدول 1. ماتریس مسیر ساخت قطعات (aij)
|
ماشین قطعه |
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
1 |
1 |
0 |
0 |
|
2 |
1 |
1 |
0 |
0 |
0 |
|
3 |
0 |
0 |
1 |
1 |
1 |
|
4 |
0 |
0 |
1 |
1 |
0 |
جدول 2. زمان پردازش قطعات بر روی ماشینها (tij)
|
ماشین قطعه |
1 |
2 |
3 |
4 |
5 |
|
1 |
4 |
5 |
12 |
0 |
0 |
|
2 |
6 |
4 |
0 |
0 |
0 |
|
3 |
0 |
0 |
7 |
6 |
14 |
|
4 |
0 |
0 |
5 |
3 |
0 |
جدول 3. ماتریس تخصیص ماشینها به سلولها (mjc)
|
ماشین سلول |
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
1 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
1 |
1 |
با توجه به مسأله مطرح شده و حل مدل با در نظر گرفتن تابع هدف اول که حداقلسازی حداکثر زمان تکمیل کارها است، بهترین توالی به‌دست آمده با استفاده از نرم افزار Lingo 11 در شکل 1 نشان داده شده است.
مدت زمان کل ساخت برای این مسأله 27 بوده (27Cmax =) و با توجه به تخصیص قطعات، یک حرکت بین سلولی وجود دارد. با توجه به نتایج حل، قطعات 1 و 2 به سلول 1 و قطعات 3 و 4 به سلول 2 اختصاص یافتهاند و نهایت توالی سلولها بدین صورت است که سلول 2 در توالی اول بوده و سلول 1 در توالی دوم. حال در صورتی که توالی سلولها تغییر یابد؛ یعنی سلول 2 در توالی اول قرار گیرد و سلول 1 در توالی دوم، مدت زمان کل ساخت 48 میشود. نمایی شماتیک از زمانبندی صورت گرفته برای این توالی در شکل 2 آمده است.
شکل 1. شمایی از توالی قطعات و سلولها در شرایط اول از آزمون ارایه شده
شکل 2. شمایی از توالی قطعات و سلولها در شرایط دوم از آزمون ارایه شده
4. طراحی الگوریتم بهینه سازی ذرات انبوه برای حل مدل پیشنهادی
در این مقاله، یک الگوریتم بهینهسازی ذرات انبوه چند هدفه مبتنی بر آرشیو پارتو که با عملگرهای ژنتیک و جستجوی همسایگی متغیر ترکیب شده، برای حل مسأله زمانبندی سلولی پیشنهاد شده است. شکل 3 ساختار کلی طراحی شده برای الگوریتم بهینهسازی ذرات انبوه چند هدفه را نشان میدهد.
شکل3. ساختار کلی الگوریتم پیشنهادی
1-4. نحوه نمایش جواب‌ها
در تمام الگوریتمهای فراابتکاری، به دلیل نیاز به حل شدنی در شروع کار، لازم است حل شدنی را طبق ساختار مشخصی ذخیره کنیم که به این ساختار، نحوه نمایش جواب میگویند. در اینجا برای نمایش جواب از ساختار ماتریسی استفاده شده است. نمایش جواب در این مسأله، شامل دو ماتریس است که یکی برای نمایش توالی سلولها و دیگری برای نمایش توالی کارها در سلولها طراحی شده است. شکل شمارههای 2 و 3 به ترتیب ماتریس سطری(برداری) و ماتریس دو بعدی را نشان می دهد. در شکل 4، Cj نشان دهنده شماره سلولی است که در خانه jام توالی زمانبندی شده است. در شکل شماره 5، Aijشماره کاری است که در سلول iام در خانه jام توالی زمانبندی شده است.
شکل4. ماتریس برداری نمایش توالی سلولها
شکل5. ماتریس دو بعدی نمایش توالی کارها در سلولها
2-4. نحوه تولید جواب‌های اولیه
در این مقاله، از یک روش جستجوی ممنوع نخبهگرا[10] برای تولید جواب‌های آغازین استفاده میشود. هدف اصلی به کارگیری این روش، تولید جواب‌های اولیهای است که از نظر کیفیت[11] جواب و پراکندگی[12]، از سطح مطلوب مناسبی برخوردار باشند. جواب آغازین میتواند هر یک از جواب‌های حاصل از بهینهسازی هر یک از توابع هدف در زمان متوقف شدن نرم افزار لینگو باشد (نقطه آرمانی پویا). روش پیشنهادی در ابتدا، جواب موجود را در یک فهرست مجازی ذخیره کرده، سپس با استفاده از یک رویکرد حرکت مناسب به جستجوی جواب مطلوب دیگری که شرط (شرایط) پذیرش را دارا باشد، در مجاورت جواب میپردازد. این فرایند تا دستیابی الگوریتم به شرط پایانی ادامه پیدا میکند. رویکرد حرکت مورد استفاده، عملگر شیفت به راست است، به این صورت که دو اندیس بصورت تصادفی تولید شده و توالی بین این دو اندیس به سمت راست به صورت چرخشی شیفت داده میشوند. رویکرد حرکت طراحی شده از استراتژی هوشمند روش جستجوی ممنوع، مبتنی بر پرهیز از بازگشت به جواب‌هایی که در تکرارهای قبلی به‌دست آمدهاند، از طریق بکارگیری یک فهرست مجازی حافظه به نام فهرست ممنوع استفاده میکند. فهرست ممنوع مورد استفاده در اینجا، به مسیر جستجو وابسته بوده، از تکرار یک حرکت در طول دوره ممنوعیت[13] جلوگیری میکند. برای دستیابی به جواب‌های مطلوب از نظر کیفیت و پراکندگی در مسیر جستجو، از رابطه (20) استفاده میگردد.
fi، مقدار iامین تابع هدف توالی تولید، Fi، مقدار iامین مؤلفه نقطه آرمانی پویا وwi ، وزن تخصیص یافته به iامین تابع هدف است. هدف از به کارگیری تابع فوق بر پایه این حقیقت استوار است که اگر تابع فوق به ازای یک مجموعه از وزنهای wi برای یک جواب کمینه گردد، آن جواب متعلق به جواب‌های پارتو است.
برای تعیین شرط پذیرش جواب جدید، متغیر به صورت زیر تعریف میگردد:
در رابطه (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. تعیین pi و pg اولیه
برای هر کدام از جواب‌ها بهترین جوابی را که تا به حال به آن رسیده، به عنوان pi تعیین میکنیم و pg بهترین نقطه یا جوابی است که همه جواب‌ها یا ذرات به آن رسیده اند.
5-4. روش بهبود جواب‌ها به وسیله جستجوی همسایگی متغیر (VNS)
هر کدام از ذرات یا جواب‌ها که در جمعیت جواب‌ها موجود است، توسط این رویکرد بهبود داده میشوند. این رویکرد با یک جواب اولیه شروع میکند که در این کار برای هر کدام از جواب‌ها اجرا میشود. از آنجایی که روش جستجوی همسایگی متغیرهر جواب ورودی را بواسطه ساختارهای مختلف جستجوی همسایگی بهبود میدهد، چهار ساختار جستجوی همسایگی (NSS) برای رویکرد جستجوی همسایگی متغیرتعریف میشود:
1- در جستجوی همسایگی اول، دو اندیس (برای هر دو ماتریس) بطور تصادفی ایجاد شده و برای ماتریس اول (یک بعدی) خانه با اندیس اول قبل از خانه با اندیس دوم درج میشود و برای ماتریس دوم (دو بعدی) ستون با اندیس اول قبل از ستون با اندیس دوم درج میشود.
2- در جستجوی همسایگی دوم، چهار اندیس بطور تصادفی تولید شده و دو اندیس اول قبل از دو اندیس دوم درج میشوند.
3- در جستجوی همسایگی سوم، شش اندیس بطور تصادفی تولید شده و سه اندیس اول قبل از سه اندیس دوم درج میشوند.
4- در جستجوی همسایگی چهارم، دو اندیس چندین بار تولید میشود و در هر تکرار خانه‌های این دو اندیس جابهجا میشوند.
در رویکرد جستجوی همسایگی متغیرکه در آن ساختارهای جستجوی همسایگی مختلف استفاده شدهاند، پس از هر عملگر جستجوی همسایگی، یک عملگر آشفتگی[17] بر روی جواب خروجی جستجوی همسایگی اعمال میشود. علت استفاده از عملگر آشفتگی این است که در بهینه محلی گیر نکنیم. این عملگر بر اساس ویژگی‌های بهترین جوابی است که تا به حال یافت شده است. این ویژگیها در یک ماتریس احتمالی ذخیره میشوند.
6-4. به روز رسانی مکان ذرات یا جواب‌ها
در حالت کلی، در الگوریتم بهینهسازی ذرات انبوه ، فضای جواب باید پیوسته باشد، ولی در اینجا برای به روز رسانی مکان ذرات از عملگرهای الگوریتم ژنتیک استفاده شده است و برای همین نیازی نیست که ساختار جواب در فضای پیوسته باشد. نحوه به روز رسانی ذرات یا جواب‌ها مطابق فرمول (22) صورت میپذیرد:
: جواب iام در تکرار k+1ام.
: جواب iام در تکرار kام.
: بهترین جوابی که جوابiام به آن رسیده است.
: بهترین جوابی که در تکرار kام الگوریتم پیدا کرده است.
'-' : عملگر تقاطعی[18] است که برای طراحی این عملگر از یک عملگر ox استفاده شده است.
: نشان دهنده عملگر جهش[19] بر روی جواب است. در این مقاله، برای پیادهسازی این عملگر از یک جستجوی همسایگی تکرار شونده به همراه جهش هدایت شده استفاده شده است (رحیمی واحد و همکاران، 2008).
'+' : عملگر انتخاب جواب از بین سه جواب و و است.
در پایان هر تکرار، PSO مقادیر pi و pg به روز رسانی میشوند.
5. نتایج محاسباتی
در این بخش، روش پیشنهادی بر روی مسایل با اندازههای کوچک و بزرگ اجرا گردیده است. برای اثبات کارایی روش پیشنهادی، نتایج حاصل از آنها با جواب‌های تولید شده توسط الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II) مقایسه شده است.
1-5. مفروضات کلی الگوریتمها
در هر دو گروه از مسایل، مفروضات کلی زیر در نظر گرفته میشود:
برای هر یک از مسایل تولید شده، هر یک از الگوریتمها پنج بار اجرا گردیده، نتایج به صورت متوسط مقدار حاصل از این اجراها بیان میگردد.
2-5. شاخصهای مقایسه[20]
برای ارزیابی کیفیت و پراکندگی الگوریتمهای فراابتکاری چند هدفه، شاخصهای متعدد و متنوعی وجود دارند. در این مقاله، برای انجام مقایسه دو شاخص زیر مورد توجه قرار خواهند گرفت.
1) شاخص کیفیت: این شاخص به مقایسه کیفیت جواب‌های پارتوی به‌دست آمده توسط هر روش میپردازد. در واقع همه جواب‌های پارتوی به‌دست آمده توسط هر دو روش را با هم سطحبندی کرده و مشخص میکند که چند درصد جواب‌های سطح یک متعلق به هر روش است. هر چه این درصد بالاتر باشد، الگوریتم، از کیفیت بالاتری برخوردار است.
2) شاخص پراکندگی: این شاخص برای تعیین میزان جواب‌های غیرمغلوب یافت شده بر روی مرز بهینه استفاده میگردد. تعریف شاخص پراکندگی به صورت زیر است:
در رابطه (23)، نشان دهنده فاصله اقلیدسی بین دو جواب مجاور و بر روی مرز بهینه است.
3-5. نتایج مقایسهای مسایل با اندازههای کوچک و بزرگ
مفروضات روش الگوریتم بهینهسازی ذرات انبوه - الگوریتم ژنتیک:
مفروضات روش الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II):
در انتها، عملکرد روش الگوریتم بهینهسازی ذرات انبوه - الگوریتم ژنتیک (GA-PSO) چند هدفه و الگوریتم ژنتیک مرتب شده غیر مغلوب (NSGA-II) برای حل مسایل طراحی شده، تجزیه و تحلیل میگردد. هر کدام از مسایل کوچک و بزرگ برای هر ترکیب r,t ، پنج بار اجرا گردیدهاند. جداول 4 و 5 نتایج حاصل از اجرای دو الگوریتم را نشان میدهد.
جدول 4. مقایسه نتایج به‌دست آمده برای مسایل کوچک
|
شماره مسأله |
تعداد سلول |
تعداد ماشین |
تعداد قطعه |
شاخص کیفیت |
شاخص پراکندگی |
||
|
GA-PSO |
NSGA-II |
GA-PSO |
NSGA-II |
||||
|
1 |
2 |
10 |
7 |
87.46 |
12.54 |
587.8 |
282.8 |
|
2 |
3 |
10 |
7 |
77.84 |
22.16 |
579.2 |
314.2 |
|
3 |
4 |
10 |
7 |
100 |
0 |
640.1 |
503.9 |
|
4 |
3 |
10 |
8 |
96.74 |
3.26 |
670.1 |
169.3 |
|
5 |
4 |
10 |
8 |
96.61 |
3.39 |
711.7 |
204.1 |
|
6 |
2 |
10 |
10 |
100 |
0 |
640.7 |
609.2 |
|
7 |
3 |
10 |
10 |
100 |
0 |
726.9 |
617.2 |
|
8 |
4 |
10 |
10 |
100 |
0 |
716.6 |
603.4 |
جدول 5. مقایسه نتایج به‌دست آمده برای مسایل بزرگ
|
شماره مسأله |
تعداد سلول |
تعداد ماشین |
تعداد قطعه |
شاخص کیفیت |
شاخص پراکندگی |
||
|
GA-PSO |
NSGA-II |
GA-PSO |
NSGA-II |
||||
|
1 |
4 |
20 |
20 |
95.16 |
4.84 |
4793.1 |
1556.1 |
|
2 |
8 |
20 |
20 |
100 |
0 |
4744.2 |
7494.5 |
|
3 |
4 |
10 |
30 |
100 |
0 |
4819.9 |
1172.4 |
|
4 |
8 |
20 |
40 |
100 |
0 |
7699.6 |
4457.6 |
|
5 |
8 |
30 |
40 |
97.86 |
2.14 |
8848.8 |
3321.4 |
|
6 |
8 |
20 |
50 |
100 |
0 |
10758 |
5892.3 |
|
7 |
8 |
30 |
50 |
100 |
0 |
12639 |
7211.3 |
|
8 |
4 |
40 |
50 |
100 |
0 |
12947 |
9145.9 |
|
9 |
8 |
40 |
50 |
100 |
0 |
13486 |
11738 |
6. نتیجه گیری
در این مقاله، مدل ریاضی جدید چند هدفهای برای مسأله زمانبندی سیستم تولید سلولی ارایه شده است. اهداف مسأله مورد نظر، شامل: حداقل کردن حداکثر زمان تکمیل کارها، حداقل کردن هزینه دیرکرد و حداقل کردن هزینه زودکرد است که تاکنون به آن پرداخته نشده است. این مسأله با توجه به ماهیت پیچیده آن در زمره مسایل چند جملهای نامعین سخت (NP-hard) قرار میگیرد. بنابراین، الگوریتم تلفیقی بهینهسازی ذرات انبوه - ژنتیک چندهدفهای برای حل مسأله مورد نظر ارایه گردیده است. ابتدا چندین مسأله در ابعاد کوچک و بزرگ طراحی و سپس نتایج حاصل از اجرای روش پیشنهادی بر روی این مسایل با جواب‌های تولید شده توسط روش الگوریتم ژنتیک مرتب شده غیرمغلوب (NSGA-II) از لحاظ دو شاخص کیفیت و پراکندگی مقایسه شده است. نتایج نشان میدهد که روش پیشنهادی تلفیقی بهینهسازی ذرات انبوه - ژنتیک چند هدفه، کارایی بسیار قابل قبولی برای تولید جواب‌های پارتوی با کیفیت، متنوع و دارای پراکندگی بالاتری نسبت به روش الگوریتم ژنتیک مرتب شده غیرمغلوب داشته است. به عبارت دیگر، روش پیشنهادی، توالیهای بهینه بیشتری را در اختیار تصمیم گیرندگان نهایی جهت انتخاب قرار میدهد. در نظر گرفتن توابع هدف دیگر، در نظر گرفتن زمانهای آمادهسازی، زمانهای در دسترس برای ماشینها، بررسی مسأله در حالت پویا، در نظر گرفتن بریدگی کارها و یا استفاده از سایر روش‌های فراابتکاری برای حل مسأله مورد نظر برای تحقیقات آتی توصیه میشود.
[1] Just-In-Time
[2] Particle Swarm Optimization
[3] Genetic Algorithm
[4] Bottleneck
[5] Simulated Annealing
[6] Tabu Search
[7] Greedy Randomized Adaptive Search Procedure
[8] Flexible Manufacturing System
[9] Memetic Algorithm
[10] Elite Tabu Search
[11] Quality
[12] Diversity
[13] Tabu Tenure
[14] Aspiration
[15] Fine-Grained
[16] Truncation Method
[17] Disturb
[18] Crossover
[19] Mutation
[20] Comparison Metrics
)