Vágási feladat

A beágyazási probléma  egy NP-teljes optimalizálási probléma , amely lényegében hátizsákos problémára redukálható . A probléma egy egészszámú lineáris programozási probléma . A probléma az ipar számos területén felmerül. Képzelje el, hogy Ön egy cellulóz- és papírgyárban dolgozik, és számos rögzített szélességű papírtekercse van, de a különböző ügyfeleknek különböző számú, különböző szélességű tekercsre van szüksége. Hogyan vágjunk papírt a hulladék minimalizálása érdekében?

Az Európai Papírgyártók Szövetsége [1] adatai szerint 2012-ben a régióban 1331 papírgép egyenként átlagosan 56 millió euró (körülbelül 73 millió USD) hulladékot termel. Még 1% megtakarítás is nagyon jelentős lesz.

Probléma megfogalmazása és a megoldás megközelítései

A beágyazási probléma szabványos megfogalmazása (de nem az egyetlen) egy m rendelésből álló listát feltételez, minden sorrendhez darabokra van szükség. Megalkotjuk az összes lehetséges egymásba ágyazási kombinációt ("vágótérképeket"), és minden térképhez egy pozitív egész változót rendelünk , amely jelzi, hogy a térképet hányszor használták. Írjuk fel a lineáris programozási feladatot:

ahol  - hányszor jelenik meg a megbízás a kártyán és  - a kártya (gyakran elveszett) ára . A megszorítások pontos természete némileg eltérő matematikai jellemzőket eredményezhet. A megadott limitek minimum limitek ( legalább egy adott mennyiséget kell előállítani, de nem kizárt, hogy több is lesz). Ha , akkor minimálisra kell csökkenteni a forrásanyag vágott darabjainak számát. Ha az egyenlőtlenségekből eredő kényszereket egyenlőségekkel helyettesítjük, a problémát konténerezésnek nevezzük . Általánosabb megfogalmazásban a korlátok kétoldalúak (és ebben az esetben a veszteségminimalizálási megoldás eltérhet a minimális alapanyag darabszámú megoldástól):

A probléma e megfogalmazása nem csak az egydimenziós esetre alkalmazható. Sok variáció lehetséges, például nem a hulladék minimalizálása a cél, hanem az össztermékszám maximalizálása.

Általában a lehetséges kártyák száma exponenciálisan növekszik m -vel , a megbízások számával. A megrendelések számának növekedésével nem feltétlenül célszerű felsorolni a lehetséges egymásba ágyazási mintákat.

Alternatív megoldásként utólagos generálás is használható . Ez a módszer néhány kártyával kezdődően megoldja a beágyazási problémát. A módszer szükség esetén új térképeket generál a megoldási folyamat során. Az egydimenziós esetben új térképek jelennek meg egy további optimalizálási probléma, a hátizsák probléma megoldása során, amely egy lineáris programozási probléma kettős változóira vonatkozó információkat használ fel . A hátizsák-probléma jól ismert megoldási módszerekkel rendelkezik, mint például az elágazó és kötött módszer és a dinamikus programozás . A lusta oszlopgenerálás sokkal hatékonyabb lehet, mint az eredeti megközelítés, különösen a feladat méretének növekedésével. A beágyazási problémára alkalmazott késleltetett oszlopgenerálást először Gilmour és Gomory alkalmazta az 1960-as években megjelent cikkeiben [2] [3] . Megmutatták, hogy ez a megközelítés garantáltan (töredékes) optimális megoldáshoz vezet anélkül, hogy az összes lehetséges térképet előzetesen számba kellene venni.

Gilmour és Gomory eredeti módszere nem egész, így a megoldás tört komponenseket is tartalmazhatott, például egy bizonyos térképet 3,67-szer kellett használni. A legközelebbi egész számra való kerekítés gyakran nem működik, abban az értelemben, hogy az optimálisnál szuboptimális megoldást és alul- vagy túltermelést eredményez bizonyos rendeléseknél (és esetleges megszorítások megsértése esetén, ha kétoldalas). Ezt a hiányosságot az új algoritmusok küszöbölték ki, amelyek lehetővé teszik az optimális megoldások megtalálását (a minimális pazarlás melletti megoldás megtalálása értelmében) nagyon nagy (általában a gyakorlatban szükségesnél nagyobb) problémákra [4] [5] ).

A beágyazási probléma gyakran rendkívül degenerált, hiszen azonos veszteséggel számos megoldás lehetséges. Ez a degeneráció az alkatrészek átrendezésének képességéből adódik, új egymásba ágyazási mintákat hozva létre, de nem változtatja meg az ebből eredő veszteségeket. Ez a kapcsolódó feladatok teljes gyűjteményét adja, amelyek ugyanazoknak a korlátoknak felelnek meg, mint például:

