Guillotine vágási feladat

A guillotine vágás  problémája a kombinatorikus geometria problémája , közel áll a konténerek vágási és csomagolási problémáihoz [1] . A probléma kérdése, hogy egy nagyobb méretű lapból hogyan lehet a maximális számú téglalap méretű lapot előállítani, csak guillotine vágást, azaz éltől szélig egyenes vágást végezve.

Mint a vágási probléma, ez is egy NP-teljes probléma . A guillotine vágás problémájának megoldására egy sor közelítő és pontos algoritmus létezik [2] [3] [4] .

A lemezüveg gyártásánál fontos a guillotine vágás feladata: az üveglapokat vízszintesen és függőlegesen hornyolják, majd a bevágás mentén törik.

Jegyzetek

1. ↑ Gerhard Wäscher, Heike Haußner, Holger Schumann, A vágási és csomagolási problémák továbbfejlesztett tipológiája, European Journal of Operational Research 183 (2007) 1109-1130, [1]  (hivatkozás nem érhető el)
2. ↑ Michael L. McHale, Roshan P. Shah méretre vágja a guillotine-t. PC AI magazin, 13. kötet, 1. szám, január/február 99. http://www.amzi.com/articles/papercutter.htm Archiválva : 2014. november 29. a Wayback Machine -nél
3. ↑ M. Hifi, R. M'Hallah és T. Saadi, Hozzávetőleges és pontos algoritmusok a kettős kényszerű kétdimenziós guillotine vágóanyag-problémához. Számítási optimalizálás és alkalmazások, 42. kötet, 2. szám (2009), 303-326, DOI: 10.1007/s10589-007-9081-5
4. ↑ François Clautiaux, Antoine Jouglet, Aziz Moukrim, A Guillotine-vágási probléma új gráfelméleti modellje. INFORMÁL Journal on Computing 2011. október ijoc.1110.0478 pp. 1-15