Problém řezání zásob vysvětlený prostě
Co je problém řezání zásob, proč je NP-těžký a jak 1D a 2D optimalizátory (gilotinové řezy versus volné uspořádání) najdou dobrá řešení rychle.
Co je problém řezání zásob?
Máte dodací délky (pruty, prkna, desky) a seznam požadovaných kusů; vyřežte všechny kusy z co nejmenšího množství materiálu. Zní to triviálně; matematicky je to NP-těžký problém — počet kombinací exploduje s rostoucím seznamem kusů.
1D, 2D a gilotinové řezy
1D znamená jeden rozměr: trubky, profily, laťky. 2D přidává šířku — překližka, sklo, plech. Gilotinové řezy jdou od hrany ke hraně (co dělá formátovací pila); volné uspořádání dovolí libovolnou rotaci a negilotinová rozvržení (co dělají lasery a frézky).
Proč jsou přesná řešení vzácná
Přesně se řeší jen malé případy (dynamické nebo celočíselné programování). Praxe spoléhá na heuristiky — First Fit Decreasing, Best Fit Decreasing, algoritmy polic — které obvykle skončí v řádu pár procent od optima během milisekund.
Šířka řezu a další reálné pasti
Každý řez spotřebuje materiál: list 3 mm přidá 3 mm na řez a 50 řezů potichu sežere 150 mm materiálu. Znovupoužití zbytků, směr vláken a ztráty na ořez hran hrají stejnou roli jako samotné skládání.
Zkuste to na vlastním seznamu řezů
Kalkulačka Kalkulačka řezání na délku optimalizuje seznamy prutů a profilů; kalkulačka Kalkulačka řezání desek zvládá gilotinová rozvržení desek s rotací a šířkou řezu. Vložte svůj seznam a porovnejte celkovou spotřebu materiálu před a po.
Kalkulačka řezání na délku Otevřít kalkulačku řezání na délku