Cutting Stock Problem, Dijelaskan Sederhana
Apa itu cutting stock problem, kenapa ia NP-hard, dan bagaimana optimizer 1D dan 2D (guillotine vs nesting sejati) menemukan solusi bagus dengan cepat.
Apa itu cutting stock problem?
Diberikan panjang bahan baku (batang, papan, lembaran) dan daftar keping yang diminta, potong semua keping dari bahan sesedikit mungkin. Kedengarannya sepele; secara matematis ini NP-hard — jumlah kombinasinya meledak seiring panjangnya daftar keping.
1D, 2D, dan potongan guillotine
1D berarti satu dimensi: pipa, profil, stud. 2D menambah lebar — triplek, kaca, plat logam. Potongan guillotine berjalan dari tepi ke tepi (yang dilakukan panel saw); nesting sejati mengizinkan rotasi bebas dan penataan non-guillotine (yang dilakukan laser dan router).
Kenapa solusi eksak jarang dipakai
Hanya instance kecil yang bisa diselesaikan secara eksak (pemrograman dinamis atau bilangan bulat). Industri mengandalkan heuristik — First Fit Decreasing, Best Fit Decreasing, algoritma shelf — yang biasanya mendarat dalam beberapa persen dari optimum dalam hitungan milidetik.
Kerf dan jebakan dunia nyata lainnya
Setiap potongan memakan material: kerf mata gergaji 3 mm menambah 3 mm per potongan, dan 50 potongan diam-diam memakan 150 mm bahan baku. Pemakaian ulang potongan sisa, arah serat, dan kehilangan trim sama pentingnya dengan penataannya sendiri.
Coba pada daftar potong Anda sendiri
Kalkulator pemotongan linear mengoptimalkan daftar batang dan profil; Kalkulator pemotongan lembaran menangani penataan lembaran guillotine dengan rotasi dan kerf. Tempel daftar Anda dan bandingkan total bahan sebelum dan sesudah.
Kalkulator pemotongan linear Buka kalkulator pemotongan linear