Guillotine problem

The guillotine problem is a problem in combinatorial geometry and in printing.

An optimised sheet of smaller rectangles which can be divided intact through the correct series of "guillotine" cuts.
A non-optimised sheet: these rectangles cannot be separated by making single cuts across the plane.

Closely related to packing problems and specifically to cutting stock and bin packing problems,[1] it is the question of how to get the maximum number of sheets of one rectangular size out of a larger sheet, only orthogonal cuts that bisect one component of the sheet are allowed, as on a paper cutting guillotine.

The Guillotine problem is important in glass machining. Glass sheets are scored along horizontal and vertical lines and then broken along these lines to obtain smaller panels.[2]

Like the cutting stock problem, it is NP hard, but various approximate and exact solutions have been devised.[3][4][5]

References
  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. Tlilane, Lydia; Viaud, Quentin (2018-05-18). "Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description" (PDF). Challenge ROADEF/EURO. ROADEF. Retrieved 2019-06-13.
  3. 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
  4. 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
  5. 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.