پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,730,721 |
| تعداد دریافت فایل اصل مقاله | 17,563,035 |
بهینهسازی مسأله چیدمان قطعات منظم مستطیل شکل با استفاده از الگوریتم رقابت استعماری | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| پژوهش در مدیریت تولید و عملیات | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مقاله 9، دوره 9، شماره 1 - شماره پیاپی 16، اردیبهشت 1397، صفحه 161-180 اصل مقاله (1.32 M) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نوع مقاله: مقاله پژوهشی- فارسی | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/jpom.2018.92481.0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مطهره کارگربیده1؛ پدرام پیوندی* 2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1دانشجوی دکترای، دانشکده نساجی، دانشگاه یزد، یزد، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2استادیار، دانشکده نساجی، دانشگاه یزد، یزد، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| چیدمان یکی از مسائل شناختهشده در حوزۀ تحقیق در عملیات بهویژه در زمینۀ برنامهریزی تولید است. هدف اصلی بررسی مسأله چیدمان، کاهش ضایعات ناشی از برش با استفاده از بهینهچینی قطعات است. مسائل چیدمان از نوع مسائل اِنپی-سخت هستند که روشهای دقیق قادر به حل آنها نیستند. برای بهینهسازی این نوع مسائل، در مقالۀ حاضر از الگوریتم نوظهور فرا ابتکاری رقابت استعماری استفاده و نتایج آن با نتایج الگوریتم ژنتیک مقایسه شده است. برای دستیابی به نتیجۀ بهتر، پارامترهای اولیۀ الگوریتم فرا ابتکاری با روش طراحی آزمایشهای تاگوچی تنظیم شده است. کارآیی روش پیشنهادی با استفاده از مجموعهای از مسائل معیارِ مطرح در این زمینه ارزیابی و کیفیت آن با استفاده از روش آماری ANOVA آزمون شده است. نتایج این پژوهش نشان میدهد الگوریتم رقابت استعماری، الگوریتمی کارآمدتر و سریعتر در حل این نوع مسائل است. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| کلیدواژهها | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| الگوریتم رقابت استعماری؛ الگوریتم ژنتیک؛ الگوریتم چیدمان؛ بهینهسازی؛ مسائل چیدمان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
مقدمه در فرایند تولید بسیاری از صنایع نیاز است تا قطعات کوچکتر با برش از اجسام بزرگتر حاصل یا بهطور معادل، قطعههای کوچکتر در جسمی بزرگتر جای داده شوند. در این عمل معمولاً بخشهایی از جسم بزرگتر به قطعاتی بدون استفاده تبدیل و ضایعات و دورریز محسوب میشوند. کاهش چنین ضایعاتی نقش مهمی در کاهش هزینهها دارد. مسأله چیدمان یکی از موضوعات علم تحقیق در عملیات است و توجه بسیاری از پژوهشگران را به خود جلب کرده است. در بسیاری از صنایع از جمله صنایع تولیدکنندۀ بدنۀ خودرو، سازههای ساختمانی، کشتی و هواپیماسازی، کاغذ، پوشاک، چرم، سنگبری و در فعالیتهایی مانند حملونقل، انبارداری و بستهبندی، مسأله چیدمان و یا مسائل مشابه آن مشاهده میشود. تعداد الگوهایی که دستهای از قطعات میتوانند در کنار یکدیگر قرار دهند بسیار زیاد است و تعداد کمی از این الگوها ضایعات کم تولید میکنند؛ بنابراین استفاده از روال عمومی ریاضی برای حل این نوع مسائل امکانپذیر نیست. از دهۀ 50 میلادی که رایانهها بهعنوان پردازندههای سریع و اقتصادی دادهها ظاهر شدند، به مسأله چیدمان توجه بیشتری شده است. در طی سالها، دو روش اصلی اکتشافی و تقریب بر پایۀ برنامهریزی خطی برای حل این نوع مسائل ارائه شد (هوپر و تورتون[i]، 2001). استفاده از برنامهریزی خطی بیشتر محدود به مسائل چیدمان یکبعدی یا دوبعدی با تعداد قطعات کم است. بیشتر توجه پژوهشگران بهعلت بزرگبودن فضای جواب مسأله چیدمان، معطوف به روشهای ابتکاری و فرا ابتکاری حل اینگونه مسائل است؛ بهنحویکه توانایی جستجوی هوشمندانه فضای جستجو را دارند (دیکهوف[ii]، 1990). در روشهای گوناگون حل مسائل چیدمان، از انواع الگوریتمهای ابتکاری جایگذاری برای تبدیل مجموعهای از قطعات به چیدمان معتبر استفاده میشود. چیدمان معتبر، چیدمانی است که در آن قطعات هیچگونه همپوشانی با یکدیگر ندارند و بهطور کامل در داخل شئ مورد نظر قرار میگیرند. الگوریتمهای ابتکاریِ جایگذاری با قراردادن گامبهگام قطعات یا جابهجایی قطعاتِ جایگذاریشده روی شئ، مطابق قانونهای خاص،برای تولید چیدمان معتبر استفاده میشوند. بورک[iii] و همکارانش (2006)، لیو و تنگ[iv] (1999)، چازل[v] (۱۹۸۳) و اولیور و فریرا[vi] (1993) از جمله افرادی هستند که روشهایی ابتکاری برای چیدمان انواع قطعات ارائه کردهاند. لئونگ[vii] و همکارانش (2012) روشی ابتکاری براساس جستجوی ممنوعه مبتنی بر برنامهریزی غیرخطی برای حل مسأله چیدمان دوبعدی قطعات نامنظم ارائه کردهاند. در روش ابتکاری که اوزکان[viii] (2013) معرفی کرده است، برخلاف روشهای دیگر در هر مرحله، محل چیدمان یک جفت قطعه بهجای یک قطعه تعیین میشود. الگوریتمهای جستجوی فرا ابتکاری با استفاده از استراتژیهای خاص مبتنی بر استفاده از نتایج موجود با الهامگرفتن از فرایندهای طبیعی یا فیزیکی توانایی پیداکردن چیدمان مناسب، مؤثر و کارآمد را دارند. الگوریتم ژنتیک یکی از الگوریتمهای فرا ابتکاری است که برای حل مسائل چیدمان بسیار استفاده شده است. پژوهشگرانی مانند فالکنیر و فالکنوار و دلچیمبر[ix] (1992)، هوانگ[x] و همکارانش (1994)، رونارسون[xi] و همکارانش (1996)، داگلی و پوشیانُندا[xii] (1997)، لیو و تنگ (1999)، هوپر و تورتون (2002)، ولنزوئلا و وانگ[xiii] (2001)، بورتفلد[xiv](2006)، هیفی و هالاه[xv] (۲۰۰۳) و بورک و همکارانش (2006) مطالعاتی روی الگوریتم ژنتیک (ابزاری برای حل مسائل چیدمان) انجام دادهاند. الگوریتم انجماد تدریجی یکی دیگر از روشهای فرا ابتکاری است که در حل مسائل چیدمان به کار گرفته شده است. داوسلند[xvi] (1993)، لیا و چان[xvii] (1997)، فاینا[xviii] (1999)، بیسیگل[xix] و همکارانش (2005)، از جمله پژوهشگرانی هستند که از الگوریتم انجماد تدریجی برای حل مسائل چیدمان استفاده کردهاند. سومین الگوریتم فرا ابتکاری که در حل مسائل چیدمان از آن استفاده میشود، الگوریتم جستجوی ممنوعه است. ازجمله پژوهشگرانی که عملکرد الگوریتم جستجوی ممنوعه را برای حل مسائل چیدمان ارزیابی کردهاند عبارتاند از لودی[xx] و همکارانش (2004)، وی[xxi] و همکارانش (2011)، آلوارزوالد[xxii] و همکارانش (2007)، بورک و همکارانش (2006) و پورزا و مورابیتو[xxiii] (2006). شاین و کیتا[xxiv] (2012) از الگوریتم فرا ابتکاری ازدحام ذرات و وانگ[xxv] (2010) از الگوریتم ژنتیک انطباقی برای حل مسائل چیدمان دوبعدی استفاده کردهاند. مسأله چیدمانِ بین، نوعی مسأله چیدمان است که در آن قطعات باید روی تعدادی شئ با طول و عرض ثابت چیده شوند. آمارو[xxvi] و همکارانش (2013) و جونیور[xxvii] و همکارانش (2013) سعی در حل مسأله چیدمان دوبعدی قطعات نامنظم با استفاده از ترکیب الگوریتم ژنتیک با الگوریتمهای چیدمان، ابتکاری مختلف داشتند. دوسلند16 (1993) از جمله اولین پژوهشگرانی بود که از روشهای فرا ابتکاری برای حل مسائل چیدمان قطعات با اشکال منظم استفاده کرد. الگوریتم انجماد تدریجی دوسلند هر دو دسته از راهحلهای معتبر و نامعتبر را بررسی و راهحلی با کمترین همپوشانی را جستجو میکند. جیکوب[xxviii] (1996) روش فرا ابتکاری برای حل مسائل چیدمان دوبعدی قطعات منظم مستطیل شکل و نامنظم ارائه کرد. وی مسأله چیدمان را مسأله جایگشتی در نظر گرفته و از الگوریتم ژنتیک برای پیداکردن دنبالهای مناسب از قطعات برای جایگذاری و از الگوریتم جایگذاری پایین- چپ برای تبدیل دنبالۀ قطعات به یک چیدمان معتبر استفاده کرد. داگلی و پوشیانُندا[xxix] (1997) از روش دومرحلهای براساس الگوریتم شبکههای عصبی و الگوریتم ژنتیک برای حل مسأله چیدمان دوبعدی قطعات با اشکال مستطیل شکل استفاده کردند. روش داگلی و پوشیانُندا قادر است چیدمانهایی با بازدهی 95% تا 97% تولید کند. سوک و بینگل[xxx] (2006) دو روش جدید برای حل مسائل چیدمان دوبعدی معرفی کردند. آنان همانند روش جیکوب مسأله چیدمان را مانند مسأله جایگشتی مدلسازی کردند و از الگوریتمهای ژنتیک و انجماد تدریجی برای پیداکردن بهترین دنباله از قطعات و از الگوریتم جایگذاری پایین- چپ- جهشی برای تبدیل دنبالۀ قطعات به چیدمانی معتبر استفاده کردند. لی[xxxi] و همکارانش (2009) روشی مشابه روش سوک و بینگل با استفاده از الگوریتم جایگذاری تنظیمکنندۀ ارتفاع و الگوریتم ژنتیک ارائه کردند. وانگ (2010) روشی براساس ترکیب دو الگوریتم فرا ابتکاری ژنتیک و انجماد تدریجی برای حل مسائل چیدمان دوبعدی قطعات منظم ارائه کرد. در این بخش تنها روشهای ابتکاری و فرا ابتکاری حل مسائل چیدمان منظم دوبعدی تشریح شد. برای مطالعات بیشتر دربارۀ انواع روشهای ابتکاری و فرا ابتکاری حل مسائل چیدمان مختلف، به مطالعۀ کارگر و پیوندی (1393) مراجعه شود. در این پژوهش مسأله برش قطعات منظم مستطیل بررسی و حل شده است. ورودی این نوع مسائل، دنبالهای محدود از مستطیلهایی با ابعاد مشخص (قطعات) است که باید بدون همپوشانی داخل فضایی مستطیل شکل (شئ) بهعرض مشخص و طول نامحدود جایگذاری شوند. هدف از حل مسأله، یافتن دنبالهای از قطعات است که کمترین طول فضای مستطیل شکل را اشغال کنند. با بررسی روشهای حل مسائل چیدمان مشاهده میشود نوع الگوریتم فرا ابتکاری استفادهشده نقش بهسزایی در دستیابی به جواب بهینه دارد. دراینراستا به بررسی کارایی الگوریتمهای فرا ابتکاری نوظهور در حل این نوع مسائل توجه بسیاری شده است؛ از جملۀ این الگوریتمها، الگوریتم رقابت استعماری[xxxii] است. آتشپز و لوکاس، الگوریتم رقابت استعماری را ابداع کرده و در کاربردهای گوناگون توانمندی خود را نسبت به الگوریتمهای فرا ابتکاری دیگر به اثبات رسانده است ( ابراهیمی و پیوندی، 2013) و (اورتمن[xxxiii]، 2010). در این پژوهش نیز به حل مسأله چیدمان از این روش توجه بسیاری شده است و نتایج حاصله با الگوریتم معمول و پذیرفتهشده در این نوع مسائل یعنی الگوریتم ژنتیک مقایسه شد. در این پژوهش برای کارایی بهتر الگوریتمهای فرا ابتکاری، پارامترهای الگوریتمهای فرا ابتکاری بهروش تاگوچی تنظیم شده است.
شرح مسأله مسائل چیدمان شامل پیداکردن آرایشی مناسب از چیدمان مجموعهای محدود از قطعات در یک یا چند شیء مشخص است و هدف رایج این فرایند، به حداکثر رساندن بهرهبرداری و به حداقل رساندن "دورریز" مواد اولیه، در کمترین زمان ممکن است. در فرایند چیدمان باید اطمینان حاصل شود که هیچ همپوشانی بین قطعات وجود ندارد (لینز[xxxiv] و همکاران، 2003). مجموعهای از چندضلعیها P=(P1, P2,…,Pn) و شئِ مستطیل شکل C=C(W , L) با عرض ثابت W و طول متغیر L را در نظر بگیرید. پایینترین و چپترین رأس شئ C در نقطۀ مبدأ (0 ، 0) قرار دارد و موقعیت چندضلعی Pi از طریق مختصات نقطۀ مرجع آن Vi=(xi ,yi) نسبت به مبدأ شئ C بیان میشود. نقطۀ مرجع یکی از رئوس یا مرکز ثقل چندضلعی است که در این مسأله، پایینترین و چپترین رأس چندضلعی در نظر گرفته شده است. شکل 1 نمایی از مسأله چیدمان نشان میدهد. در این مسأله فرض شده است که قطعات اجازه دوران ندارند.
شکل 1- مدلی از مسأله چیدمان
مسأله چیدمان چندضلعیهای Pi روی شئ C باتوجهبه شکل 1 بهصورت مدل ذیل شرح داده میشود: Minimize L s.t.
منظور از i ترتیب قطعات برای جایگذاری است. در پژوهش حاضر هدف حداقلکردن طول L از شئ بهکمک یافتن بهترین دنباله از ترتیب قطعات برای جایگذاری روی شئ است؛ به این منظور از الگوریتم فرا ابتکاری رقابت استعماری استفاده میشود. این الگوریتم، الگوریتم جستجوی نوین و قدرتمندی است. در این روش فرض میشود فضای جستجوی شامل ترتیبهای مختلف از قطعات برای جایگذاری روی شئ است. الگوریتم فرا ابتکاری استفادهشده در طول چند دهۀ اجرا روی فضای جستجو بهسمت دنبالهای همگرا میشود که شئ با طول کمتر تولید کند. الگوریتمهای فرا ابتکاری الگوریتم ژنتیک الگوریتم ژنتیک[xxxv] روشی برای جستجوی تصادفی عددی است که از فرآیند سادهشدۀ تکامل طبیعی تقلید میکند. الگوریتم روی جمعیتی از پاسخها عمل کرده و با به کار بردن اصل بقای بهترین و تکامل، جوابهای بهتر و مناسبتر ایجاد میکند. جزئیات روش الگوریتم ژنتیک استفادهشده در این مقاله، بهصورت فلوچارت در شکل 2 نشان داده شده است (میشل[xxxvi]، 2005).
شکل 2- فلوچارت الگوریتم ژنتیک
الگوریتم رقابت استعماری این الگوریتم به فرایند استعمار، بهعنوان مرحلهای از تکامل اجتماعی-سیاسی بشر نگریسته و با مدلسازی ریاضی این پدیدۀ تاریخی، از آن بهعنوان منشأ الهام الگوریتم قدرتمند در زمینۀ بهینهسازی بهره میگیرد. فلوچارت الگوریتم رقابت استعماری در شکل 3 نشان داده شده است ( ابراهیمی و پیوندی، 2013).
شکل 3- فلوچارت الگوریتم رقابت استعماری
در ابتدای اجرای الگوریتم، باید کشورها بهصورت تصادفی تولید شوند. در الگوریتم بهینهسازی، هدف یافتن جواب بهینه برحسب متغیرهای مسأله است. در یک مسأله بهینهسازی Nvar بعدی، یک کشور آرایهای است که بهصورت زیر تعریف میشود:
pi(i=1, 2, 3, … Nvar) نشاندهندۀ متغیرهای بهینهسازی است. بهینهسازی بعد از یافتن حداقل مقدار هزینه به پایان خواهد رسید. در این مرحله تعدادی از کشورهای قوی اولیه، استعمارگر در نظر گرفته میشوند. باقیماندۀ کشورها مستعمراتی را تشکیل میدهند که هرکدام متعلق به یک امپراطوری هستند. چگونگی شکلگیری امپراطوریهای اولیه در شکل 4 نشان داده شده است. مطابق شکل 4 استعمارگران قویتر، مستعمرات بیشتری به خود اختصاص دادهاند.
شکل 4- استعمارگران اولیه تولیدشده و مستعمرات آنها
امپریالیستها سعی دارند با اعمال سیاست جذب، کشورهای مستعمره را در راستای ابعاد مختلف اجتماعی -سیاسی به خود نزدیک کنند. این بخش از فرایند استعمار در الگوریتم بهینهسازی بهصورت حرکت مستعمرات بهسمت کشور امپریالیست، مدل شده است. شکل(5-الف) شمای کلی این حرکت را نشان میدهد. همانگونهکه در این شکل نشان داده شده است، کشور مستعمره[xxxvii] بهاندازۀ x واحد در جهت خط واصل مستعمره به استعمارگر[xxxviii] حرکت کرده و به موقعیت جدید کشانده میشود. در این شکل، فاصلۀ میان استعمارگر و مستعمره با d نشان داده شده است. x نیز عددی تصادفی با توزیع یکنواخت (یا هر توزیع مناسب دیگر) است که توزیع x بهصورت رابطۀ 2 نمایش داده میشود.
در این رابطه، ضریبی بزرگتر از یک و d فاصلۀ بین استعمارگر و مستعمره است. وجود ضریب باعث میشود کشور مستعمره در حین حرکت بهسمت کشور استعمارگر، از جهتهای مختلف به آن نزدیک شود.
شکل5- الف: حرکت مستقیم مستعمره بهسمت استعمارگر مربوطه. ب: حرکت مستعمره بهسمت استعمارگر با انحراف زاویهای.
در سیاست جذب، حرکت مستعمره بهسمت استعمارگر مربوطه، لزوماً مستقیم نیست. مستعمره بهصورت غیرمستقیم، همراه با انحراف بهسمت استعمارگر مربوطه نزدیک میشود. این انحراف احتمالی با افزودن زاویهای تصادفی به مسیر جذب مستعمرات انجام میگیرد. شکل(5-ب) این حالت را نشان میدهد. بدین منظور بهجای حرکت بهاندازۀ x بهسمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، بههمان میزان ولی با انحراف در مسیر طی میکند. حرکت را بهصورت تصادفی و با توزیع یکنواخت یا هر توزیع دلخواه و مناسب دیگر نیز میتوان استفاده کرد؛ بنابراین:
در این رابطه پارامتری دلخواه است که افزایش آن باعث افزایش جستجوی اطراف امپریالیست میشود و کاهش آن نیز باعث میشود تا مستعمرات تا حد ممکن به بردار واصل مستعمره به استعمارگرِ نزدیک حرکت کنند. انقلاب، عملیاتی اساسی در الگوریتم و بهمعنای جابجایی تصادفی یک مستعمره به یک موقعیت جدید تصادفی است. انقلاب در الگوریتم از به دامافتادن پاسخها در بهینههای محلی جلوگیری و فضای جستجوی بیشتری را فراهم میکند. در حین حرکت مستعمره بهسمت استعمارگر، ممکن است بعضی از مستعمرات به موقعیت بهتری از استعمارگر برسند (هزینۀ کمتر از هزینۀ استعمارگر). در این حالت جای مستعمره و استعمارگر عوض میشود و الگوریتم با موقعیت استعمارگر جدید ادامه مییابد. قدرت یک امپراطوری برابر است با قدرت کشور استعمارگر بهاضافۀ درصدی از میانگین قدرت مستعمرات آن. هر امپراطوری که از قدرتش کاسته شود، در جریان رقابتهای امپریالیستی حذف خواهد شد. بدینصورت که یک یا چند مستعمرۀ ضعیف از ضعیفترین امپراطوریها حذف و در تصاحب سایر امپراطوریها در خواهد آمد. لزوماً قویترین امپراطوری مستعمرات مذکور را تصاحب نخواهد کرد؛ بلکه امپراطوریهای قویتر، احتمال تصاحب بیشتری دارند. برای مدلکردن این واقعیت، فرض میشود امپراطوریِ در حال حذف، ضعیفترین امپراطوری موجود است. بدین ترتیب، برای تصاحب مستعمرات ضعیف، رقابتی میان کلیۀ امپراطوریها ایجاد میشود. شکل 6 استراتژی رقابت ذکرشده را نشان میدهد.
شکل6- رقابت استعماری
الگوریتم رقابت استعماری گسسته الگوریتم اولیه که آتشپز و لوکاس[xxxix] (2007) ارائه کردهاند قابلیت اجرا روی مسائل پیوسته را دارد. در مسائل بهینهچینی قطعات هدف یافتن دنبالهای از ترتیب قطعات برای تولید پاسخ بهینه است؛ بنابراین مسأله از انواع مسائل جایگشتی است. ازآنجاییکه مسائل جایگشتی از نمونۀ بارز مسائل گسسته هستند، استفاده از الگوریتم رقابت استعماری معمول برای حل اینگونه مسائل امکانپذیر نیست. راهکار مناسب برای حل این موضوع تبدیل متغییرهای گسسته به متغییرهای پیوسته در طول اجرای الگوریتم است. در این راهکار فرض میشود هدف بهینهسازی مسأله پیوسته است و تمام عملیات برای مسأله پیوسته انجام میشوند؛ بنابراین الگوریتم رقابت استعماری روی مجموعهای از متغییرهای پیوسته عمل و متغیرهای بهینهسازی را تنها در مرحلۀ ارسال به تابع هزینه، گسسته میکند. برای این منظور استفاده از یک تابع واسط در مرحلۀ ارسال متغییرها به تابع هزینه لازم است. تابع واسط متغیر پیوسته را هنگام ارزیابی میزان هزینه، گسسته و به تابع هزینۀ مسأله بهینهسازی ارسال میکند. سپس این مقدار هزینه به الگوریتم رقابت استعماری برای ادامۀ عملیات برگردانده میشود. در اتمام اجرای الگوریتم رقابت استعماری مقادیر پاسخهای بهینۀ تولیدشده در الگوریتم، پیوسته هستند. این مقادیر پیوسته با تابع واسط، گسسته و بهعنوان جواب اصلی مسأله گسسته نمایش داده میشوند. در این مقاله برای حل مسأله بهینهچینی قطعات با استفاده از الگوریتم رقابت استعماری، ابتدا برای تولید کشورها به تعداد N_var اعداد حقیقی تصادفی بین بازۀ صفر تا یک تولید و به تعداد کشور مورد نیاز تکرار میشوند. سپس از کشورهای تولیدشده برای استفاده در الگوریتم رقابت استعماری استفاده میشود. در مرحلۀ ارسال متغییرها به تابع هزینه، از مکان مرتبشدۀ (از کوچک به بزرگ و یا برعکس) هر کشور بهعنوان مقادیر آن برای ارزیابی قدرت هر کشور استفاده میشود (تابع واسط پیشنهادی برای تبدیل دنبالۀ اعداد پیوسته به دنبالۀ اعداد گسسته). در واقع با استفاده از این روش الگوریتم رقابت استعماری روی اعداد حقیقی اعمال میشود؛ ولی هنگام ارزیابی از مکان مرتبشدۀ اعداد حقیقی داخل هر آرایه استفاده میشود که خصوصیات لازم در مسائل گسسته مانند عدد طبیعیبودن و تکرارناپذیری را دارذ. شکل 7 فلوچارت گسستهسازی متغییرها و انتقال آنها به تابع هزینه را نشان میدهد.
شکل 7- فلوچارت گسستهسازی متغییرها قبل از انتقال به تابع هزینه
شکل 8 مراحل تبدیل دنبالۀ اعداد حقیقی به دنبالۀ قطعات (توسط تابع واسط) را نشان میدهد.
شکل8 - مراحل تبدیل دنباله اعداد حقیقی به دنباله قطعات
الگوریتمهای ابتکاری جایگذاری برای محاسبۀ تابع هدف در طول اجرای الگوریتم جستجوی فرا ابتکاری، لازم است مجموعۀ قطعات مطابق ترتیب یافتشده با الگوریتم جایگذاری روی شئ جایگذاری شوند و بازدهی شئ بهعنوان تابع هدف محاسبه شود. همانطورکه در شکل 9 مشاهده میشود، مسأله چیدمان شامل جایگذاری N قطعه با عرض و طول درفضای مستطیل شکل بهعرض است. درصورتیکه فضای طولی اشغالشده در چیدمان برابر L باشد، بازدهی چیدمان از رابطۀ 4 محاسبه میشود.
شکل 9- نمونهای از چیدمان i قطعه در عرض W روشهای زیادی برای جایگذاری قطعات پیشنهاد شده است. این روشها شامل، روشهای الگوریتم جایگذاری پایین- چپ، الگوریتم پایین- چپ- جاذبهدار، الگوریتم پایین- چپ- جهشی، الگوریتم پایین-چپ- توسعهیافته و الگوریتم بهترین تناسب هستند. در این پژوهش، ابتدا بین عملکرد و سرعت اجرای پنج الگوریتم ابتکاری جایگذاری پایین- چپ (BL)، الگوریتم پایین- چپ- جاذبهدار (BLLT)، الگوریتم پایین- چپ- جهشی (BLF)، الگوریتم پایین-چپ- توسعه یافته (BLD) و الگوریتم بهترین تناسب (BF) ، مقایسهای انجام شده است. سپس الگوریتم جایگذاری بهینه برای ترکیب با الگوریتمهای فرا ابتکاری انتخاب شدهاند.
تنظیم پارامترها انتخاب مناسب پارامترها نقش بسیار مهمی در کارایی روشهای فرا ابتکاری دارد. در این پژوهش، برای تعیین سطح مناسب هر پارامتر، از روش تاگوچی استفاده شده است (تاگوچی[xl] و همکاران، 2005). این روش بر پایة حداکثرکردن معیار عملکرد ( که نرخ سیگنال به نویز نامیده می شود)، برای تعیین سطوح بهینة فاکتورهای مؤثر در محاسبات است. بهطور کلی روش تاگوچی بهصورت زیر است: • برای هر آزمایش نرخ سیگنال به نویز و جدول آنالیز واریانس مشخصههای کیفیت آن محاسبه میشود. • برای فاکتورهایی که اثر مهمی بر نرخ سیگنال به نویز دارند، سطحی که نرخ سیگنال به نویز بالاتری دارد بهمنزلة سطح بهینة فاکتور انتخاب میشود. • فاکتوری که اثر مهمی بر نرخ سیگنال به نویز ندارد، اما بر میانگین پاسخ اثر مهمی دارد، سطح با مقدار هدف بهتر انتخاب میشود. • برای فاکتورهایی که اثر مهمی بر دو نرخ سیگنال به نویز و میانگین پاسخ ندارند، سطح با مقیاس اقتصادی بهمنزلة مقدار بهتر برای الگوریتم در نظر گرفته میشود. براساس این روش زمانی که مسأله از نوع بهینهسازی و پاسخِ تا حد ممکن کوچک مدنظر است از رابطۀ 5 استفاده خواهد شد. در این رابطه منظور از S سیگنال و N مقادیر نویز در نظر گرفته شده است.
آزمایشات برای تنظیم پارامترهای الگوریتم رقابت استعماری و ژنتیک در سه سطح انجام شده است. جدولهای 1 و 2 مقدار پارامترهای الگوریتم رقابت استعماری و ژنتیک را نشان میدهند.
جدول 1- پارامترهای الگوریتم رقابت استعماری و سطوح آن پارامتر
جدول 2- پارامترهای الگوریتم ژنتیک و سطوح آن پارامتر
مطابق تعداد پارامترها و سطوح مختلف آنها، طرح تاگوچی L27 برای تنظیم پارامترهای الگوریتم رقابت استعماری و طرح تاگوچی L9 برای تنظیم پارامترهای الگوریتم ژنتیک استفاده شده است. مقادیر نرخ S/N برای الگوریتم رقابت استعماری در شکل 10 نشان داده شده است.
شکل 10- میانگین نرخ S/N در هر سطح برای تنظیم پارامترهای الگوریتم رقابت استعماری
نتایج بهدستآمده بهروش تاگوچی نشان میدهد، سطوح 3، 3، 2، 3، 1، 3 و 3 بهترتیب بهترین سطوح برای پارامترهای تعداد کشورها، تعداد امپراطوری، تعداد دههها، ضریب جذب، ضریب انحراف، نرخ انقلاب و نرخ مشارکت الگوریتم رقابت استعماری و سطوح 3، 3، 2 و 2 بهترتیب بهترین سطوح برای پارامترهای جمعیت اولیه، تعداد نسلها، نرخ ترکیب و نرخ جهش الگوریتم ژنتیک هستند.
نتایج پژوهش در این پژوهش ابتدا عملکرد سه الگوریتم جایگذاری (پایین- چپ، الگوریتم پایین- چپ- جاذبهدار، الگوریتم پایین- چپ- جهشی) با یکدیگر مقایسه، سپس الگوریتم جایگذاری مناسب انتخاب و با الگوریتم رقابت استعماری و ژنتیک ترکیب شدهاند. برای پیادهسازی الگوریتم رقابت استعماری و الگوریتم ژنتیک از برنامهنویسی تحت زبان برنامهنویسی متلب نسخه 2014a استفاده شد. برای ارزیابی عملکرد روش پیشنهادی از 22 مجموعه داده معیار استفاده شده است که شامل 17 تا 97 قطعه و قابل چیدمان بهصورت 100 درصد هستند (هوپر، 2000). جدول 3 مشخصات 22 مجموعه دادههای معیار را نشان میدهد.
جدول 3- مشخصات مجموعه دادهها
برای مقایسۀ عملکرد الگوریتمهای جایگذاری نام برده شده در بخش (4) از لحاظ سرعت و قابلیت در تولید چیدمان بهینه، از مجموعه داده T1a استفاده شد. به این منظور تمام جایگشتهای ممکن مجموعه داده T1a که شامل !17 حالت است با استفاده از پنج الگوریتم جایگذاری نام برده شده به چیدمان معتبر تبدیل شدند و مدت زمان اجرا و بازدهی چیدمان تولیدی هریک از الگوریتمهای ابتکاری با یکدیگر مقایسه شدند. سرعت و بازدهی چیدمانهای حاصل در جدول 4 گزارش شده است.
جدول 4- نتایج اجرای الگوریتمهای ابتکاری جایگذاری در چیدمان مجموعه داده T6a،
نتایج نشان میدهد الگوریتم پایین- چپ- جهشی قادر است چیدمانهایی با بازدهی بالایی تولید کند؛ اما سرعت اجرای این الگوریتم پایین است. همچنین نتایج نشان میدهد علیرغم سرعت بالای الگوریتم پایین-چپ و پایین-چپ توسعهیافته، موفق به تولید چیدمان با بازدهی کامل برای این مجموعه داده نشدهاند. همچنین میانگین بازدهی چیدمانهای حاصل از آنها نسبت به الگوریتم پایین- چپ-جهشی و الگوریتم پایین- چپ- جاذبهدار، پایین است. نتایج حاصل از اجرای الگوریتم بهترین تناسب از هر دو لحاظ سرعت اجرا و بازدهی چیدمان حاصل قابل قبول نیست. این موضوع نشان میدهد این الگوریتم برای استفاده در این نوع چیدمان مناسب نیست. از مقایسۀ نتایج نمایشدادهشده در جدول 4 نتیجه میشود الگوریتم جایگذاری پایین- چپ- جاذبهدار قادر است با سرعت مناسب جوابهای قابل قبولی تولید کند. در پژوهش دیگری که نویسندگان این پژوهش انجام دادهاند نیز مناسببودن الگوریتم جایگذاری پایین- چپ- جاذبهدار به اثبات رسیده است (کارگر و پیوندی، 1393)؛ بنابراین در این پژوهش برای تبدیل دنبالۀ قطعات به چیدمان معتبر از الگوریتم پایین-چپ-جاذبهدار استفاده میشود. شکل 11 چیدمان دنبالهای از قطعات مستطیلی با جایگشت (۲، ۶، ۴، ۷، ۳، ۰، ۱، ۵)، توسط الگوریتم جایگذاری پایین- چپ- جاذبهدار را نشان میدهد.
شکل 11- جایگذاری دنبالهای از قطعات مستطیلی با جایگشت (۲، ۶، ۴، ۷، ۳، ۰، ۱، ۵) توسط الگوریتم جایگذاری پایین- چپ- جاذبهدار،
همانطورکه بیان شد در این پژوهش برای ارزیابی عملکرد الگوریتم رقابت استعماری در حل مسائل چیدمان، از مقایسۀ آن با الگوریتم ژنتیک استفاده شده است. الگوریتم ژنتیک، الگوریتم معمول در حل اینگونه مسائل است. چیدمان هریک از 22 مجموعه داده معیار 20 مرتبه با هریک از دو الگوریتم فرا ابتکاری آزمون شدهاند. بهترین نتایج بهدستآمده با هریک از الگوریتمهای فرا ابتکاری برای 22 مجموعه دادهها در جدول 5 نمایش داده شده است. حداکثر زمان اجرا برای 22 مجموعه داده معیار با هریک از الگوریتمهای فرا ابتکاری، 15 دقیقه بوده است. از مقایسۀ نتایج جدول 4 مشاهده میشود الگوریتم رقابت استعماری به چیدمان با بازدهی 100%، 4 مجموعه داده دست یافته است و درنهایت 12 چیدمان با بازدهی بالاتر نسبت به الگوریتم ژنتیک تولید کرده است. همچینین مشاهده میشود میانگین بازدهی چیدمانهای تولیدشده با الگوریتم رقابت استعماری 12/2 درصد بالاتر از میانگین بازدهی چیدمانهای تولید شده با الگوریتم ژنتیک است. شکل 12، دو نمونه چیدمانهای بهینۀ یافتشده با الگوریتم رقابت استعماری را نشان میدهد.
جدول 5- بهترین نتایج بهدستآمده با هریک از الگوریتمهای فرا ابتکاری برای 22 مجموعه دادهها معیار
شکل 12- چیدمان بهینۀ یافتشده با الگوریتم رقابت استعماری برای مقایسۀ دقیقتر عملکرد الگوریتم رقابت استعماری و الگوریتم ژنتیک در حل این نوع مسائل چیدمان، از آزمون آماری ANOVA برای بررسی معناداربودن تفاوت نتایج حاصل از این دو الگوریتم استفاده شده است. جدول 6 خلاصۀ این نتایج را نشان میدهد.
جدول 6- خلاصۀ نتایج آزمون ANOVA
همانطورکه جدول 5 نشان میدهد تفاوت نتایج حاصل از دو الگوریتم فرا ابتکاری معنادار است. در روش حل مسائل چیدمان علاوه بر قابلیت روش در دستیابی به جواب بهینه، مدت زمان حل مسأله نیز پارامتر با اهمیت در ارزیابی روش است. بهدلیلآنکه نوع نرمافزار و نحوۀ کدنویسی برنامه تأثیر زیادی در میانگین زمان اجرای الگوریتم دارد، پارامتر میانگین زمان اجرای الگوریتم، پارامتر مناسبی برای مقایسه نیست؛ از اینرو برای بررسی دقیقتر هر الگوریتم پارامتر تعداد فراخوانی تابع هدف نیز در نظر گرفته شده است. در واقع زمانبرترین قسمت هر الگوریتم بخش ارزیابی مقدار تابع هدف است و از مقدار آن زمان لازم الگوریتم، مستقل از مشخصات رایانه تقریب زده میشود. درعینحال با هر بار فراخوانیِ تابع هدف، جواب یافتهشده با الگوریتم ارزیابی میشود؛ بنابراین الگوریتمی قویتر است که با تعداد فرخوانی کمترِ تابع هدف، نتایج بهتری ارائه کند؛ برای مثال شکل 13 تغییرات تعداد فراخوانی تابع هدف (NFE) در طول نسل برای بهترین جواب الگوریتمهای ژنتیک و الگوریتم رقابت استعماری را برای مجموعه قطعاتJ1 و J2 نشان میدهد.
شکل 13- تغییرات تعداد فراخوانی تابع هدف در طول نسل برای بهترین جواب با الگوریتمهای ژنتیک و رقابت استعماری برای الف) مجموعۀ قطعات J1، ب)مجموعۀ قطعات J2، همانطورکه از نمودارهای شکل 13 مشخص است، تعداد فراخوانی تابع هدف با الگوریتم ژنتیک در چیدمان هر دو مجموعه قطعات بیشتر از الگوریتم رقابت استعماری است. این موضوع بهمنزلۀ زمان بیشتر اجرای الگوریتم ژنتیک است. همچنین الگوریتم ژنتیک با وجود زمان اجرای بیشتر چیدمانهایی با میانگین بازدهی کمتر تولید کرده است؛ بنابراین الگوریتم رقابت استعماری جایگزین خوبی برای الگوریتم ژنتیک در حل مسائل چیدمان قطعات مستطیل است.
نتیجهگیری در این مقاله برای حل مسائل برش قطعات منظم مستطیل شکل، روش فرا ابتکاری براساس الگوریتم نوظهور رقابت استعماری ارائه شد. کارایی روش پیشنهادی با استفاده از 22 مجموعه داده معیار ارزیابی و نتایج حاصل با نتایج الگوریتم ژنتیک مقایسه شد. عملکرد دو روش فرا ابتکاری براساس دو فاکتور قابلیت روش در دستیابی به چیدمانی با بازدهی بالاتر و سرعت روش ارزیابی شده است. براساس آنالیز آماری نتایج حاصل از اجرای روشهای فرا ابتکاری مشاهده شد نتایج حاصل از ICA تفاوت معناداری با نتایج حاصل از GA دارد و الگوریتم ICA قادر به دستیابی به چیدمانهایی با بازدهی بالاتر است. همچنین الگوریتم ICA به چیدمان صد در صد 4 نمونه از 22 مجموعه داده دست یافته است. الگوریتم رقابت استعماری قادر است با تعداد NFE بسیار کمتر به جواب مشابه با الگوریتم ژنتیک دست یابد. ازآنجاکه تعداد NFE کمتر در طول اجرا الگوریتم فرا ابتکاری نشاندهندۀ سرعت بیشتر اجرای الگوریتم است، الگوریتم رقابت استعماری روشی سریعتر در حل اینگونه مسائل جایگشتی است. درنهایت نتیجه میشود الگوریتم ICA روشی کارامدتر نسبت به الگوریتم ژنتیک در حل مسائل چیدمان است. در حل مسائل چیدمان با استفاده از روشهای فرا ابتکاری، تعداد بهینههای محلی زیاد باعث سردرگمی الگوریتم در پیداکردن مسیر درست بهسمت بهینه مطلق میشود. راهکاری که برای حل این مشکل مناسب دیده میشود، تأثیردادن پارامتر دیگری بهغیر از طول چیدمان در تابع هدف است. به اینگونه که تابع هدف دو چیدمان با طولی یکسان از مجموعۀ قطعات یکسان، از یکدیگر متمایز هستند. مناسب دیده میشود در پژوهشهای آینده این موضوع بررسی شود. [i] Hopper and Turton [ii] Dyckhoff [iii] Burke [iv] Liu and Teng [v] Chazelle [vi] Oliveira and Ferreira [vii] Leung [viii] Ozcan [ix] Falkenauer and Delchambre [x] Hwang [xi] Runarsson [xii] Dagli and Poshyanonda [xiii] Valenzuela and Wang [xiv] Bortfeldt [xv] Hifi and Hallah [xvi] Dowsland [xvii] Lai and Chan [xviii] Faina [xix] Beisiegel [xx] Lodi [xxi] Wei [xxii] Alvarez and Parreno [xxiii] Pureza and Morabito [xxiv] Shin and Kita [xxv] Wang [xxvi] Amaro and Pinheiro [xxvii] Junior [xxviii] Jakobs [xxix] Poshyananda [xxx] Soke and Bingul [xxxi] Li [xxxii] Imperialist Competitive Algorithm – ICA [xxxiii] Ortmann [xxxiv] Lins [xxxv] Genetic Algorithm - GA [xxxvi] Micell [xxxvii] Colony [xxxviii] Imperialist [xxxix] Lucas [xl] Taguchi | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kargar,M. ,Payvandy,P.(2015)"Application of heuristic methods in marker making",9th NTC, Iran, Tehran [In Persian]
Kargar,M. ,Payvandy,P.(2015)"An Overview for Marker Making Methods Using Heuristic and Metaheuristic Algorithms", Textile Science and Technology, 11(2), 17-28, [In Persian]
Alvarez, V. R., Parreno, F., & Tamarit, J. M. (2007). "A Tabo search algorithm for a two-dimensional non-guillotine cutting problem". European Journal of Operational Research, 183, 1167-1182.
Amaro, B., Pinheiro, P. R., & Saraiva, R. D. (2013). "A hybrid methodology for tackling the irregular strip packing problem". in Proceedings of the 11th IFAC Workshop on Intelligent Manufacturing Systems (IMS ’13), 11, 396–401.
Atashpaz-Gargari, E., & Lucas, C. (2007). "Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition". IEEE Congress on Evolutionary Computation, 4661-4667.
Beisiegel, B., Kallrath, J., Kochetov, Y., & Rudnev, A. (2005). "Simulated annealing based algorithm for the 2D bin packing problem with impurities". International CoNFErence of the German Operations Research Society (GOR), Bremen.
Bortfeldt, A. (2006). "A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces". European Journal of Operational Research, 172, pp. 814-837.
Burke, E. K., Hellier, R., Kendall, G., & Whitwell, G. (2006). "A new Bottom- Left-Fill heuristic algorithm for the 2d irregular packing problem". European Journal of Operational Research, 54, 587-601.
Burke, E. k., Kendall, G., & Whitwell, G. (2004). "A new placement heuristic for the orthogonal stock-cutting problem". European Journal of Operational Research, 52(4), 655–671.
Chazelle, B. (1983). "The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation". J. IEEE. T. Comput, 32, 697-707.
Dagli, C.H., & Poshyanonda, P. (1997). "New approaches to nesting rectangular patterns". Journal of Intelligent Manufacturing. 8(3), 177-190.
Dowsland, K. (1993). "Some experiments with simulated annealing techniques for packing problems". European Journal of Operational Research, 68, 389-391.
Dyckhoff, H. (1990). "Typology of cutting and packing problems". European Journal of Operational Research, 44, 145-159.
Ebrahimi, S., & Payvandy, P. (2013). "Optimization of the Link Drive Mechanism in a Sewing Machine Using Imperialist Competitive Algorithm". International Journal of Clothing Science and Technology, 26(3), 247 – 260.
Faina, L. (1999). "An application of simulated annealing to the cutting stock problem". European Journal of Operational Research, 114, 542-556.
Falkenauer, E. & Delchambre, A. (1992). "A genetic algorithm for bin-packing and line balancing". Proceedings of the 1992 IEEE International CoNFErence on Robotics and Automation, 1186-1192.
Hifi, M., & Hallah, R. M. (2003). "Hybrid algorithm for the two dimensional layout problem: the cases of regular and irregular shapes". Journal of International Transactions in Operational Research, 10, 195-216.
Hopper E., & Turton B. C.H. (2001). "A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems". Artificial Intelligence Review, 16, 257 – 300.
Hopper, E., & Turton, B.C.H. (2001). "An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem". European Journal of Operational Research, 128(1), 34-57.
Hopper. E. (2000). Two-dimensional packing utilizing evolutionary algorithms and other meta-heuristic methods. Ph.D Thesis, University of Wales, Cardi.
Hwang, S. M., Cheng, Y. K., & Horng, J. T. (1994). "On solving rectangle bin packing problems using genetic algorithms". Proceedings of the 1994 IEEE International CoNFErence on Systems, Man and Cybernetics, 1583-1590.
Jakobs, S., (1996). "On genetic algorithms for the packing of polygons". European Journal of Operational Research. 88, 149- 165.
Junior, B. A. , Pinheiro, P. R. , & Saraiva, R. D. (2013). "Tackling the irregular strip packing problem by hybridizing genetic algorithm and bottom-left heuristic". in Proceedings of the IEEE Congress on Evolutionary Computation (CEC ’13), 3012–3018, Cancun, Mexico.
Lai, K. K., & Chan, J. W. M. (1997). "Developing a simulated annealing algorithm for the cutting stock problem". Computers & Industrial Engineering, 32, 115-127.
Leung, S. C. H., Lin, Y., & Zhang, D. (2012). "Extended local search algorithm based on nonlinear programming for twodimensional irregular strip packing problem". Computers and Operations Research, (39), 678–686.
Li, M., Huang, P.J., & Zhou, Z. (2009). "Optimal Layout of Rectangular Parts Based on Niche Genetic Algorithm". Journal of Hunan University, 1, 322-330.
Lins, L., Lins, S., & Morabito, R. (2003). "An L-Approach For Packing (l, w) Rectangles Into Rectangular And L-Shaped Pieces". Journal of Operational Research Society, 54(7), 777-789.
Liu, D., & Teng, H. (1999). "An improved BL-algorithm for genetic algorithms of the orthogonal packing of rectangles". European Journal of Operational Research,112(2), 413-419.
Lodi, A., Martello, S. & Vigo, D. (2004). "TSpack: A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems". Annals of Operations Research, 131(1), 203-203.
Mccell, J. (2005). "Genetic Algorithm for Modeling and Optimization". Journal of Computational and Optimization, 184, 205-222.
Oliveira, J. F., & Ferreira, J. S. (1993). "Algorithms for nesting problems". Journal of Intelligent Manufacturing, 39, 255-276.
Ortmann. F. (2010). Heuristics for online rectangular packing problems, PhD dissertation, University of Stellenbosch.
Ozcan, E., Kai, Z., & Drake, J. H. (2013). "Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing". Expert Systems with Applications , 40, 4035–4043.
Pureza, V., Morabito, R. (2006). "Some experiments with a simple Tabu search algorithm for the manufacturer's pallet loading problem". Journal of Computers & Operations Research, 33, 804-819.
Runarsson, T. P., Jonsson, M. T., & Jensson P. (1996) "Dynamic dual bin packing using fuzzy objectives". 8th IEEE International CoNFErence on Collaborative. Nagoya, 219-222.
Shin, Y. B., & Kita, E. (2012). "Solving two-dimensional packing problem using particle swarm optimization". Computer Assisted Methods in Engineering and Science, 19, 241–255.
Soke, A., & Bingul, Z. (2006). "Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems". Engineering Applications of Artificial Intelligence, 19, 557–567.
Taguchi, G., Chowdhury, S., & Wu, Y. (2005). Taguchi’s Quality Engineering Handbook. Wiley, New Jersey.
Valenzuela, C. L., & Wang, P. Y. (2001). "Heuristics for large strip packing problems with guillotine patterns: An empirical study". Metaheuristic International CoNFErence 2001, Porto.
Wang, B. (2010). "An Adaptive Genetic Algorithm for 2D Packing Problem". ModernApplied Science, 4(4),1- 4.
Wei, L., Oon, W-C., Zhu, W., & Lim, A. (2011). "A skyline heuristic for the 2d rectangular packing and strip packing problems". European Journal of Operational Research, 215, 337–346. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
آمار تعداد مشاهده مقاله: 2,548 تعداد دریافت فایل اصل مقاله: 1,117 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||