Tối ưu cắt phôi 1D

Tối ưu hóa cắt phôi 1D hoạt động như thế nào

Bài toán cắt phôi một chiều đặt câu hỏi: làm sao cắt các chi tiết yêu cầu từ phôi có chiều dài tiêu chuẩn (thanh, ống, thép hình, nhôm định hình) với số phôi ít nhất có thể. Đây là bài toán NP-hard, nên các công cụ thực tế dùng heuristic nhanh, cho kết quả rất gần tối ưu với các danh sách đơn hàng xưởng thông thường.

First Fit Decreasing (FFD) sắp xếp tất cả chi tiết từ dài nhất đến ngắn nhất, rồi đặt từng chi tiết vào phôi đầu tiên còn chỗ; nếu không phôi nào vừa, mở một phôi mới. Best Fit Decreasing (BFD) cũng sắp xếp giảm dần nhưng đặt mỗi chi tiết vào phôi sao cho khoảng trống còn lại sau đó là nhỏ nhất, nhờ vậy có thể xếp các tổ hợp khít hơn một chút với một số cơ cấu đơn hàng.

Mỗi nhát cắt tiêu hao vật liệu bằng đúng bề rộng mạch cưa. Công cụ này áp dụng mạch cưa giữa các chi tiết liên tiếp trên cùng một phôi (n chi tiết cần n − 1 nhát cắt), nên phần phế liệu báo cáo tách riêng đầu mẩu cuối thanh thật sự khỏi hao hụt mạch cưa. Với FFD, lý thuyết bảo đảm kết quả không bao giờ vượt quá 11/9 × tối ưu + 6/9 phôi (Dósa, 2007) — trong thực tế kết quả thường là tối ưu hoặc chỉ hơn tối ưu một phôi.

Khi nào nên dùng công cụ này

• Cắt danh sách đơn hàng thép cây, thép kết cấu, ống hoặc nhôm định hình từ phôi tiêu chuẩn 6 m hoặc 12 m
• Ước tính số thanh phôi cần mua cho một công việc gia công trước khi đặt vật tư
• So sánh phế liệu giữa hai chiều dài phôi mà nhà cung cấp chào để chọn phương án rẻ hơn
• Lập phiếu trình tự cắt cho thợ vận hành máy cưa với các chi tiết được gắn nhãn theo từng thanh
• Định lượng hao hụt mạch cưa tách riêng khỏi phế liệu đầu mẩu khi cần luận chứng cho lưỡi cưa mỏng hơn

Những sai lầm thường gặp cần tránh

• Bỏ qua mạch cưa — trên thanh 6 m cắt thành 20 chi tiết, mạch cưa 3 mm tiêu hao ~57 mm, có thể đẩy chi tiết cuối sang một thanh mới
• Lẫn lộn đơn vị giữa chiều dài phôi và danh sách chi tiết (nhập phôi theo mét nhưng chi tiết theo milimét)
• Nhập tổng số chi tiết gộp cho nhiều cụm lắp thay vì dùng cột số lượng, khiến danh sách đơn hàng khó kiểm tra
• Coi kết quả heuristic là tối ưu được bảo đảm cho các ngân sách vật liệu quan trọng về an toàn — với các lô sản xuất công nghiệp lớn, phương pháp LP sinh cột (column generation) có thể tiết kiệm thêm vài phôi
• Quên rằng các đoạn dư còn dùng được (đầu mẩu dài) ở đây vẫn tính là phế liệu — nếu bạn lưu kho đoạn dư để tái sử dụng, hãy trừ chúng khỏi phế liệu báo cáo

Cách diễn giải kết quả

• Phôi sử dụng là con số quan trọng nhất — hãy so sánh với cận dưới ⌈tổng chiều dài chi tiết ÷ chiều dài phôi⌉ để đánh giá độ chặt của sơ đồ cắt
• Hiệu suất sử dụng trên ~90% là tốt với danh sách đơn hàng hỗn hợp; trên 95% là xuất sắc và thường có nghĩa các chiều dài chi tiết kết hợp tốt với chiều dài phôi
• Phế liệu theo từng mẫu cho thấy thanh nào mang đầu mẩu — một thanh duy nhất chứa phần lớn phế liệu thường để lại một đoạn dư còn dùng được
• Hao hụt mạch cưa tăng theo số lượng chi tiết, không phải chiều dài chi tiết — nhiều chi tiết ngắn mất tỷ lệ vật liệu vào lưỡi cưa cao hơn
• Nếu FFD và BFD cho cùng số phôi, sơ đồ cắt gần như chắc chắn là tối ưu cho chiều dài phôi đó; nếu khác nhau, hãy lấy phương án tốt hơn

Tiêu chuẩn & tài liệu tham khảo liên quan

• Gilmore & Gomory (1961) — A Linear Programming Approach to the Cutting-Stock Problem (Operations Research 9:849-859), phương pháp chính xác nền tảng
• Dósa (2007) — cận trên trường hợp xấu nhất chặt cho First Fit Decreasing: FFD(I) ≤ 11/9·OPT(I) + 6/9
• Johnson (1973) — Near-optimal bin packing algorithms (MIT), phân tích kinh điển về họ heuristic FFD/BFD
• Chiều dài phôi thương mại thường theo thanh cán 6000 mm và 12000 mm cho thép cây và thép hình kết cấu; hãy kiểm tra danh mục của nhà cung cấp trước khi tối ưu

Câu hỏi thường gặp

Nên chọn FFD hay BFD?

Cả hai đều sắp xếp chi tiết dài nhất trước và chỉ khác nhau ở cách chọn phôi: FFD lấy phôi đầu tiên còn chỗ, BFD lấy phôi vừa khít nhất. Hai thuật toán thường cho cùng số phôi; khi khác nhau, chênh lệch là một phôi. Hãy chạy cả hai (một cú nhấp) và giữ sơ đồ tốt hơn.

Mạch cưa được áp dụng như thế nào?

Mạch cưa được cộng giữa các chi tiết liên tiếp trên cùng một phôi — n chi tiết cần n − 1 nhát cắt, đoạn dư cuối không cần nhát cắt thêm. Hãy đặt mạch cưa bằng bề rộng lưỡi cưa hoặc mỏ cắt thực tế của bạn (thường 2-4 mm với cưa nguội, 1-2 mm với cưa vòng).

Kết quả có thể kém hơn tối ưu thực sự không?

Có, nhưng với biên độ nhỏ được chứng minh: FFD không bao giờ cần quá 11/9 số phôi tối ưu cộng một hằng số. Với danh sách đơn hàng quy mô xưởng, kết quả gần như luôn tối ưu; với các lô quy mô nhà máy hàng nghìn chi tiết, bộ giải chính xác bằng sinh cột đôi khi có thể tiết kiệm thêm phôi.