For developers
Az 1D szabási probléma
Hogyan lehet egy adott vágási listát a lehető legkevesebb szálanyagból levágni, ez a 1D szabási probléma: egy klasszikus, valóban nehéz optimalizálási feladat. Itt elmagyarázzuk, mi ez, miért áll ellen a nyers erőt alkalmazó módszereknek, és hogyan oldják meg a gyakorlatban, beleértve a weboldal mögött működő API-t is.
Mi az 1D szabási probléma
Adott egy sor fix hosszúságú szálanyag (pl. 6000 mm-es rudak) és egy lista a szükséges darabokról, hosszal és darabszámmal. Egy vágási séma egy szálanyag feldarabolásának egyik módja. Ami megmarad, az hulladék. A feladat az, hogy úgy válasszunk sémákat és vágási darabszámokat, hogy minden alkatrész elkészüljön a lehető legkevesebb szálanyagból, és így a legkevesebb hulladékkal. Ez egy 1D probléma, mert csak a hossz számít. A fűrészlap a teljes keresztmetszetet átvágja, így a szélesség és a profil nem befolyásolja a kiosztást.
1D „bin packing” (dobozpakolás), és miért NP-nehéz
A szabási probléma az 1D dobozpakolási probléma általánosítása. A dobozpakolás célja, hogy különböző méretű elemeket a lehető legkevesebb, fix méretű dobozba csomagoljunk. A szabás ugyanez a kérdés, de itt az elemek nagy mennyiségben ismétlődnek, így sémákban gondolkodunk, nem egyedi darabokban. A dobozpakolás az egyik klasszikus NP-nehéz probléma, és annak eldöntési formája – elférnek-e ezek az elemek k dobozban – NP-teljes. A szabási probléma örökli ezt a nehézséget.
Az ok a kombinatorikus robbanás. A különböző vágási sémák száma exponenciálisan nő a darabméretek számával, és a mennyiségek sémák közötti elosztásának módjai ezt tovább tetézik. Nincs ismert algoritmus, amely garantáltan optimális megoldást találna polinomiális idő alatt, és hacsak nem P egyenlő NP-vel, nem is lesz. Ezért a valódi megoldók nem sorolnak fel mindent; okosan szelektálnak a lehetőségek között.
Hogyan oldják meg a gyakorlatban
First-fit-decreasing (FFD) heurisztika
Az ipar igáslova: a darabokat hossz szerint csökkenő sorrendbe rendezzük, majd mindegyiket az első olyan rúdra helyezzük, amelyiken még elfér. Új rudat csak akkor kezdünk, ha egyiken sincs már hely. Gyors és meglepően jó, bizonyítottan kb. 11/9-ed részén belül van az optimális rúdszámnak, plusz egy kis konstans. A legtöbb szoftver itt megáll; egy jó szoftver ezt kiindulópontnak használja, nem végcélnak.
Oszlopgenerálás (Gilmore és Gomory)
A megfogalmazás, amely a nagy feladatokat is kezelhetővé tette. Gilmore és Gomory (1961) a problémát vágási sémánként egy változóval írta le. Mivel ezekből exponenciálisan sok van, a lineáris relaxációt késleltetett oszlopgenerálással oldották meg: elindulnak néhány sémával, majd egy korlátos hátizsák-alprobléma megoldásával ismételten legenerálják a következő leghasznosabb sémát. Az így kapott alsó korlát közismerten szoros.
Korlátozás és szétválasztás (branch-and-bound, branch-and-price)
Ahhoz, hogy a törtértékű relaxációból egész számú rudakat kapjunk, keresni kell, de nem vakon. A korlátozás és szétválasztás (branch-and-bound) bejárja az egész értékű választások fáját, miközben az LP korlát segítségével lemetszi azokat az ágakat, amik nem lehetnek jobbak az eddigi legjobb tervnél. Oszlopgenerálással kombinálva ez lesz a branch-and-price, a legtöbb egzakt szabászati megoldó alapja.
Alsó korlátok és a bizonyítás
Egy komoly megoldó nemcsak egy tervet ad, hanem alsó korlátot is számol (az LP relaxációból vagy egy egyszerűbb, összhossz alapú érvelésből), és összehasonlít. Ha egy terv pontosan annyi rudat használ, amennyit a korlát elkerülhetetlennek bizonyít, akkor az a terv bizonyítottan optimális. Egyetlen más terv sem lehet jobb, és a megoldó ezt közli, ahelyett, hogy a szerencsében bízna.
Hogyan oldja meg a LinearCutting
A LinearCutting ezt a folyamatot futtatja: egy gyors heurisztika az azonnali, megvalósítható tervhez, majd egy korlátvezérelt keresés, ami addig javít, amíg el nem éri az alsó korlátot (bizonyítottan optimális, és ezt jelzi), vagy le nem jár az ideje, és visszaadja az addig talált legjobb tervet. A fizikai valóságot is modellezi: vágásrés minden vágásnál, végi letisztázás, rögzített mennyiségű leesők és a ferde vágások, amik többet fogyasztanak. Egy terv, ami nem számol a fűrészlappal, nemcsak szuboptimális, hanem hibás. A tesztfeladatok nyilvánosak, így az eredményeket bármely más eszközzel összevetheti.
JSON API-ként érhető el: küldje el a darabokat és a szálanyagot, és kap egy ellenőrzött vágási tervet a vágási képekkel, a hulladékkal, a beállítások számával, és azzal, hogy a terv elérte-e az optimális korlátot. Vannak hivatalos kliensek Python (pip install linearcutting) és JavaScript vagy TypeScript (npm install linearcutting) számára, így a meghívása mindkét nyelven csak néhány sor.
Oldja meg a saját kódjából
Ne írjon saját megoldót, hívjon egyet. Az oldal kalkulátora mögött ugyanaz a motor dolgozik, JSON API-ként, hivatalos Python és JavaScript kliensekkel, ingyenes szinttel és a dokumentációban futtatható élő példával.
pip install linearcutting npm install linearcutting