ارائه الگوریتمی برای مسئله برش دوبعدی با تقاضا

این مقاله مسئله برش دو بعدی با تقاضا، مورد بررسی قرار می گیرد . در این مسئله باید با برش ورق های مستطیل شکل بزرگ، مستطیل های کوچکتر مورد نیاز به نحوی تولید شوند که ضمن تامین تقاضاهای آنها ضایعات یا تعداد ورق های مصرفی حداقل گردد . حل این مسئله در هر صنعتی که برش صفحات در آن مورد نیاز باشد از نظر کاهش ضایعات حائز اهمیت خواهد بود . در اکثر مقالات، تقاضای قطعات در نظر گرفته نشده و تنها به مسئله حداقل کردن ضایعات در یک ورق پرداخته شده است . مسئله برش جزء مسائل Np-hard بوده و روش های دقیق قادر به حل عملی آن نخواهند بود، لذا الگوریتمی فراابتکاری با استفاده از روش SA برای حل مستقیم مسئله برش با تقاضا ارائه شده است . در این الگوریتم جواب اولیه با رویه ای قانون گرا ایجاد شده و از یک SA داخلی ، در فرآیند تولید جواب همسایگی در هر تکرار حلقه SA اصلی استفاده شده است این امر موجب کارایی مناسب الگوریتم گردیده است . به دلیل وجود نداشتن مسائل نمونه به اندازه کافی ، روشی برای تولید مسائل تصادفی برش با تقاضا ارائه شده است وبه این ترتیب مسائلی در محدوده ١٠ تا٥٠ نوع قطعه و با تقاضای کل حداکثر ٢٤٠٠ تولید و توسط الگوریتم حل شده است . نتایج محاسباتی نشان دهنده قابل قبول بودن الگوریتم می باشد؛ این الگوریتم توانسته است برای مسائلی با٣٠ نوع قطعه و تقاضای کل ٥٠٠، جوابی با ضایعات کمتر از ٦درصد را بیابد .

Keywords:

مسئله برش دو بعدی , ضایعات , سبک برش , روش SA