ギロチンカット問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/08 08:19 UTC 版)
ギロチンカット問題（ギロチンカットもんだい、英：Guillotine problem）とは、組合せジオメトリと印刷の問題のことである。
梱包の問題、特に在庫とビンの梱包の問題に密接に関連して[1]、大きいシートから1つの長方形サイズのシートの最大数を取得する方法の問題。紙カットギロチンのように、シートの1つの構成要素を2等分する直交カットのみが許される。
ガラス加工では、ギロチンの問題が重要である。ガラスシートは、水平線と垂直線に沿って刻み目が付けられ、これらの線に沿って分割され、より小さいパネルが得られる[2]。
板取り問題と同様に、NP困難な問題として知られているが、さまざまな近似および厳密アルゴリズムが考案されている[3][4][5]。
脚注
- ^ 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,
- ^ Tlilane (2018年5月18日). “Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description”. Challenge ROADEF/EURO. ROADEF. 2019年6月13日閲覧。
- ^ 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
- ^ 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
- ^ 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
- ギロチンカット問題のページへのリンク
