Задача гильотинного раскроя

Гильотинный раскрой.

Задача гильотинного раскроя — задача комбинаторной геометрии, близкая к задаче раскроя и задачам упаковки в контейнеры[1]. Вопрос задачи — как получить максимальное число листов прямоугольного размера из листа большего размера, делая только гильотинные разрезы, то есть прямые разрезы от края до края.

Как и задача раскроя, является NP-полной задачей. Существует серия приближённых и точных алгоритмов решения задачи гильотинного раскроя[2][3][4].

Задача гильотинного раскроя важна при производстве листового стекла: листы стекла надрезаются горизонтальными и вертикальными прямыми, а затем разламываются вдоль надреза.

Примечания

  1. ↑ Gerhard Wäscher, Heike Haußner, Holger Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109—1130, [1] (недоступная ссылка)
  2. ↑ Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm Архивная копия от 29 ноября 2014 на Wayback Machine
  3. ↑ M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 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-Cutting Problem. INFORMS Journal on Computing October 2011 ijoc.1110.0478 pp. 1-15