Co je problém dělení materiálu? Srozumitelné vysvětlení

Pokud jste někdy stáli před hromadou desek Kronospan nebo Egger se seznamem dílů v ruce a snažili se tužkou nakreslit rozložení na zadní stranu obálky, tento problém znáte. Jen jste nevěděli, že má formální název. Problém dělení materiálu (anglicky cutting stock problem) řeší jedinou otázku: jak rozřezat velké desky nebo tyče na požadované kusy tak, aby zbytků bylo co nejméně. Truhlářské dílny, výrobci nábytku i hobbyisté ho řeší každý den.

Problém, který zná každý truhlář

Představte si situaci: vyrábíte kuchyňskou linku. Potřebujete 14 bočnic, 7 polic, 7 zadních stěn a 14 dvířek — celkem 42 dílů z desek 2800×2070 mm. Každý díl má konkrétní rozměry. U některých musí vlákna běžet podélně, u jiných na směru nezáleží. Prořez pilového kotouče zabere 3 mm na každém řezu.

Zkuste teď tužkou na papír zjistit, z kolika desek všech 42 dílů vyříznete. Na první desku strávíte 20 minut mazáním a překreslováním. U třetí desky ztratíte přehled o tom, které díly už máte umístěné. A i po veškeré námaze nemáte žádnou záruku, že lepší rozložení neexistuje.

To je jádro problému dělení materiálu: máte sadu požadovaných dílů a zásobu standardních desek, a hledáte rozložení s nejmenším počtem desek a nejmenším odpadem.

Matematika za tím (zjednodušeně)

Informatici klasifikují problém dělení materiálu jako „NP-těžký.” V praxi to znamená, že počet možných rozložení roste s každým dalším dílem tak rychle, že žádný počítač nedokáže v rozumném čase otestovat všechny varianty. Při 10 dílech existují tisíce platných rozložení. Samotné pořadí, v jakém nařežete 40 dílů, dává 40 faktoriál možností — číslo o 48 číslicích — a to ještě předtím, než rozhodnete, kam přesně na desku který díl přijde a které z nich otočíte. Při 100 dílech, což je jedna kuchyňská linka, překračuje už samotný počet pořadí počet atomů v pozorovatelném vesmíru.

Jde o stejnou kategorii problémů jako bin packing (balení do kontejnerů): máte přepravky pevné velikosti a předměty různých rozměrů a chcete vše umístit s co nejmenším počtem přepravek. Algoritmy nezkoušejí každou kombinaci. Místo toho používají heuristiky — chytré zkratky jako first-fit decreasing, column generation nebo genetické algoritmy — které nacházejí téměř optimální řešení během sekund.

Formálně úlohu popsali v roce 1961 Paul Gilmore a Ralph Gomory, a nešlo přitom o dřevo. Vznikla v papírenském průmyslu, kde se ze širokých rolí řežou užší kotouče, a právě odtud pochází i metoda column generation, kterou dnes používají optimalizátory pro desky i tyče. Ten původ vysvětluje, proč klasická formulace pracuje s jedním rozměrem: dvourozměrný případ, tedy deska, přišel až později a je podstatně těžší.

Je to totéž co bin packing?

Blízcí příbuzní, ale ne totéž — a rozdíl mezi nimi je přesně to, co dělá dílenskou úlohu těžší než tu učebnicovou.

Bin packing se ptá, kolik nádob pevné velikosti stačí na danou sadu předmětů. Problém dělení materiálu se ptá, jak z materiálu dané velikosti získat požadované díly. Zní to podobně, jenže druhá formulace s sebou nese věci, které v učebnicovém bin packingu nejsou vůbec: šířku prořezu, směr, kterým řezy vedou, a otázku, jestli je stroj vůbec dokáže provést.

Právě ta poslední podmínka je v truhlářské dílně rozhodující. Formátovací i panelová pila umí jen průběžné řezy skrz celý zbývající kus, takže uspořádání, ve kterém je díl obklopený jinými díly ze všech stran, je matematicky platné a fyzicky nevyrobitelné. Řešitel, který tuhle podmínku nezná, vrátí plán s lepším číslem a horší použitelností.

Do stejné kategorie „co praxe přidává proti učebnici” patří i směr kresby, který u části dílů zakazuje otáčení, olepení hran, které mění rozměr dílu proti zadanému, a různé skladové formáty téhož dekoru. Akademická formulace pracuje s jednou velikostí materiálu a se zaměnitelnými díly. Dílenská zakázka nemá ani jedno.

Proč ruční plánování vždy plýtvá víc

Vezměme konkrétní příklad. Potřebujete 5 velkých panelů ze standardní desky Kronospan (2800×2070 mm):

