For developers
Problém jednorozměrného dělení materiálu
Jak nařezat sadu požadovaných délek ze skladových tyčí s použitím co nejmenšího počtu tyčí je problém jednorozměrného dělení materiálu: klasický, skutečně těžký optimalizační problém. Zde je vysvětleno, co to je, proč odolává hrubé síle a jak se řeší v praxi, včetně API, které pohání tuto stránku.
Co je problém jednorozměrného dělení materiálu
Máte dané skladové kusy o pevné délce (např. 6000 mm tyče) a seznam požadovaných dílů, každý s délkou a množstvím. Řezný vzor je jeden způsob, jak nařezat jednu skladovou tyč na několik těchto dílů; jakákoli zbývající délka je odpad. Problémem je vybrat řezné vzory a počet tyčí pro každý z nich tak, aby byl vyroben každý požadovaný díl a celkový počet skladových tyčí, a tedy i celkový odpad, byl co nejmenší. Jeden rozměr, protože záleží pouze na délce: řez prochází celým průřezem, takže šířka a profil do skládání nevstupují.
Jednorozměrné skládání do kontejnerů a proč je NP-těžké
Problém dělení materiálu je zobecněním problému jednorozměrného skládání do kontejnerů: skládání do kontejnerů vyžaduje naskládat sadu různě velkých položek do co nejmenšího počtu kontejnerů o pevné velikosti. Dělení materiálu je stejná otázka, jakmile se položky opakují ve velkém množství, takže uvažujete o vzorech spíše než o jednotlivých kusech. Skládání do kontejnerů je jedním z klasických NP-těžkých problémů a jeho rozhodovací forma, 'vejdou se tyto položky do k kontejnerů', je NP-úplná. Problém dělení materiálu tuto obtížnost dědí.
Důvodem je kombinatorická exploze. Počet odlišných řezných vzorů roste exponenciálně s počtem velikostí dílů a počet způsobů, jak rozdělit množství mezi tyto vzory, exploduje navrch. Neexistuje žádný známý algoritmus, který by našel zaručené optimum v čase, který by se škáloval polynomiálně se vstupem, a pokud se P nerovná NP, žádný takový nebude. Skutečné řešiče tedy nevyjmenovávají všechno; chytře vylučují možnosti, které mohou.
Jak se to řeší v praxi
Heuristika First-Fit-Decreasing (FFD)
Pracovní heuristika: seřaďte požadované díly od nejdelšího po nejkratší, poté každý umístěte na první tyč, kam se ještě vejde, a novou tyč otevřete, až když na žádné není místo. Je rychlá a překvapivě dobrá, prokazatelně v rozmezí přibližně 11/9 optimálního počtu tyčí plus malá konstanta. Většina nástrojů zde končí; dobrý nástroj používá FFD jako výchozí bod, ne jako cíl.
Generování sloupců (Gilmore a Gomory)
Formulace, která umožnila řešit i velké úlohy. Gilmore a Gomory (1961) popsali problém s jednou proměnnou pro každý nářezový plán, a protože jich je exponenciálně mnoho, vyřešili lineární relaxaci generováním sloupců se zpožděním: začali s několika málo plány a opakovaně generovali další nejužitečnější plán řešením dílčího problému batohu s omezením. Dolní mez, kterou tato metoda poskytuje, je pověstně těsná.
Metoda větví a mezí a metoda větví a cen
Aby se z této zlomkové relaxace stal celý počet tyčí, je třeba hledat, ale ne naslepo. Metoda větví a mezí prozkoumává strom celočíselných voleb a pomocí LP meze ořezává celé větve, které nemohou překonat dosud nejlepší nalezený plán. V kombinaci s generováním sloupců se z ní stává metoda větví a cen, která je základem většiny přesných řešičů pro nářezové plány.
Dolní meze a důkaz
Seriózní řešič nevrací jen plán. Spočítá dolní mez (z LP relaxace nebo z jednoduššího argumentu celkové délky) a porovná ji. Když plán použije přesně tolik tyčí, kolik je podle meze nevyhnutelné, je prokazatelně optimální: žádný plán nemůže být lepší a řešič to může konstatovat, místo aby jen doufal, že měl štěstí.
Jak to řeší LinearCutting
LinearCutting používá tuto sadu metod: rychlou heuristiku pro okamžitý proveditelný plán, poté hledání řízené mezí, které se zlepšuje, dokud buď nedosáhne dolní meze (prokazatelně optimální, a řekne vám to), nebo nevyčerpá časový limit a nevrátí nejlepší nalezený plán. Modeluje i fyzikální realitu: prořez u každého řezu, začištění konců, odřezky s pevnou délkou a šikmé řezy, které spotřebují více materiálu. Plán, který ignoruje pilový kotouč, není jen neoptimální, je špatný. Srovnávací úlohy jsou zveřejněny, abyste si mohli výsledky ověřit s jakýmkoli jiným nástrojem.
Je k dispozici jako JSON API: pošlete své díly a materiál a získáte zpět ověřený nářezový plán s rozložením, odpadem, počtem nastavení a informací, zda plán dosáhl optimální meze. Existují oficiální klienti pro Python (pip install linearcutting) a JavaScript nebo TypeScript (npm install linearcutting), takže volání je otázkou několika řádků v obou jazycích.
Řešte to ze svého kódu
Nepište vlastní řešič, zavolejte si hotový. Stejný engine, který pohání kalkulačku na tomto webu, je JSON API s oficiálními klienty pro Python a JavaScript, s bezplatnou úrovní pro veřejnost a s živým příkladem, který si můžete spustit v dokumentaci.
pip install linearcutting npm install linearcutting