بهینه‌سازی الگوی برش ورق برای کاهش پرت و ضایعات

در بسیاری از کارخانه‌ها و کارگاه‌ها، ورق‌های فلزی یا چوبی برش داده می‌شوند تا قطعات مختلف ساخته شوند. اگر الگوی برش درست انتخاب نشود، بخش زیادی از ورق تبدیل به ضایعات می‌شود. در این مقاله روش‌های مختلف برای پیدا کردن بهترین الگوهای برش و کاهش پرت ورق توضیح داده می‌شود.

۱. مقدمه

وقتی ورق بزرگ را به قطعات کوچکتر تقسیم می‌کنیم، همیشه بین قطعات فاصله‌هایی باقی می‌ماند که آن‌ها را نمی‌توان استفاده کرد. این بخش‌های اضافه، ضایعات یا پرت نامیده می‌شوند. ضایعات تنها هدررفت مواد نیست، بلکه هزینهٔ بازیافت و دورریز را هم به دنبال دارد. هدف ما این است که به کمک روش‌های هوشمندانه، الگوهایی پیدا کنیم که کمترین فاصلهٔ خالی و بیشترین قطعات لازم را در برش ورق فراهم کنند.

۲. مدل سادهٔ مسأله

تصور کنید ورق‌هایی با طول ثابت (مثلاً ۲ متر) داریم و باید از آن‌ها قطعاتی با طول‌های مختلف (مثلاً ۰.۵ متر، ۰.۷ متر و ۱.۲ متر) بسازیم. به‌ازای هر نوع قطعه یک تعداد مشخص (مثلاً ۱۰ عدد از ۰.۵ متری، ۵ عدد از ۰.۷ متری و …) نیاز داریم.

• الگوی برش یعنی یک راه چیدن قطعات روی ورق: مثلاً دو قطعه ۰.۵ متری و یک قطعه ۱.۲ متری روی یک ورق جا می‌شوند.

• پرت ورق یعنی فاصلهٔ خالی که پس از قرار دادن آن قطعات روی ورق باقی می‌ماند.

ما می‌خواهیم هردفعه الگوهایی انتخاب کنیم که مجموع فاصله‌های خالی (پرت) کم شود و بتوانیم نیاز همهٔ قطعات را با کمترین تعداد ورق برآورده کنیم.

۳. روش‌های حل مسأله

۳.۱ روش ستون‌زنی (Column Generation)

1. ابتدا تعدادی الگوی ساده انتخاب می‌کنیم و مسئله را با آن‌ها حل می‌کنیم.

2. سپس به کمک یک الگوریتم داخلی، بررسی می‌کنیم که آیا می‌توان الگوی جدیدی پیدا کرد که کم‌تر ورق مصرف کند یا نه.

3. اگر بتوانیم الگوی بهتری بیابیم، آن را اضافه و دوباره مسئله را حل می‌کنیم.

4. تا وقتی الگویی پیدا نشود که ورق مصرفی را کاهش دهد، ادامه می‌دهیم.

این روش دقت بالایی دارد ولی ممکن است برای تعداد زیاد قطعه یا الگو زمان‌بر باشد.

۳.۲ روش‌های سریع (Heuristics)

این روش‌ها بسیار ساده و سریع‌اند ولی همیشه دقیق‌ترین جواب را نمی‌دهند:

• First Fit Decreasing (FFD):

  1. طول قطعات را از بزرگ به کوچک مرتب می‌کنیم.

  2. هر قطعه را در اولین ورقی که جا دارد قرار می‌دهیم.

• Best Fit Decreasing (BFD):

  1. مانند FFD ابتدا مرتب‌سازی.

  2. هر قطعه را در آن ورقی می‌گذاریم که کم‌ترین فضای خالی پس از قرارگیری باقی بگذارد.

این روش‌ها سریع اجرا می‌شوند و برای مسأله‌های متوسط مناسب‌اند، اما گاهی به جواب بهینه نمی‌رسند.

۳.۳ روش‌های پیشرفته (Metaheuristics)

این روش‌ها با الهام از فرآیندهای طبیعی یا تکاملی کار می‌کنند تا از جواب‌های ضعیف خارج شوند:

• الگوریتم ژنتیک:

  • چندین الگو (مانند مجموعه‌ای از کروموزوم) تولید می‌کند.

  • با ترکیب و تغییر آن‌ها به نسل‌های بعدی می‌رسد.

  • بهترین جواب‌ها را نگه می‌دارد تا کم کم به الگوی بهینه نزدیک شود.

• شبیه‌سازی تبرید (Simulated Annealing):

  • با دیدن یک جواب اولیه شروع می‌کند.

  • به صورت تصادفی تغییراتی ایجاد می‌کند و گاهی حتی تغییرات بد را هم می‌پذیرد.

  • رفته‌رفته احتمال پذیرش تغییرات بد را کم می‌کند تا در جواب‌های بهتری متوقف شود.

این روش‌ها معمولاً زمان بیشتری می‌گیرند اما می‌توانند به جواب‌های نزدیک به بهینه برسند.

۴. مقایسه روش‌ها

• ستونی: دقیق و نزدیک به جواب بهینه، اما برای مسائل بزرگ سنگین است.

• FFD/BFD: خیلی سریع، ساده در پیاده‌سازی، کیفیت مناسب برای حجم متوسط.

• ژنتیک/تبرید: تعادل خوبی بین سرعت و کیفیت؛ مخصوصاً وقتی زمان اجرا اهمیت کمتری داشته باشد.

۵. نتیجه‌گیری

اگر تعداد و تنوع قطعات کم تا متوسط باشد، روش‌های ساده مثل FFD یا BFD کفایت می‌کنند.
چنان‌چه دقت بالا مهم باشد و منابع محاسباتی کافی دارید، روش ستون‌زنی بهترین انتخاب است.
در مواردی که هم می‌خواهیم دقت بالا و هم زمان نسبتاً مناسب داشته باشیم، ترکیب الگوریتم ستون‌زنی با یک روش متاهیوریستیک (مثلاً ژنتیک) پیشنهاد می‌شود. این ترکیب کمک می‌کند ابتدا جواب دقیق پیوسته را پیدا کنیم و سپس با یک جست‌وجوی محلی سریع جواب را بهتر و نزدیک‌تر به حالت صحیح کنیم.