بخشی از مقاله
چکیده:
هدف اصلی مسائل برش بر حداقل نمودن ضایعات ناشی از برش میباشد. در این مقاله ما به حل مسئله برش دوبعدي میپردازیم. برش استفاده شده در این روش غیرگیوتینی میباشد. هدف مسئله حداقل نمودن هزینهي سفارشدهی و نگهداري مواد خام ضمن تامین تمامی تقاضاي ایجاد شده براي قطعات میباشد. در این مسئله صفحات مواد خام با ابعاد متفاوت مورد استفاده قرار میگیرد . هنگام ایجاد الگوي برش قطعات قابلیت چرخش 90 درجه دارند.روشهاي دقیق و همچنین هیوریستیکهاي متفاوتی جهت حل اینگونه مسائل ارائه شده است. با افزایش اندازه مسئله به دلیل پیچیدهتر شدن آن روشهاي دقیق قادر به حل مسائل با سایز بزرگ نمیباشند بنابراین طی سالهاي اخیر تمایلات پژوهشگران به استفاده از روشهاي هیوریستیک افزایش پیدا کرده است. هیوریستیکهاي چیدمان - - - bottom left - bl و همچنین - - - bottom left fill - blf در بسیاري از پژوهش هاي مرتبط با مسائل برش مورد استفاده قرار میگیرد. در این مقاله روشی با ترکیب الگوریتم ژنتیک - - Genetic Algorithm و هیوریستیک - Bottom Left Fill - BLF - - و هیوریستیک Two-phaseپیشنهاد شده است.
کلمات کلیدي: برش دو بعدي؛ برش غیرگیوتینی؛ کنترل موجودي؛ الگوریتم ژنتیک؛ هیوریستیک ; blf هیوریستیک .Two-phase
.1 مقدمه
تمرکز اصلی تحقیقات انجام شده در زمینه برش مواد خام - CSP - بر حداقل نمودن ضایعات ناشی از برش میباشد. مسئله اي که اکثر مقالات مرتبط با CSP به آن توجه میکنند این است که چگونه قطعات کوچک را روي صفحات بزرگ مواد خام قرار داده و برش دهند بطوریکه الگوي چیدمان ایجاد شده کمترین ضایعات را ایجاد کند. در بسیاري از فرآیندهاي تولید با مسئله برش مواد خام - CSP - میشوند. که این مسائل با توجه به ویژگی ها و محدودیت هایشان به دستههاي مختلف تقسیم میشوند. این ویژگی ها عبارتند از:
-1 ابعاد : مسئله برش میتواند 1 بعدي، 2 بعدي و 3 بعدي باشد.
-2 نوع مواد خام : مواد خام مورد استفاده میتواند بصورت یک صفحه با ابعاد مشخص ،تعدادي صفحه با ابعاد یکسان و یا تعدادي صفحه مواد خام با ابعاد متفاوت مورد استفاده قرار گیرد.
-3 تنوع قطعات مورد نیاز: قطعات با ابعاد یکسان و قطعات با ابعاد متفاوت. -4 نوع برش : برش گیوتینی و غیر گیوتینی .
یکی دیگر از ویژگی هایی که در مسائل برش مختلف تمایز ایجاد میکند قابل چرخش بودن یا نبودن قطعات هنگام ایجاد الگوي برش است.در برخی مسائل قطعه با طول l و عرض w با قطعه با طول w و عرض l متفاوت است، در این مسائل قطعات غیر قابل چرخش میباشند. در مسائلی که قطعات اجازه چرخش 90 درجه را دارند قطعه با طول l و عرض w با قطعه با طول w و عرض l تفاوتی ندارد.امروزه هر صنعت با در نظر گرفتن محدودیتهاي موجود و شرایط کاري خاص خود از تکنولوژي، روشها و دستگاههایی متناسب با آن شرایط و محدودیتها استفاده میکند. صنایع برش صفحات - فلزي، چوبی، شیشهاي و... - براي تبدیل صفحات مستطیلی مواد خام به قطعات مستطیلی کوچکتر از دو روش برش گیوتینی و غیر گیوتینی استفاده میکنند. برش گیوتینی، برشی است که با هر برش صفحه مورد نظر با هر برش به دو مستطیل تقسیم میشود،این برش از یک ضلع آزاد مستطیل شروع می شود و موازي با یکی از اضلاع ورق اصلی، به ضلع آزاد مقابل ختم میشود - شکل-1 الف - ، اما در برش غیرگیوتینی، چنین فرضی وجود ندارد.
با هر بار برش صفحه بصورت غیرگیوتینی حداقل 5 مستطیل ایجاد میشود - شکل-1ب - نمونهاي از یک برش غیر گیوتینی است - . در این مقاله از برش غیر گیوتینی براي تولید و برش الگو استفاده خواهد شد. در این مقاله ما به حل مسئله برش دو بعدي با هدف حداقل نمودن ضایعات و همچنین تامین تمام تقاضا براي هر قطعه میپردازیم. نوع برش مواد خام غیر گیوتینی بوده و مواد خام به اندازه کافی در انبار موجود است. باید توجه داشت که مسئله برش - Cutting Problem - با مسئله برش مواد خام - Cutting Stock Problem - متفاوت است. در حقیقت - CP - به دنبال پیدا کردن بهترین الگوي برش به نحوي است که مجموع سود بدست آمده از برش صفحات را حداکثر کند. در صورتیکه CSP مسئله برش تمامی قطعات کوچک به تعداد مورد نیاز از تعدادي صفحه مواد خام است بطوریکه تعداد صفحات استفاده شده حداقل شود.
با توجه به اینکهCSP به حوزه NP-HARD تعلق دارد هیوریستیکها و متاهیوریستیکهاي مختلفی براي حل این مسئله ارائه شده است - Chu and Antonio - 1999 - . - Ayadi et all ,2009 هیوریستیکی بر پایه ترکیب الگوریتم هاي bl و shelf براي حل CSP گیوتینی ارائه دادند. - Morabito and Arenales - ,1996 هیوریستیک هاي مختلفی براي بهبود رویکرد برش طبق فرایند branch and bound جهت حل cp غیر گیوتینی پیشنهاد دادند . هیوریستیک هاي دیگري نیز توسط - Bengtsson, 1982 - و - El-Bouri et al, 1994 - در جهت حل مسئله بسته بندي - bin-packing - توسعه یافته است. - - El Hayek,et al, 2008 به توسعه هیوریستیکی بر پایهي ترکیب مفهوم بیشینه کردن فضاي استفاده شده و متریک هیوریستیک جهت حل مسئه cp غیر گیوتینی پرداختند. متاهیوریستیک هایی نیز براي حل این مسئله ارائه شدهاند به عنوان مثال متاهیوریستیک - SA - Simulated Annealing توسط - Lai and Chan 1997 - ،الگوریتم ژنتیک - Beasley 2004 - ، جست و جوي ممنوعه , - Alvarez et all, 2007 - بهینه سازي حرکت ذرات - PSO - - Barkallah et all, 2014 - - Ayadi - and Barkallah 2016 - - Ben Lagha et all,2014 - . - Gilmore and Gomory 1965 الگوریتم branch-and-price-and-cut را ارائه دادند. - boschetti - et all, 2002
مدل ریاضی خطی جدید با حدود جدید را فراهم آوردند. - ALVAREZ,2007 - و همکاران جهت حل مسئله برش غیر گیوتینی یک الگوریتم جست و جوي ممنوعه جدید با حافظه بلند مدت ارائه دادند. در الگوریتم یادشده از دو نوع حرکت و چندین استراتژي intensification و diversification استفاده شده .آنها در نهایت به مقایسه این الگوریتم با الگوریتم ارائه شده توسط - Beasley - 2004 و الگوریتم GRASP ارائه شده توسط - ALVAREZ,2005 - پرداختند. - - BRAUDO,2004 و همکاران مسئله برش غیرگیوتینی محدود شده را ابتدا بوسیله الگوریتم ژنتیک حل کردند. آنها با سه هیوریستیک متفاوت چیدمان قطعات را انجام دادند و سپس این هیوریستیک هاي چیدمان را با هم مقایسه کردند. هدف آنها حداکثر نمودن ارزش مستطیل هایی است که روي صفحه مواد خام چیده میشوند
- MOEINI & LE THI, 2011. - روشی را بر پایه تکنیک هاي برنامه ریزي DC براي حل مسئله برش غیر گیوتینی محدود شده ارائه دادند. انها ابتدا این مسئله را بر اساس DC برنامه ریزي کرده و سپس با روش DCA مسئله را حل میکنند. انها نشان دادند که روش DCA براي حل مسئله برش غیر گیوتینی محدودشده - CONSTRAINED - عملکرد بهتري نسبت به روش CPLEX دارد.
- ANDRADE ,2012 - و همکاران مسئله برش غیر گیوتینی را بوسیله مدلهاي ریاضی چند سطحی - Multi level - انجام دادند.یکی از فرضیات در نظر گرفته شده توسط - ANDRADE ,2012 - و همکاران استفاده از باقی مانده صفحات مواد خام برش خورده میباشد. انها در نهایت نشان دادند مدل هاي چند سطحی در مسئله برش به مدل یک سطحی MIP تبدیل شوند. - - SOKE and BINGUL ,2006 از BL بهبود یافته جهت چیدن قطعات کوچکتر روي ورقه هاي مواد اولیه استفاده کردند و سپس از الگوریتم هاي ژنتیک و SA بطور جداگانه براي تولید جایگشت قطعات استفاده کردند. در نهایت به این نتیجه رسیدند که عملکرد GA بهتر از SA میباشد. - - BEASLEY,1985 الگوریتم هیوریستیک جمعیتی براي حل مسئله برش غیر گیوتینی محدودشده ارائه دادند. این الگوریتم بر پایه فرمول نویسی غیر خطی است که هدفش حداکثر نمودن کل ارزش قطعات بریده شده است BEASLEY سپس الگوریتم را بوسیله دادههایی با سایز کم و زیاد آزمایش کرد.
- DANIELS and GHANDFOROUSH ,1990 - به توسعه الگوریتمی براي حل مسائل غیر گیوتینی CONSTRAINED پرداختند. Song - - et all, 2013 براي حل مسئله برش غیرگیوتینی دو بعدي ابتدا قطعات را بوسیله الگوریتم BL می چینند سپس از الگوریتم ها PSO و AFSA براي تولید جایگشت در ترتیب چیدمان قطعات استفاده میکنند. نتایج بدست آمده حاکی از آن است که عملکرد الگوریتم AFSA بهتر از عمکرد PSO بوده است. - Prada - et all,2011 روش constructive-evolutive بر پایه تکنیک هاي متاهیوریستیک را ارائه دادند. این متد با ترکیب روش هاي هوش مصنوعی و الگوریتم ژنتیک به حل مسئله برش غیرگیوتینی میپردازد.
.2 روش تحقیق
جهت حل این مسئله الگوریتمی بر پایه ترکیب متاهیوریستیک ژنتیک و هیوریستیک Bottom Left Fill - BLF - ارائه شده است.
.2,1 الگوریتم ژنتیک
الگوریتم ژنتیک - GA - یکی از روشهاي بهینه سازي و جست و جوي جامع است که بر پایه نظریه داروین در مورد شبیهسازي انتخاب در طبیعت میباشد - Goldberg, 1989 - . از این الگوریتم براي حل مسائل بهینه سازي استفاده میشود. شناخته شده ترین عملگرهاي ژنتیک عملگرهاي جهش انتخاب و تقاطع هستند. الگوریتم ژنتیک با بهبود جمعیت فعلی در جست و جوي جواب هاي بهتر و جدید است. الگوریتم ژنتیکمعمولاً به عنوان یک شبیهساز کامپیوتر که در آن جمعیت یک نمونهي انتزاعی - کروموزومها - از نامزدهاي راهحل یک مسأله بهینهسازي به راه حل بهتري منجر شود، پیادهسازي میشوند. فرضیه با جمعیتیکاملاً تصادفی منحصر بفرد آغاز میشود و در نسلها ادامه مییابد. در هر نسل گنجایش تمام جمعیت ارزیابی میشود، چند عضو برتر از نسل جاري انتخاب میشوند - بر اساس شایستگیها - و براي شکل دادن نسل جدید، اصلاح میشوند - کسر یا دوباره ترکیب میشوند - و در تکرار بعدي الگوریتم به نسل جاري تبدیل میشود. هرعضو در جمعیت - هرکروموزوم - یک جواب براي مسئله است که کیفیت هر یک از جواب ها بوسیله تابع برازش مشخص میشود.
در ابتدا الگوریتم ژنتیک جمعیت اولیه را تولید کرده و مقدار برازندگی هر کروموزوم را بوسیله تابع برازش محاسبه میکند. تابع برازش هر مسئله مختص همان مسئله است و براي مسائل دیگر کارایی ندارد. سپس معیار بهینه سازي بررسی میشود. در صورتیکه معیار - هاي - بهینه سازي محقق شده باشد این پاسخ میتواند به عنوان بهترین پاسخ پذیرفته شود. در غیر این صورت جمعیت جدید با استفاده از عملگرهاي انتخاب، جهش و تقاطع تولید میشود. کروموزوم ها با توجه به مقدار برازندگیشان براي انجام عملگر انتخاب، انتخاب میشوند .کروموزومها با بهترین مقدار برازندگی توسط این عملگر انتخاب شده و وارد نسل بعد میشوند. سپس عملگر هاي جهش و تقاطع براي ایجاد بقیه اعضاي نسل جدید بکارگرفته میشوند . شروط خاتمه الگوریتم ژنتیک عبارتند از: -1 طی شدن تعداد تکرار مشخص از الگوریتم -2 رسیدن به جواب دلخواه
-3 طی شدن زمان از پیش تعیین شده در اجراي الگوریتم در این پژوهش هدف الگوریتم ژنتیک تعیین بهترین ترتیب چیدمان قطعات و انتخاب صفحات است .
.2,2 هیوریستیکBottom-Left-Fill
هدف مسائل برش افزایش قابلیت استفاده از صفحات مواد خام و بدست آوردن الگوي برش مناسب با حداقل ضایعات میباشد. ضایعات به ان قسمتی از صفحه مواد خام گفته میشود که از ان استفاده نشده است. روشهاي حل مسائل برش شامل دو مرحله میشوند . مرحله اول: تعیین جایگشت مناسب ترتیب قرارگیري قطعات روي صفحات مواد خام و مرحله دوم : اجراي الگوریتم چیدمان براي قرار دادن تمام قطعات روي صفحات مواد خام الگوریتم هاي چیدمانی که بیشتر از بقیه روش ها در مقالات برش مستند شدهاند عبارتند از هیوریستیک هاي BL و. BLF الگوریتم Bottom-Left-Fill - BLF - یک الگوریتم چیدمان ابتکاري شناخته شده است که با توسعه الگوریتم Bottom Left - BL - بدست آمده است. در الگوریتم BL قطعات از گوشه سمت راست و بالا تا جاي ممکن به پایین
