Giljotinklippningsuppgift

Problemet med giljotinskärning  är ett problem med kombinatorisk geometri , nära problemet med skärnings- och packningsproblem i behållare [1] . Frågan om problemet är hur man får det maximala antalet ark av rektangulär storlek från ett ark av en större storlek, och gör bara giljotinsnitt , det vill säga raka snitt från kant till kant.

Liksom skärproblemet är det ett NP-komplett problem . Det finns en serie ungefärliga och exakta algoritmer för att lösa problemet med giljotinskärning [2] [3] [4] .

Uppgiften med giljotinskärning är viktig vid tillverkning av glasskivor: glasskivor är skårade horisontellt och vertikalt och bryts sedan längs skåran.

Anteckningar

1. ↑ Gerhard Wäscher, Heike Haußner, Holger Schumann, En förbättrad typologi av skär- och packningsproblem, European Journal of Operational Research 183 (2007) 1109-1130, [1]  (länk ej tillgänglig)
2. ↑ Michael L. McHale, Roshan P. Shah skära ner giljotinen i storlek. PC AI magazine, volym 13, nummer 1 jan/feb 99. http://www.amzi.com/articles/papercutter.htm Arkiverad 29 november 2014 på Wayback Machine
3. ↑ M. Hifi, R. M'Hallah och T. Saadi, Ungefärliga och exakta algoritmer för problemet med dubbelbegränsad tvådimensionell giljotin. Computational Optimization and Applications, volym 42, nummer 2 (2009), 303-326, DOI: 10.1007/s10589-007-9081-5
4. ↑ François Clautiaux, Antoine Jouglet, Aziz Moukrim, A New Graph-Theoretical Model for the Guillotine-Cuting Problem. INFORMER Journal on Computing oktober 2011 ijoc.1110.0478 pp. 1-15