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

در این مقاله مسئله برش دو بعدی۱ با تقاضا، مورد بررسی قرار می گیرد. در این مسئله باید با برش ورقهای مستطیل شکل بزرگ، مستطیلهای کوچکتر مورد نیاز به نحوی تولید شوند که ضمن تامین تقاضاهای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شد. حل این مسئله در هر صنعتی که برش صفحات در آن مورد نیاز باشد از نظر کاهش ضایعات حائز اهمیت خواهد بود. در اکثر مقالات، تقاضای قطعات در نظر گرفته نشده و تنها به مسئله حداقل کردن ضایعات در یک ورق پرداخته شده است. مسئله برش جزء مسائل Np-hard بوده و روشهای دقیق قادر به حل عملی آن نخواهند بود، لذا الگوریتمی فراابتکاری۲ با استفاده از روشSA ۳برای حل مستقیم مسئله برش با تقاضا، ارائه شده است. در این الگوریتم جواب اولیه با رویه ای قانون گرا ایجاد شده و از یک SA داخلی، در فرایند تولید جواب همسایگی در هر تکرار حلقه SA اصلی استفاده شده است این امر موجب کارایی مناسب الگوریتم شده است. به دلیل وجود نداشتن مسائل نمونه به اندازه کافی، روشی برای تولید مسائل تصادفی برش با تقاضا ارائه شده است و به این ترتیب مسائلی در محدوده ۱۰ تا۵۰ نوع قطعه و با تقاضای کل حداکثر ۲۴۰۰ تولید و توسط الگوریتم حل شده است. نتایج محاسباتی نشان دهنده قابل قبول بودن الگوریتم است. این الگوریتم توانسته است برای مسائلی با۳۰ نوع قطعه و تقاضای کل ۵۰۰ جوابی با ضایعات کمتر از ۶ درصد را بیابد

Keywords:

Two dimensional cutting stock problem , Waste , Cutting patterns , Simulated annealing , مسئله برش دو بعدی , ضایعات , سبک برش , روشSA