Tối ưu bảng cắt

Công cụ dùng first-fit decreasing (xếp vào chỗ đầu tiên vừa, theo thứ tự giảm dần), quy tắc kinh điển cho bài toán cắt một chiều. Mỗi thanh được trải ra riêng, sắp xếp từ dài nhất đến ngắn nhất, rồi đặt vào tấm đầu tiên còn đủ chỗ. Chỉ khi không tấm nào nhận được thanh đó thì mới mở một tấm mới. Bắt đầu từ các thanh dài là có lý do: chúng khó xếp nhất, còn các thanh ngắn sẽ lấp vào khoảng trống chúng để lại.

First-fit decreasing là một phương pháp heuristic nhanh. Nó thường cho số tấm tối thiểu hoặc rất gần mức đó, nhưng không đảm bảo là tối ưu toán học với mọi danh sách. Nếu kế hoạch kết thúc bằng một tấm gần như không dùng đến, hãy thử cùng danh sách với chiều dài vật liệu hơi khác, hoặc kiểm tra xem hoán đổi tay hai thanh có tiết kiệm được một tấm không.

Mạch cưa được tính như thế nào

Mỗi đường cắt tách hai thanh sẽ lấy đi một độ dày lưỡi cưa. Công cụ tính mạch cưa giữa các thanh liền kề trên một tấm, nên tấm chứa n thanh phải trả cho n - 1 đường cắt. Khi còn vật liệu sau thanh cuối, cần thêm một đường cắt nữa để tách thanh với phần thừa, và đường cắt đó được trừ vào phần thừa. Tấm được lấp đầy chính xác đến đầu mút thì không cần đường cắt cuối.

Ví dụ tính toán

Tấm gỗ dài 96, mạch cưa 0,125 và các thanh 40 x 2, 30 x 3 và 20 x 1:

Kết quả là 3 tấm, 288 vật liệu cho 190 chiều dài thanh, tức hao hụt 98 (phần thừa cộng mạch cưa), khoảng 34%. Tấm thứ ba gần như trống, cho thấy danh sách này phù hợp với vật liệu ngắn hơn hoặc phần thừa dài có thể dùng cho việc khác.

Mẹo để bảng cắt tiết kiệm hơn

• Đo mạch cưa thực tế của lưỡi cưa. Lưỡi mỏng lấy đi khoảng 2 đến 2,5 mm (khoảng 3/32 inch), lưỡi cưa bàn tiêu chuẩn lấy đi khoảng 3 mm (1/8 inch).
• Cộng thêm vài milimét cho những thanh sẽ được bào, chà nhám hoặc cắt vuông lại sau khi cắt.
• Giữ lại phần thừa đủ dài cho một thanh sau này. Cột phần thừa cho biết mỗi tấm để lại những gì.
• Mua chiều dài vật liệu ít hao hụt nhất. Chạy cùng danh sách với từng chiều dài nhà cung cấp bán và so sánh số tấm cũng như tỷ lệ hao hụt.