Thuật toán hiệu quả để lồng chiều dài 1 chiều vào chiều dài kho được xác định trước là gì?Thuật toán lồng nhau 1 chiều
Ví dụ, Nếu bạn cần thanh thép trong số lượng và độ dài sau,
- 5 x 2 mét
- 5 x 3 mét
- 5 x 4 mét
và chúng có thể được cắt từ các thanh 10 mét. Làm thế nào bạn có thể tính toán mẫu cắt các thanh 10m để số lượng thanh tối thiểu được sử dụng?
Ngoài ra, làm cách nào bạn có thể kết hợp nhiều độ dài cổ phiếu vào thuật toán?
Tôi đã có một chút thời gian để giải quyết vấn đề này vì vậy tôi sẽ viết lên cách tôi đã giải quyết. Tôi hy vọng điều này sẽ hữu ích cho ai đó. Tôi không chắc chắn nếu nó là ok để trả lời câu hỏi của riêng tôi như thế này. Người kiểm duyệt có thể thay đổi điều này thành câu trả lời nếu điều đó phù hợp hơn.
Cảm ơn mọi người đã trả lời. Điều này đã chỉ cho tôi thuật toán thích hợp; the cutting stock problem.
Bài đăng này cũng hữu ích; "Calculating a cutting list with the least amount of off cut waste".
Ok, vào giải pháp.
Tôi sẽ sử dụng thuật ngữ sau trong giải pháp của mình;
- Cổ: chiều dài của vật liệu sẽ được cắt thành từng miếng nhỏ
- Cut: chiều dài vật liệu đã được cắt từ cổ phiếu. nhiều vết cắt có thể được lấy từ cùng một mảnh chứng khoán
- Chất thải: chiều dài của vật liệu còn lại trong một phần của cổ phiếu sau khi tất cả các vết cắt đã được thực hiện.
Có ba giai đoạn chính để giải quyết vấn đề,
- Xác định tất cả kết hợp cắt có thể
- Xác định kết hợp có thể được lấy từ mỗi phần chứng khoán
- Tìm sự pha trộn tối ưu cắt kết hợp.
Bước 1
Với vết cắt N, có 2^N-1 độc đáo kết hợp cắt. Các kết hợp này có thể được biểu diễn dưới dạng bảng chân lý nhị phân.
Trong đó A, B, C là các vết cắt độc đáo;
A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC
Có thể sử dụng vòng lặp cho một số toán tử bitwise để tạo nhanh nhóm của từng tổ hợp cắt.
Điều này có thể tốn khá nhiều thời gian cho các giá trị lớn của N.
Trong trường hợp của tôi có nhiều trường hợp cùng một lần cắt. Điều này tạo ra các kết hợp trùng lặp.
A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB
Tôi đã có thể khai thác dự phòng này để giảm thời gian tính kết hợp. Tôi đã nhóm các lần cắt trùng lặp lại với nhau và tính các kết hợp độc đáo của nhóm này. Sau đó, tôi nối thêm danh sách kết hợp này vào từng kết hợp duy nhất trong nhóm thứ hai để tạo nhóm mới.
Ví dụ, với các vết cắt AABBC, quy trình như sau.
A A | Combination
-------------------
0 1 | A
1 1 | AA
Gọi nhóm này X.
Nối X để hợp độc đáo của B,
B B X | Combination
-------------------
0 0 1 | A
| AA
0 1 0 | B
0 1 1 | BA
| BAA
1 1 0 | BB
1 1 1 | BBA
| BBAA
Gọi nhóm này Y.
Nối Y để trường hợp duy nhất của C,
C Y | Combination
-----------------
0 1 | A
| AA
| B
| BA
| BAA
| BB
| BBA
| BBAA
1 0 | C
1 1 | CA
| CAA
| CB
| CBA
| CBAA
| CBB
| CBBA
| CBBAA
This examp le tạo 17 kết hợp duy nhất thay vì 31 (2^5-1). Tiết kiệm gần một nửa.
Sau khi tất cả các kết hợp được xác định, đã đến lúc kiểm tra xem điều này phù hợp với cổ phiếu như thế nào.
Bước 2
Mục đích của bước này là để lập bản đồ kết hợp cắt được xác định trong bước 1 để kích thước cổ phiếu có sẵn.
Đây là một quá trình tương đối đơn giản. Đối với mỗi kết hợp cắt,
calculate the sum of all cut lengths.
for each item of stock,
if the sum of cuts is less than stock length,
store stock, cut combination and waste in a data structure.
Add this structure to a list of some sort.
Điều này sẽ dẫn đến danh sách kết hợp cắt lồng hợp lệ. Nó không phải là cần thiết để lưu trữ các chất thải vì điều này có thể được tính toán từ độ dài cắt và chiều dài cổ phiếu. Tuy nhiên, lưu trữ chất thải giảm xử lý yêu cầu trong bước 3.
Bước 3
Trong bước này, chúng ta sẽ xác định sự kết hợp của việc cắt giảm sản xuất các chất thải ít nhất. Điều này dựa trên danh sách các tổ hợp lệ được tạo ở bước 2.
Trong một thế giới lý tưởng, chúng tôi sẽ tính toán tất cả các khả năng và chọn khả năng tốt nhất. Đối với bất kỳ bộ cắt giảm không tầm thường nào, sẽ mất mãi mãi để tính toán tất cả. Chúng ta sẽ chỉ phải hài lòng với một giải pháp không tối ưu. Có nhiều thuật toán khác nhau để hoàn thành nhiệm vụ này.
Tôi đã chọn phương pháp sẽ tìm kiếm tổ có chất thải ít nhất. Nó sẽ lặp lại điều này cho đến khi tất cả các vết cắt đã được tính toán.
Bắt đầu với ba danh sách
- cutList: một danh sách của tất cả các vết cắt cần thiết (bao gồm cả bản sao).
- nestList: Danh sách tổ được tạo ở bước 2. Điều này được sắp xếp từ chất thải thấp nhất đến chất thải cao nhất.
- finalList: Ban đầu trống, điều này sẽ lưu trữ danh sách các kết hợp cắt sẽ được xuất ra cho người dùng.
Phương pháp
pick nest from nestList with the least waste
if EVERY cut in the nest is contained in cutList
remove cuts from cutList
copy this nest into the finalList
if some cuts in nest not in cutList
remove this nest from nestList
repeat until cutlist is empty
Với phương pháp này, tôi quản lý để có được một sự lãng phí tổng cộng khoảng 2-4% đối với một số dữ liệu thử nghiệm điển hình. Hy vọng rằng tôi sẽ xem xét lại vấn đề này tại một số điểm và thực hiện thuật toán Delayed column generation. Điều này sẽ cho kết quả tốt hơn.
Tôi hy vọng điều này sẽ giúp bất kỳ ai khác gặp sự cố này.
David
Điều này đọc rất nhiều khủng khiếp như một câu hỏi về bài tập về nhà ... –
có thể nó không phải là bài tập về nhà - điều này rất giống với một vấn đề công nghiệp thực tế tôi đã viết một chương trình cho khoảng năm 1990 – DarenW
. Đó là kết quả có thể xem tại http://wood-cut.rhcloud.com. Nó không đưa ra giải pháp tối ưu, vì nó sẽ đòi hỏi một cách tiếp cận liệt kê nhưng đưa ra một giải pháp có thể chấp nhận được. Tôi đã thấy một số phần mềm cung cấp điều này với chi phí nhiều hơn $ 50 và sử dụng thuật toán di truyền, và không đảm bảo giải pháp tối ưu, đôi khi thậm chí cung cấp cho kết quả nghèo hơn http://wood-cut.rhcloud.com. Tôi đang làm việc để tối ưu hóa trang web của mình và sẽ viết thuật toán đó khi tôi có thời gian. –