• 2× bočnice: 2100×600 mm
• 2× police: 800×500 mm
• 1× zadní stěna: 2100×800 mm

Ručně většina lidí umístí největší kusy jako první a menší napasuje do mezer. Tabulka v Excelu pomůže sledovat spotřebu plochy, ale nedokáže rychle otestovat rotace ani alternativní rozložení. Optimalizační algoritmus vyhodnotí stovky variant za méně než sekundu.

Při ceně desky Egger kolem 1 200–1 800 Kč vč. DPH ušetří i jedna deska navíc na kuchyňském projektu stovky korun. Na výrobní sérii 50 kuchyní se úspory násobí do desítek tisíc.

Kde všude se problém dělení materiálu vyskytuje

Tento problém se objevuje všude, kde se řežou materiály ze standardních rozměrů:

• Truhlářství a výroba nábytku — desky Kronospan, Kaindl, Egger v desítkách rozměrů na projekt. Směr dekoru situaci ještě ztěžuje.
• CNC nesting — automatizované stroje potřebují soubor s rozložením. Optimalizátor ho vygeneruje přímo, bez ručního nestingu na ovládacím panelu stroje.
• Zpracování plechů — ocelové a hliníkové tabule stojí výrazně víc za metr čtvereční, takže i 3–5 % úspora odpadu znamená tisíce korun.
• Řezání skla a dlažby — křehké materiály, kde nesprávný řez nelze opravit. Správné rozložení na první pokus předchází drahým chybám.
• Lineární řezání (1D) — tyče, trubky, profily a řezivo. Stejný problém, o jednu dimenzi jednodušší. Stále NP-těžký při větším počtu dílů.

Jak optimalizační software problém řeší

Postup je jednodušší, než byste čekali. Zadáte požadované díly — rozměry, počty, směr vláken. Nastavíte rozměr skladové desky (nebo více rozměrů, pokud dodavatel nabízí různé formáty). Zadáte šířku prořezu pro váš kotouč, typicky 3–4 mm. A kliknete na „Optimalizovat.”

Software na pozadí spustí sérii algoritmických průchodů. Zkouší různá umístění dílů, rotace (pokud to dekor dovoluje) a uspořádání desek. Každé rozložení vyhodnotí podle celkového procenta odpadu a počtu potřebných desek. Během sekund vrátí plán řezání — vizuální mapu s přesným umístěním každého dílu na každé desce.

Dostanete tisknutelné rozložení, seznam dílů s pozicemi a jasná čísla o odpadu. Žádné hádání, žádné překreslování, žádné zapomenuté díly.

Dá se problém vyřešit přesně?

U malých zakázek ano a odpověď je pak prokazatelně nejlepší možná. S rostoucím počtem různých rozměrů se ale přesné metody stávají nepoužitelnými.

„Přesně” tu znamená, že řešitel nejen najde dobrý plán, ale zároveň dokáže, že lepší neexistuje. U několika málo různých rozměrů to zvládne — u zakázky, kde se opakuje pět typů dílů, může přesná metoda projít celý prostor možností a skončit s důkazem. Jakmile ale roste počet různých rozměrů, prostor možností roste rychleji než výkon, který mu můžete věnovat, a hledání důkazu se protáhne ze sekund na hodiny.

Výrobní nástroje proto volí jinou dohodu: rychle najít velmi dobrý plán místo pomalu najít dokonalý. Rozdíl mezi oběma výsledky bývá malý, kdežto rozdíl v čase je propastný — a v dílně, kde se plán počítá znovu po každé změně rozměru, je použitelnost důležitější než dokazatelná optimalita.

S tím souvisí otázka, kterou si klade skoro každý: nedal by delší výpočet lepší plán? Do určitého bodu ano, dál už na tom nezáleží. Většina zisku přijde brzy a další hledání obvykle jen potvrzuje, že stávající plán se těžko překonává. Rychlá odpověď proto bývá důvodem, proč zakázka plýtvá materiálem, jen výjimečně — mnohem častěji za to může špatně zadaný rozměr desky, chybějící prořez nebo zbytečně vynucený směr kresby.

Praktický dopad na vaši dílnu

Rozdíl mezi ručním a softwarovým plánováním se projevuje okamžitě. Truhlář, který denně řeže 10–15 desek, může při 10% snížení odpadu ušetřit 1–2 desky denně. Za měsíc to představuje materiál v hodnotě tisíců korun.

Další přínos je čas. Ruční plánování složitějšího projektu zabere 30–60 minut. Software to zvládne za sekundy. Uvolněný čas můžete věnovat samotné práci u stroje.