コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ギロチンカット問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ギロチン切断によって得られるパーティション

ギロチンカット問題:Guillotine problem)とは、 組み合わせジオメトリ印刷の問題のことである。

梱包の問題 、特に在庫ビンの梱包の問題密接に関連して[1]、 大きいシートから1つの長方形サイズのシートの最大数を取得する方法の問題。紙カットギロチンのように、シートの1つの構成要素を2等分する直交カットのみが許される。

ガラス加工では、ギロチンの問題が重要である。 ガラスシートは、水平線垂直線に沿って刻み目が付けられ、これらの線に沿って分割され、より小さいパネルが得られる[2]

板取り問題と同様に、 NP困難だが、さまざまな近似および厳密アルゴリズム考案されている[3] [4] [5]

脚注

[編集]
  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 (2018年5月18日). “Challenge ROADEF / EURO 2018 Cutting Optimization Problem Description”. Challenge ROADEF/EURO. ROADEF. 2019年6月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