• A minimális számú beágyazótérkép megtalálásának feladata: minimális veszteséggel járó megoldások között találni egy minimális számú beágyazótérképet tartalmazó megoldást. Ez a feladat nagyon nehéz, még akkor is, ha a veszteségek ismertek [6] [7] . Van egy olyan sejtés , hogy minden egyenletre kötött, n sorrendű egydimenziós egymásba ágyazási feladatnak van legalább egy minimális hulladékmegoldása n + 1 egymásba ágyazási térképpel. A beágyazott diagramok számának felső határa nem ismert, bár ismertek az n + 5-ös példák.

• A minimálraktár feladata: olyan vágási sorrendet találni, hogy ne halmozódjon fel nagy számú, részben teljesített rendelés. A probléma egészen 2007-ig nyitott volt, amikor is megjelent egy dinamikus programozáson alapuló hatékony algoritmus [8] .

• A késcsere minimális számának problémája (egydimenziós beágyazási probléma esetén): keresse meg a fészkelőtérképek alkalmazásának sorrendjét a vágókések mozgási számának minimalizálása érdekében. Ez a probléma az általánosított utazó eladó probléma speciális esete .

Egy egydimenziós vágási probléma illusztrációja

A papírgép korlátlan számú, egyenként 5600 mm széles tekercset (nyersdarabot) képes gyártani. A következő 13 utolsó tekercset kell megszereznie:

Megoldás

Ehhez a kis feladathoz 308 lehetséges beágyazási minta létezik. Az optimális megoldáshoz 73 eredeti tekercs szükséges, és 0,401% hulladékot tartalmaz. Kimutatható, hogy ehhez a hulladékmennyiséghez a minimális fészkek száma 10. Az is kiszámítható, hogy 19 ilyen különböző megoldás létezik, mindegyikben 10 fészek és 0,401% hulladék. Egy ilyen megoldás látható az alábbiakban és az ábrán:

Osztályozás

