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

Задача гильотинного раскроя — задача комбинаторной геометрии, близкая к задаче раскроя и задачам упаковки в контейнеры[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,  (недоступная ссылка)
  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
  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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.