Mi az anyagszabási probléma? Közérthető magyarázat

Ha valaha álltál már egy halom Pfleiderer- vagy Egger-lap előtt ceruzával a kezedben, és azon gondolkodtál, hogyan fér ki az összes alkatrész a lehető legkevesebb lemezből — akkor már találkoztál az anyagszabási problémával. Csak nem tudtad, hogy a matematikusok évtizedek óta kutatják. Ez a kérdés minden bútorgyártó műhely hétköznapjainak része, és a válasz közvetlenül hat az anyagköltségre, a hulladékra és a nyereségedre.

A probléma, amivel minden asztalos találkozik

Tegyük fel, hogy egy komplett konyhabútor-garnitúrát gyártasz. 14 oldallap, 7 polc, 7 hátfal, 14 ajtólap — összesen 42 alkatrész, szabvány 2800×2070 mm-es lapokból. Minden darabnak megvan a maga mérete. Néhánynál fontos az erezet iránya, másoknál mindegy. A fűrészed 3 mm-es réssel vág.

Hány lap kell, hogy minden alkatrész kiférjen? Próbáld meg ceruzával, papíron kiszámolni. Az első lap elrendezésével eltöltesz húsz percet, törölsz, újrarajzolsz. A harmadik lapnál már nem tudod, melyik darabokat helyezted el. És a végén sincs garancia, hogy létezik-e jobb megoldás.

Lényegében ez az anyagszabási probléma: adott méretű alapanyagból adott méretű darabokat kell kivágni úgy, hogy a lehető legkevesebb lapot használd el, és a lehető legkevesebb hulladék keletkezzen.

A mögöttes matematika, érthetően

Az informatikusok az anyagszabási problémát „NP-nehéznek” hívják. Gyakorlatban ez annyit tesz, hogy az alkatrészek számával a lehetséges elrendezések száma olyan gyorsan nő, hogy egyetlen számítógép sem képes mindegyiket végigpróbálni ésszerű idő alatt. 10 alkatrésznél néhány ezer érvényes variáció létezik. Már önmagában az is, hogy 40 darabot milyen sorrendben vágsz ki, 40 faktoriális lehetőség — egy 48 jegyű szám —, és ez még azelőtt van, hogy eldöntenéd, melyik darab hova kerül a táblán, és melyiket forgatod el. 100 darabnál, azaz nagyjából egy konyhánál, már a puszta sorrendek száma is meghaladja a megfigyelhető univerzumban lévő atomok számát.

Ez a probléma ugyanabba a családba tartozik, mint a bin packing feladat: fix méretű tárolókba változó méretű tárgyakat pakolsz, és a lehető legkevesebb tárolót szeretnéd felhasználni. Az algoritmusok nem próbálnak ki minden kombinációt — heurisztikákat alkalmaznak. Ilyen stratégiák például a „legnagyobb darab először” elv, az oszlopgenerálás vagy a genetikus algoritmusok. Ezek másodpercek alatt megtalálják a közel optimális megoldást. Nem mindig adják a tökéletes elrendezést, de stabilan jobbak, mint bármilyen kézi kísérlet.

Honnan ered a feladat?

Nem az asztalosiparból — oda csak megérkezett.

A feladat első komoly megfogalmazása Leonyid Kantorovicshoz köthető, aki 1939-ben a szovjet rétegeltlemez-ipar számára írta le, hogyan kellene a rendelkezésre álló táblákat a megrendelt darabokra osztani. A megoldás módszere ugyanaz volt, amiből később a lineáris programozás egésze kinőtt, és amiért Kantorovics közgazdasági Nobel-emlékdíjat kapott.

A ma is használt algoritmikus áttörés Gilmore és Gomory nevéhez fűződik, akik 1961-ben a papíriparban dolgozták ki az oszlopgenerálást: ott a nagy papírtekercseket kellett megrendelt szélességű kisebb tekercsekre hasítani, és a lehetséges vágási minták száma ugyanúgy kezelhetetlenül nagy volt. Az ő megközelítésük az, ami a mai szabásoptimalizálók nagy részében ott van valamilyen formában.

Ez a származás magyarázza, miért működik ugyanaz a matematika acélra, üvegre, textilre és papírra is: a feladatot eleve általánosan fogalmazták meg, anyagtól függetlenül. És egyben azt is megmagyarázza, mit tud valójában egy optimalizáló szoftver. Nem „ért a fához” — csak nagyon jól keres egy olyan térben, amiben az ember néhány próbálkozás után elfárad.

Miért pazarol mindig többet a kézi tervezés

Nézzünk egy konkrét példát. Öt nagy alkatrészt kell kivágni egy szabvány 2800×2070 mm-es Pfleiderer lapból:

• 2× oldallap: 2100×600 mm
• 2× polc: 800×500 mm
• 1× hátfal: 2100×800 mm

Kézzel a legtöbb asztalos a legnagyobb darabokat helyezi el először, majd a kisebb darabokkal tölti ki a réseket. Egy táblázatkezelővel követheted a területfelhasználást, de a forgatásokat és az alternatív elrendezéseket nem tudod gyorsan tesztelni. Egy optimalizáló algoritmus másodpercek alatt több száz elrendezést értékel ki.