Az egymásba ágyazási feladatok többféleképpen osztályozhatók [9] . Az egyik lehetőség a dimenziók egymásba ágyazása: a fenti példa az egydimenziós beágyazást (1D) szemlélteti. Az 1D beágyazás egyéb ipari felhasználásai a csövek, kábelek és acélrudak vágása. A bútorok, ruházati cikkek és üveggyártás során a kétdimenziós problémákat alkalmazzák. Nem sok 3D-s egymásba ágyazó alkalmazás létezik, de a kapcsolódó 3D-s csomagolási problémáknak számos ipari alkalmazása van, különösen az objektumok szállítási konténerekbe való elosztása ( lásd például Kepler hipotézisét .

A vágás feladata a papír-, film- és acéliparban

A fészkelő probléma ipari alkalmazása a tömeggyártó üzemekben akkor fordul elő, amikor az alapanyagot nagy tekercsekben állítják elő, majd kisebb darabokra vágják (lásd: hasítás ). Ez előfordul például papír- és polimer fóliák, valamint lapos fém (vas vagy bronz) lemezek gyártásánál. Számos változat és további megkötés létezik a gyártási vagy folyamati korlátok, a vevői követelmények és a minőségi problémák miatt. Néhány példa:

• Kétlépcsős eljárás, ahol a tekercset az első szakaszban gyártják, majd egy másik gépen újra feldolgozzák. Például minden irodai papír (pl . Európában A4 , az USA-ban Letter ) ebben a folyamatban készül. Nehézségek merülnek fel, mert a második folyamat gépei keskenyebbek, mint az első gépei. Mindkét folyamatlépés hatékony felhasználása fontos (anyag- és energia-megtakarítás szempontjából egyaránt), és ami az első lépésnél működik, az nem biztos, hogy a másodiknál ​​működik, ezért kompromisszumot kell találni. A fémezett fólia (élelmiszer-csomagoláshoz használatos) és a műanyaggal bevont papír ( folyadékcsomagoló karton , például gyümölcslé-csomagolás) további példák az ilyen eljárásokra.

• A csévélők fizikailag vagy logikailag korlátozzák a vágást: általános korlátozások abból fakadnak, hogy csak bizonyos számú kés megengedett, ezért a vágási táblázat nem tartalmazhat több kést, mint egy bizonyos számú kést. Mivel a tekercselők nincsenek szabványosítva, sok további korlátozás is létezik.

• További korlátozásként például a vágás irányának korlátozása adható - a lap különböző élei vastagságban nagy eltérést mutathatnak, és egyes alkalmazások nagyon érzékenyek erre.

• A minőségi követelmények hatásának példája, ha a fő tekercs olyan hibákat tartalmaz, amelyeket ki kell vágni. A magas anyagminőségi követelményeket támasztó drága anyagokat, mint például a fotópapír vagy a Tyvek , gondosan optimalizálni kell a hulladék minimalizálása érdekében.

• Többgépes feladatok akkor merülnek fel, ha egy rendelés több gépen is legyártható, és ezek a gépek eltérő szélességűek. Alapvetően a több, különböző szélességű forrástekercs elérhetősége csökkenti a hulladékot. A gyakorlatban azonban egy további vágási sorrendet kell figyelembe venni.

• Problémák adódhatnak akkor is, ha a kapott tekercseknek nem kell azonos átmérőjűeknek lenniük, de bizonyos intervallumon belül lehetnek. Néha ezt a problémát 1½ dimenziós problémának nevezik . Ez a változat megjelenik például a hullámkarton gyártásánál .

• Az acélhengeriparban az a sajátosság, hogy az eredeti tekercsek elsősorban szélességben és hosszban különböznek egymástól. Így van hasonlóság a fent leírt többgépes változattal. Ebben az esetben a hulladék szélességben és hosszban egyaránt előfordulhat.

A papíripar számára beágyazott szoftvereket az ABB Group , a Greycon , a Honeywell és a Tieto szállítja .

Az acélipar beágyazási algoritmusát Robert Gongorra fogalmazta meg 1998-ban, és a SONS (Steel Optimization Nesting Software) szoftvert fejlesztett ki az acéllemezek felhasználásának javítására és a hulladék csökkentésére.

Vágó probléma az üvegiparban

A guillotine vágás  feladata, hogy az üveglapokat meghatározott méretű téglalapokká vágják, csak a lap teljes hosszában (vagy szélességében) futó vágásokkal.

Szortiment probléma

Az ehhez kapcsolódó probléma (egydimenziós esetben) az eredeti tekercs legjobb méretének meghatározása, amely megfelel a követelményeknek; szortiment problémaként ismert [10] .

Történelem

A vágási problémát először Kantorovich fogalmazta meg 1939-ben [11] . L. V. Kantorovich és V. A. Zalgaller 1951-ben, még azelőtt, hogy a számítógépek széles körben elérhetővé váltak volna, egy módszert javasoltak [12] a vágás során az anyag gazdaságos felhasználásának problémájának lineáris programozással történő megoldására. A javasolt technikát később oszlopgenerációs módszernek nevezték el .

Szoftver

Jegyzetek

1. ↑ Kulcsstatisztikák 2012 (nem elérhető link) . Európai Papíripari Szövetség. Letöltve: 2013. július 3. Az eredetiből archiválva : 2014. október 6.. (határozatlan) 
2. ↑ PC Gilmore, RE Gomory. A vágóanyag-probléma lineáris programozási megközelítése // Operations Research. - 1961. - 9. sz . - S. 849-859 .
3. ↑ PC Gilmore, RE Gomory. A vágóanyag-probléma lineáris programozási megközelítése – II. rész // Operációkutatás. - 1963. - 11. sz . - S. 863-888 .
4. ↑ C. Goulimis. Optimális megoldások a forgácsolóanyag-problémára // European Journal of Operational Research. - 1990. - 44. sz . - S. 197-208 .
5. ↑ V. de Carvalho. Forgácsolóanyag-problémák pontos megoldása oszlopgenerálás és elágazás és kötés segítségével // International Transactions in Operational Research. - 1998. - 5. sz . - S. 35-44 .
6. ↑ S. Umetani, M. Yagiura és T. Ibaraki. Egydimenziós forgácsolóanyag probléma a különböző minták számának minimalizálása érdekében // European Journal of Operational Research. - 2003. - 146. sz . - S. 388-402 .
7. ↑ A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk és S. Naidoo. Állítsa be a minimálisra csökkentett feltételeket a vágási veszteség problémájában // European Journal of Operational Research. - 1996. - 95. sz . - S. 631-640 .
8. ↑ Maria Garcia de la Banda, PJ Stuckey. ynamic programozás a nyitott veremek maximális számának minimalizálására // INFORMS Journal on Computing. - 3007. - T. 19 , 4. sz . - S. 607-617 .
9. ↑ G. Wäscher, H. Haußner, H. Schumann. A vágási és csomagolási problémák továbbfejlesztett tipológiája // European Journal of Operational Research. - T. 183 , 3. sz . - S. 1109-1130 .
10. ↑ Raffensperger John F. Az általánosított választék és a legjobb forgácsolóanyag-hossz problémák  // International Transactions in Operational Research. - 2010. - január ( 17. évf. 1. szám ). - S. 35-49 . — ISSN 0969-6016 . - doi : 10.1111/j.1475-3995.2009.00724.x .
11. ↑ L. V. Kantorovics. A termelés szervezésének és tervezésének matematikai módszerei. – Leningrádi Állami Egyetem.
12. ↑ Kantorovich L. V., Zalgaller V. A. Ipari anyagok racionális forgácsolása. - Novoszibirszk: Nauka, 1971.

Irodalom

• lineáris programozás. - W. H. Freeman, 1983. - ISBN 978-0-7167-1587-0 .
• Hatem Ben Amor, JM Valério de Carvalho. Oszlopgenerálás // Vágókészlet-problémák az oszlopgenerációban / Guy Desaulniers, Jacques Desrosiers és Marius M. Solomon. - Springer, 2005. - T. XVI. — ISBN 0-387-25485-4 .

Linkek

• Vágással és csomagolással foglalkozó európai különleges érdekcsoport
• Egy kezdetleges nyers erő algoritmus az állomány vágásához
• Rekeszcsomagoló és vágókészlet-megoldó algoritmus