Egy Pfleiderer lap ára nagyjából 4 200 Ft nettó. Ha manuális tervezéssel két lap helyett háromra van szükséged egy konyhabútor-projektnél, az azonnal ~3 000 Ft kidobott hulladékanyag laponként. Éves szinten, sorozatgyártásnál ez könnyen százezres tétel.

Hol találkozol a gyakorlatban az anyagszabási problémával

Az anyagszabási probléma mindenhol megjelenik, ahol szabvány méretű alapanyagot darabolsz:

• Bútorgyártás és asztalos munkák — Melamin, MDF és rétegelt lemez lapszabása tucatnyi különböző méretre. Az erezet iránya külön megkötés.
• CNC lapszabás — Az automata vágógépnek elrendezési fájl kell. Az optimalizáló közvetlenül generálja, nincs szükség kézi beágyazásra a gépvezérlőn.
• Fémlemez megmunkálás — Az acél- és alumíniumlemezek négyzetméterára jóval magasabb, így 3–5% hulladékcsökkentés is komoly összeg.
• Üveg- és csempevágás — Törékeny anyagok, ahol a hibás vágás nem használható fel újra.
• Lineáris (1D) darabolás — Rudak, csövek, profilok, deszkahosszok. Ugyanaz a probléma, egy dimenzióval kevesebb.

Hogyan oldja meg a szoftver

A folyamat egyszerűbb, mint gondolnád. Megadod a szükséges alkatrészeket — méreteket, darabszámot, szükség esetén az erezet irányát. Beírod az alapanyag méretét (vagy több méretet, ha a beszállítód többféle lapot kínál). Beállítod a fűrészrés szélességét, általában 3–4 mm. Aztán rákattintasz az optimalizálásra.

A háttérben az algoritmus különböző elhelyezéseket, forgatásokat és lapoldalakat próbál végig. Minden elrendezést a teljes hulladékszázalék és a szükséges lapszám alapján értékel. Másodpercek alatt visszakapod a szabástervet — egy vizuális térképet, ami pontosan megmutatja, melyik darab hova kerül melyik lapon.

Az eredmény nyomtatható elrendezés, pozíciókkal ellátott alkatrészlista és pontos hulladékszámok. Nincs tippelés, nincs újrarajzolás, nincs kimaradt alkatrész.

Mi különbözteti meg a gyakorlatot a tankönyvtől?

Öt megkötés, amiről a tiszta matematikai feladat nem tud — és mind az ötöt neked kell megadnod.

A fűrészrés. A tankönyvi változatban a vágás vastagság nélküli vonal. A műhelyben minden áthaladás elvisz egy sávot az anyagból, és ez az egyetlen különbség képes egy papíron tökéletesen kijövő elrendezést kivitelezhetetlenné tenni.

A guillotine-korlát. A panelfűrész csak éltől élig tud vágni. Elméletileg jobb elrendezések tucatjai esnek ki emiatt — olyanok, amiket egy CNC maró kivágna, egy lapszabász gép viszont nem.

A szálirány. A tiszta feladatban minden téglalap szabadon forgatható. Egy tölgy mintázatú dekorlapon nem az, és a megkötés pontosan azokra a darabokra vonatkozik, amelyek a leginkább látszanak.

A készlet nem végtelen. A klasszikus megfogalmazás korlátlan mennyiségű, azonos méretű alapanyagot feltételez. A műhelyben három egész tábla áll a falnál és négy különböző méretű maradék az állványon, és a jó terv pont ezt használja fel.

A minimális használható maradék. A matematika szempontjából a hulladék hulladék. A műhely szempontjából egy 600 × 400 mm-es darab készlet, egy 40 mm-es csík viszont szemét. Két terv azonos hulladékaránnyal ezért egyáltalán nem egyformán jó.

Ez a különbség az oka annak is, hogy az anyagszabási feladat és a klasszikus bin packing nem ugyanaz, csak közeli rokonok. A bin packing azt kérdezi, hány tárolóba fér be egy adag tárgy; az anyagszabás azt, hogyan lehet adott alapanyagból kivágni a darabokat — és ezzel behozza a fenti öt megkötést, amelyek közül egyik sem elméleti.

Végül ebből következik egy gyakorlati tanulság is: ha egy munka sok anyagot pazarol, annak szinte sosem a számítási idő az oka. A nyereség nagy része az első pillanatokban érkezik meg, utána a keresés jellemzően már csak megerősíti, hogy a meglévő tervet nehéz überelni. A valódi ok szinte mindig egy rossz bemenet — nem az a táblaméret, amit ténylegesen veszel, feleslegesen rögzített szálirány, vagy a polcon álló maradék, amit senki nem vitt be.

Az anyagkihasználás számokban

Egy átlagos asztalos műhely évi 200–400 szabvány lapot használ el. Ha az átlagos hulladékarány 30%-ról 12%-ra csökken optimalizálással, az 18 százalékpontos javulás. 300 lap esetén ez durván 54 lap megtakarítás — 4 200 Ft-os egységáron számolva 226 800 Ft nettó évente, csak az alapanyagon. Az idő, amit a kézi tervezés helyett a tényleges munkára fordítasz, ebben még nincs benne.

A vágásoptimalizálás nem varázslat — algoritmusok dolgoznak a háttérben, amelyeket évtizedek óta fejlesztenek. De a végeredmény gyakorlatias: kevesebb hulladék, kevesebb lap, alacsonyabb költség.