ギロチン切断
ギロチン切断: 一連の正しい端から端までの二等分切断によって完全に分割できる、最適化された小さな長方形のシート。
非ギロチン切断: これらの長方形は、平面を横切る単一の二等分切断では分離できません。

ギロチンカットとは、与えられた大きな長方形のシートから、ギロチンカットのみを用いて、一定寸法の小さな長方形のアイテムを作成するプロセスです。ギロチンカット（エッジツーエッジカットとも呼ばれます）は、紙のギロチンと同様に、既存の長方形の一方の端から反対側の端まで直線で二等分するカットです。

ギロチン切断は、特にガラス業界で広く使用されています。ガラス板に水平線と垂直線に沿って切り込みを入れ、その線に沿って割って小さなパネルにします。[ 1 ]また、鋼板の切断、家具製造用の木材の切断、段ボール箱の切断にも役立ちます。[ 2 ]

ギロチン切断に関連する最適化問題は様々であり、例えば、製造される部品の総面積、つまりその総価値を最大化する、大きなシートの廃棄物（未使用部分）の量、つまりシートの総数を最小化するといった問題が挙げられる。これらは、組合せ幾何学、オペレーションズ・リサーチ、そしてインダストリアル・エンジニアリングの分野で研究されてきた。[ 3 ]マイクロエレクトロニクスのフロアプランニングにおいて、「スライス可能なフロアプラン」とは、ギロチン切断によって製造できるフロアプランのことである。

関連するものの異なる問題として、ギロチン分割があります。この問題では、小さな長方形の寸法は事前に固定されていません。問題は、元のシートが長方形とは限らず、任意の直線多角形である可能性があることにあります。特に、シートには穴（原材料の欠陥を表す）が含まれている可能性があります。最適化の目標は通常、小さな長方形の数を最小化するか、切断の全長を最小化することです。

用語と前提

ギロチン切断に関する文献では、以下の用語と表記法がよく使用されます。

  • 大きな長方形（ストックシートとも呼ばれる）は、切断されるべき未加工の長方形シートである。これは幅W 0と高さH 0によって特徴付けられ、これが問題への主要な入力となる。
  • 小さな長方形（アイテムとも呼ばれる）は、切り取りに必要な出力です。これらは幅w iと高さh iで特徴付けられ、iは 1,..., mの範囲にあり、mは長方形の数です。多くの場合、同じ寸法の長方形が複数存在することが許されます。この場合、寸法のペア ( w i , h i ) は、しばしば型と呼ばれます。
  • カッティングパターン（単にパターンと呼ばれることが多い）は、ストックシート上に小さな長方形を配置したものです。これは点列 ( x i , y i ) として表されます（ i は 1,..., mの範囲） 。ここで ( x i , y i ) は長方形iの左下座標です。このようなパターンでは、長方形iは水平線分 ( x i , x i + w i ) と垂直線分 ( y i , y i + h i ) を占めます。
  • ビルドとは、2つの小さな長方形をくっつけて新しい長方形を作ることです。ギロチン制約のため、ビルドの種類は2種類しかありません。水平ビルドでは、結合された長方形の幅はw i + w j、高さは max( h i , h j ) です。垂直ビルドでは、結合された長方形の幅は max( w i , w j ) 、高さはh i + h jです。すべてのパターンはビルドの再帰的なシーケンスとして表現できます。すべてのビルドの再帰的なシーケンスは、等価な組み合わせ構造を持つ多くの異なるパターンに対応します。同じ再帰ビルドに対応するすべてのパターンの集合は、ギロチンカットクラスと呼ばれます。[ 4 ]

いくつかの問題では、後述するように、追加の入力が許容されます。目標は、元の長方形から、目標寸法を持ついくつかの小さな長方形を切り出すことです。以下の仮定がしばしば用いられます。[ 2 ]

  • すべてのカットは幅がゼロです。これは一般性を大きく損なうものではありません。なぜなら、各カットがd >0 の固定幅を持つ場合、 0,..., mのiに対してw iとh iにd を加えるだけで、問題は幅がゼロの変種に簡略化できるからです。
  • 対象の寸法は回転できません。つまり、w × h はh × wと同じ型ではありません。ただし、長方形を回転できるバリエーションは、回転パターンを明示的に追加することで回転できないバリエーションに縮小できるため、汎用性はそれほど損なわれません。

与えられたパターンをチェックする

パターン検証問題では、点列 ( x i , y i ) として与えられた切断パターンが存在します。ここで i は 1,..., m の範囲にあり、( x i , y i ) は長方形iの左下座標です （各目標寸法には長方形が 1 つずつ存在します）。このパターンがギロチンカットのみで実現可能かどうかを判定し、可能であれば、そのようなカットの列を見つけることが目標です。

明らかな必要条件は、2 つの入力長方形が両方の次元で重ならないことです。Ben Messaoud、 Chengbin、および Espinouse [ 5 ]は、必要かつ十分なより強い条件を提示しています。入力長方形は、x 1 ≤ ... ≤ x mとなるように左から右の順序付けされます。インデックスに順列pがあり、この順列では長方形は下から上の順序付け、つまりy p (1) ≤ ... ≤ y p ( m )となります。 4 つのインデックスi 1 ≤ i 2とj 1 ≤ j 2が与えられると、セット E( i 1、i 2、j 1、j 2 ) には、長方形 [ x i 1、x i 2 ] X [ y p ( j 1)、y p ( j 2) ] 内にあるすべての長方形のインデックスが含まれます。カッティングパターンがギロチンパターンであるためには、インデックスi 1 ≤ i 2およびj 1 ≤ j 2のすべての4つ組について、E( i 1 , i 2 , j 1 , j 2 )について次の条件の少なくとも1つが満たされる必要があります。

  1. E( i 1 , i 2 , j 1 , j 2 ) には最大で 1 つの要素が含まれます。
  2. E( i 1、i 2、j 1、j 2 ) のすべてのiにわたる水平線分 ( x i、x i + w i )の和集合は、少なくとも 2 つの互いに素な区間から構成されます。
  3. E( i 1、i 2、j 1、j 2 ) のすべてのiにわたる垂直線分 ( y i、y i + h i )の和集合は、少なくとも 2 つの互いに素な区間で構成されます。

条件2は、E( i 1 , i 2 , j 1 , j 2 )内の長方形が垂直方向の切断（2つの互いに交わらない水平方向の区間の間を通る切断）によって分離可能であることを意味する。条件3は、E( i 1 , i 2 , j 1 , j 2 )内の長方形が水平方向の切断によって分離可能であることを意味する。これらの条件を全て合わせると、隣接する長方形の集合に複数の要素が含まれる場合、それらはギロチンカットによって分離可能であることを意味する。

この条件は次のアルゴリズムによって確認できます。

  • 各反復で、少なくとも 2 つの長方形を含む特定のパターンをギロチン カットを使用して 2 つの分離したサブパターンに分割し、各サブパターンを再帰的に処理します。
  • すべてのサブパターンに 1 つの長方形が含まれるようになったら (この場合、答えは「はい」)、またはそれ以上ギロチン カットができなくなるまで (この場合、答えは「いいえ」)、停止します。

特定のパターンのギロチン カットを見つけるには、次のようにします。

  • m 個の水平間隔を決定し、左から右へ並べます。また、m 個の垂直間隔を決定し、下から上へ並べます。これには O( m log m ) の時間がかかります。
  • 重なり合う水平区間と重なり合う垂直区間を結合します。これにはO( m )の時間がかかります。
  • 結合後に少なくとも 2 つの分離された水平間隔がある場合、垂直ギロチン カットが可能です。少なくとも 2 つの分離された垂直間隔がある場合、水平カットが可能です。それ以外の場合、カットは不可能です。

順序付けステップは1回実行され、マージステップはm -1回実行されます。したがって、アルゴリズム全体の実行時間はO( m 2 )です。

アルゴリズムが「はい」を返す場合、一連のギロチンカットも生成します。「いいえ」を返す場合、ギロチンカットでは分離できない長方形の特定のサブセットも生成します。

必要十分条件は、ギロチンストリップカッティング問題を混合整数線形計画問題として表すために使用できる。[ 5 ]：sec.5 彼らのモデルは3n4/4のバイナリ変数と2n4の制約を持ち、実用的ではないと考えられている。

最適な裁断パターンを見つける

これらは2次元カッティングストック、ビンパッキング、長方形パッキング問題のバリエーションであり、カットはギロチンカットに制限されます。[ 6 ]

  • 基本的な (重み付けされていない) ギロチン切断問題では、必要な出力は、目標寸法のピースを生成する一連のギロチン切断であり、生成されるピースの合計面積が最大化されます (つまり、生の長方形からの無駄が最小化されます)。
  • 重み付け版では、各対象次元iに対して、値v iも存在します。目標は、生産されるピースの合計値を最大化することです。重み付けなし版（無駄を最小化する版）は、各対象次元の値をその面積（v i = h i * w i）とすることで、重み付け版に簡略化できます。
  • 制約付きのバリアントでは、各ターゲット次元iに対して、そのタイプで生成できるピースの数に 上限biが存在します。
    • 二重制約の変形では、各ターゲット次元iに対して、生成されるピースの数の下限a iと上限b iの両方が存在します。
  • バイナリバリアントは、各ターゲット次元が最大1回しか出現できない（つまり、上限が1である）制約付きバリアントです。このケースは、ギロチンカットを用いて各ターゲット次元の単一の要素を生成できるかどうかを判定する決定問題と関連しています。 [ 4 ]
  • ギロチンストリップ切断問題では、大きな長方形の高さは無限大（ただし幅は固定）であり、各種類の長方形を1つずつ切断し、使用する材料の総量（つまり全体の高さ）を最小化することが目標となります。これは、2次元ストリップパッキング問題の変種です。
  • 在庫最小化問題では、同じ寸法の在庫シートが無限にあり、その目標は、可能な限り少ないシート数で、必要なターゲット長方形をすべて切り取ることです。[ 5 ]これは、 2次元ビンパッキング問題の変形です。[ 7 ]
  • k 段階ギロチン切断は、ギロチン切断の制限された変種であり、切断は最大k段階で行われます。最初の段階では、水平方向の切断のみが行われ、2 番目の段階では、垂直方向の切断のみが行われます。
    • 2段階の変種では、第1段階で得られたすべてのストリップが同じ場所でカットされるか（「1グループ」と呼ばれる）、2つの異なる場所でカットされるか（「2グループ」と呼ばれる）、または異なる場所でカットされるか（「フリー」と呼ばれる）というさらなる区別があります。[ 8 ]
  • 1 単純ギロチンカットは、ギロチンカットの制限された変種であり、各カットで 1 つの長方形が分離されます。
    • 2単純ギロチンカットは1単純パターンであり、各部分はそれ自身も1単純パターンである。p単純カットパターンは再帰的に定義することができる。[ 9 ]

最適化アルゴリズム

対象とする長方形が1種類だけである特殊なケース（すなわち、すべての対象長方形が同一で、同じ向きにある場合）は、ギロチンパレット積載問題と呼ばれます。Tarnowski 、Terno、およびScheithauer [ 10 ]は、これを解くための多項式時間アルゴリズムを提示しています。

しかし、2種類以上の場合、ギロチン切断に関する最適化問題はすべてNP困難となる。その実用的重要性から、様々な厳密アルゴリズムや近似アルゴリズムが考案されてきた。

  • ギルモアとゴモリー[ 11 ] [ 12 ]は、段階的ギロチン切断と非段階的ギロチン切断の両方に対して動的計画法による再帰法を提示した。しかし、後に[ 13 ] [ 2 ]、両方のアルゴリズムに誤りがあることが示された。ビーズリー[ 2 ]は正しい動的計画法アルゴリズムを提示した。
  • ヘルツ[ 13 ]とクリストフィードとホイットロック[ 14 ]は、段階的ではないギロチン切断のためのツリーサーチ手順を提示した。
  • マスデン[ 15 ]とワン[ 16 ]はヒューリスティックアルゴリズムを提示した。
  • Hiffi、M'Hallah、Saadi [ 6 ]は、二重制約ギロチン切断問題に対するアルゴリズムを提案している。これは、最良優先探索を用いたボトムアップの分枝限定法アルゴリズムである。
  • Clautiaux、Jouglet、Moukrim [ 4 ]は、この決定問題に対する厳密なアルゴリズムを提案している。彼らのアルゴリズムは、ギロチン・カッティング・パターン・クラスを、ギロチン・グラフと呼ばれる有向グラフを用いてコンパクトに表現する。このグラフの各弧は、「水平」または「垂直」の2色のいずれかで着色される。このグラフの各単色有向サイクルは、ビルドに対応する。単色サイクルを繰り返し縮約することで、カッティング・パターン・クラスを表す再帰的なビルド・シーケンスを復元することができる。すべてのギロチン・グラフには、m個から2 m -2個の弧が含まれる。正規ギロチン・グラフと呼ばれる特殊な種類のギロチン・グラフは、固有のハミルトン閉路を含むという興味深い特性を持つ。この閉路に従って頂点をソートすると、グラフは適切にソートされた正規ギロチン・グラフとなり、このようなグラフとカッティング・パターン・クラスの間には1対1の対応関係がある。次に、適切にソートされた通常のギロチングラフの空間上で制約プログラミングを使用して最適化問題を解決します。
  • Russo、Boccia、Sforza、およびSterle [ 8 ]は、段階的ではない制約付きギロチンカット（数量の上限付き）を重み付きと重みなしの両方で扱った90以上の論文をレビューしています。正確な解を得るための主なアプローチには、動的計画法と木探索（分枝限定法）の2つがあります。木探索アプローチは、さらにボトムアップ（単一の長方形から始めて、ビルドを使用してシート全体を構築する）とトップダウンに分類されます。すべてのアプローチにおいて、探索空間を効率的にトリミングするために、適切な下限と上限を見つけることが重要です。これらの境界は、制約なし、段階的、および非ギロチンバリアントなど、関連するバリアントのソリューションから得られることがよくあります。
  • Abou Msabah、Slimane、Ahmed Riadh Baba-Ali。「直交切断問題のための改良遺伝的アルゴリズムと組み合わせた新しいギロチン配置ヒューリスティック」2011 IEEE国際産業工学・工学管理会議。IEEE、2011年。
  • Abou-Msabah、Slimane、Ahmed-Riadh Baba-Ali、Basma Sager。「直交切断ストック問題に対する新しいBLF2Gギロチン配置ヒューリスティックを用いた制御安定性遺伝的アルゴリズム」International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13, no. 4 (2019): 91–111。

実装

  • McHaleとShah [ 17 ]は、いつでも実行可能なアルゴリズムを実装したPrologプログラムを作成した。このアルゴリズムは、与えられた時間内で近似最適解を生成し、ユーザーがさらに時間を許せばそれを改善する。このプログラムは特殊紙メーカーに使用され、シートレイアウトに必要な時間を短縮し、無駄を削減することに成功した。

ギロチンによる分離

ギロチン分離は、平面上のn個の互いに素な凸オブジェクトの集合を入力とし、一連のギロチンカットを用いてそれらを分離する関連問題である。明らかに、それらのすべてを分離することはできないかもしれない。ホルヘ・ウルティア・ガリシアは[ 18 ]、それらの定数部分を分離することが可能かどうか、つまり、サイズnの任意の集合において、ギロチン分離可能なサイズcnの部分集合が存在するような定数cが存在するかどうかを問うた。

パックとタルドス[ 19 ]は次のことを証明した。

  • すべてのオブジェクトのサイズが同じであれば、それらの一定の割合を分離できます。正式には、すべてのオブジェクトが半径rの円を含み、半径Rの円に含まれている場合、サイズ の分離可能なセットが存在します。 証明: セル サイズが 8 R × 8 Rのグリッドを作成します。グリッドを一様にランダムに移動します。各オブジェクトは、確率 1/4 で水平線と交差し、確率 1/4 で垂直線と交差するため、交差するオブジェクトの期待数は です。したがって、最大 個のオブジェクトと交差するグリッド ラインが存在します。各グリッド セルの面積は で、各オブジェクトの面積は少なくとも であるため、各セルには最大 個のオブジェクトが含まれます。各セルからオブジェクトを 1 つ選択し、同じセル内の他のオブジェクトから分離します。このようにして分離されたオブジェクトの合計数は、少なくとも です。 単位正方形の場合についても同様の議論により、次のようになります。πr2128R2n≈140.7（R/r）2n{\displaystyle {\frac {\pi r^{2}}{128R^{2}}}n\approx {\frac {1}{40.7(R/r)^{2}}}n}n/2{\displaystyle n/2}n/2{\displaystyle n/2}（8R）2{\displaystyle (8R)^{2}}πr2{\displaystyle \pi r^{2}}（8R）2πr2{\displaystyle {\frac {(8R)^{2}}{\pi r^{2}}}}n2/（8R）2πr2＝πr2128R2n。{\displaystyle {\frac {n}{2}}/{\frac {(8R)^{2}}{\pi r^{2}}}={\frac {\pi r^{2}}{128R^{2}}}n.}127n。{\displaystyle {\frac {1}{27}}n.}
  • オブジェクトが直線の線分である場合、場合によっては、それらの最大数のみが分離可能である。特に、任意の正の整数kに対して、それらの最大数のみが分離可能であるような、互いに素な区間の族が存在する。お（nログ3⁡2）≈お（n0.63）{\displaystyle O(n^{\log _{3}{2}})\approx O(n^{0.63})}3け{\displaystyle 3^{k}}2け{\displaystyle 2^{k}}
  • n 個の凸オブジェクトの任意のコレクションでは、少なくともを分離できます。Ω（n1/3）{\displaystyle \オメガ (n^{1/3})}
  • n本の直線の集合においては、少なくともn本の直線は分離可能である。彼らは、最悪のケースは直線によって達成されると推測している。Ω（n1/2）{\displaystyle \オメガ (n^{1/2})}
  • n軸平行長方形の集合においては、少なくとも は分離可能である。彼らは分離可能であると推測しているが、この推測は未だ未解決である。n/（2ログ⁡n）{\displaystyle n/(2\log {n})}Ω（n）{\displaystyle \オメガ (n)}
  • Rの大きなオブジェクト(最小の包含ディスクは、最大で最大の包含ディスクのR倍)の任意のコレクションでは、少なくとも個のオブジェクトを保存できます。ここで、はRのみに依存する定数です。 n/（cRログ⁡n）{\displaystyle n/(c_{R}\log {n})}cR{\displaystyle c_{R}}
    • 同様の定理は高次元でも有効です。分離可能なオブジェクトの数は です 。n/c（R、d）（ログ⁡n）d{\displaystyle n/c(R,d)(\log {n})^{d}}
  • これらの分離可能なサブファミリーはすべて、時間 で構築できます。オブジェクトが全体としてN辺の多角形である場合、分離線は時間 で計算できます。お（nログ⁡n）{\displaystyle O(n\log {n})}お（北+nログ⁡n）{\displaystyle O(N+n\log {n})}

アベド、チャレルムスク、コレア、カレンバウアー、ペレス・ランテロ、ソト、ヴィーゼ[ 20 ]は次のことを証明した。

  • n軸に平行な単位正方形の任意の集合では、少なくともn /2 を分離することができ、最大でn /2 を分離できる場合もあります。
  • n軸に平行な正方形の任意の集合では、少なくともn /81 を分離できます。
  • 重りが付いたn軸平行の正方形の集合では、合計重りの少なくとも 4/729 を分離できます。
  • 重量のあるn軸平行d次元立方体の任意のコレクションでは、総重量の を分離できます。1/2お（d）{\displaystyle 1/2^{O(d)}}
  • 軸平行長方形が分離可能であるという推測に関しては、彼らはそれを解決していないが、それが正しい場合は、軸平行長方形の最大分離集合の問題に対する O(1) 近似アルゴリズムが時間内に得られることを示している。Ω（n）{\displaystyle \オメガ (n)}お（n5）{\displaystyle O(n^{5})}

カーンとピットゥ[ 21 ]は次のことを証明した。

  • n軸平行長方形の場合、ステージのみが許可されると長方形を分離することはできません。o（ログ⁡ログ⁡n）{\displaystyle o(\log \log n)}Ω（n）{\displaystyle \オメガ (n)}
  • 長方形に重み付けをする場合、ステージのみが許可されると重みを分離できなくなります。o（ログ⁡n/ログ⁡ログ⁡n）{\displaystyle o(\log {n}/\log \log {n})}Ω（n）{\displaystyle \オメガ (n)}
  • 長方形を分離する単純な2段階アルゴリズムがあります。このアルゴリズムは、長方形をサブセット（「レベル」と呼ばれる）に分割し、長方形の数が最も多いレベルを選択します。各レベルは2回のギロチンカットで分離できます。[ 21 ]：Thm.14 改良されたアルゴリズムは長方形を分離できます。n/（1+ログ2⁡n）{\displaystyle n/(1+\log_{2}{n})}1+ログ2⁡n{\displaystyle 1+\log _{2}{n}}n/ログ3⁡（n+2）{\displaystyle n/\log_{3}{(n+2)}}
  • 太い長方形の任意のコレクションでは、分離できます。Ω（n）{\displaystyle \オメガ (n)}
  • n軸に平行な正方形の任意の集合では、少なくともn /40 を分離できます。
  • 重さのあるn軸平行正方形の集合では、少なくとも総重さの 1/80 の割合で分離できます。

参照:

その他のバリエーション

最近研究されたこの問題の変種には次のようなものがあります。

  • 3次元のギロチン切断。[ 22 ] [ 23 ]
  • ギロチン切断では、原料の長方形には欠陥があっても、生産された長方形には欠陥がないようにする必要があります。[ 24 ]

参考文献

  1. ^ Tlilane, Lydia; Viaud, Quentin (2018-05-18). 「Challenge ROADEF/EURO 2018 切削最適化問題の説明」(PDF) . Challenge ROADEF/EURO . ROADEF . 2019年6月13日閲覧.
  2. ^ a b c d Beasley, JE (1985-04-01). 「制約のない2次元ギロチン切断アルゴリズム」 . Journal of the Operational Research Society . 36 (4): 297– 306. doi : 10.1057/jors.1985.51 . ISSN 0160-5682 . S2CID 58059319 .  
  3. ^ Gerhard Wäscher, Heike Haußner, Holger Schumann, 切削と梱包の問題の改良された類型論, European Journal of Operational Research 183 (2007) 1109–1130, [1] 2016年12月20日アーカイブ, Wayback Machine
  4. ^ a b c Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (2011-10-17). 「ギロチン切断問題のための新しいグラフ理論モデル」 . INFORMS Journal on Computing . 25 (1): 72– 86. doi : 10.1287/ijoc.1110.0478 . ISSN 1091-9856 . 
  5. ^ a b c Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (2008-11-16). 「ギロチン制約の特性評価とモデリング」 . European Journal of Operational Research . 191 (1): 112– 126. doi : 10.1016/j.ejor.2007.08.029 . ISSN 0377-2217 . 
  6. ^ a b M. Hifi, R. M'Hallah, T. Saadi, 二重制約付き二次元ギロチン切断ストック問題に対する近似アルゴリズムと厳密アルゴリズム. 計算最適化とその応用, 第42巻, 第2号 (2009), 303-326, doi : 10.1007/s10589-007-9081-5
  7. ^ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (2007-08-01). 「固定方向の2次元ビンパッキング問題に対する新しい縮約手順と下限値」 . Computers & Operations Research . 34 (8): 2223– 2250. doi : 10.1016/j.cor.2005.08.012 . ISSN 0305-0548 . 
  8. ^ a b Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). 「制約付き2次元ギロチン切断問題：上限値のレビューと分類」 . International Transactions in Operational Research . 27 (2): 794– 834. doi : 10.1111/itor.12687 . ISSN 1475-3995 . S2CID 195551953 .  
  9. ^ Scheithauer, Guntram (1993). 「最適なφ単純ギロチン切断パターンの計算」 (PDF) . Journal of Information Processing and Cyber​​netics . 29 (2): 115– 128.
  10. ^ Tarnowski, AG; Terno, J.; Scheithauer, G. (1994-11-01). 「ギロチンパレット積載問題に対する多項式時間アルゴリズム」 . INFOR: 情報システムとオペレーションズ・リサーチ. 32 (4): 275– 287. doi : 10.1080/03155986.1994.11732257 . ISSN 0315-5986 . 
  11. ^ Gilmore, PC; Gomory, RE (1965-02-01). 「2次元以上の多段階カッティングストック問題」 .オペレーションズ・リサーチ. 13 (1): 94–120 . doi : 10.1287/opre.13.1.94 . ISSN 0030-364X . 
  12. ^ Gilmore, PC; Gomory, RE (1966年12月1日). 「ナップサック関数の理論と計算」 .オペレーションズ・リサーチ. 14 (6): 1045–1074 . doi : 10.1287/opre.14.6.1045 . ISSN 0030-364X . 
  13. ^ a b Herz, JC (1972年9月). 「2次元ストックカットのための再帰計算手順」 . IBM Journal of Research and Development . 16 (5): 462– 469. doi : 10.1147/rd.165.0462 . ISSN 0018-8646 . 
  14. ^ Christofides, Nicos; Whitlock, Charles (1977-02-01). 「2次元切断問題のためのアルゴリズム」 .オペレーションズ・リサーチ. 25 (1): 30– 44. doi : 10.1287/opre.25.1.30 . ISSN 0030-364X . 
  15. ^ OBG Masden (1980)、IMSORワーキングペーパー、デンマーク工科大学、リンビー
  16. ^ Wang, PY (1983-06-01). 「制約付き2次元カッティングストック問題のための2つのアルゴリズム」 .オペレーションズ・リサーチ. 31 (3): 573– 586. doi : 10.1287/opre.31.3.573 . ISSN 0030-364X . 
  17. ^ Michael L. McHale、Roshan P. Shah著『ギロチンの大きさを測る』PC AI誌、第13巻、第1号、1999年1月/2月号。http ://www.amzi.com/articles/papercutter.htm
  18. ^ 1996年メキシコ、タスコで開催されたACCOTA '96「最適化トポロジーと代数の組み合わせ的および計算的側面」で発表された問題
  19. ^ Pach, J.; Tardos, G. (2000). 「ガラスを切る」 .離散幾何学と計算幾何学. 24 ( 2–3 ): 481–496 . doi : 10.1007/s004540010050 . ISSN 0179-5376 . S2CID 1737527 .  
  20. ^アベド、フィダア;チャレルムスク、パリニャ。コレア、ホセ。カレンバウアー、アンドレアス。ペレス・ランテロ、パブロ。ソト、ホセ A.ヴィーゼ、アンドレアス (2015)。ギロチン切断シーケンスについて。 pp.  1–19 . doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1。ISBN 978-3-939897-89-7。
  21. ^ a b Khan, Arindam; Pittu, Madhusudhan Reddy (2020). Byrka, Jaros\law; Meka, Raghu (編). 「正方形と長方形のギロチン分離可能性について」 .近似、ランダム化、および組み合わせ最適化. アルゴリズムとテクニック (APPROX/RANDOM 2020) . Leibniz International Proceedings in Informatics (LIPIcs). 176 . ダグストゥール、ドイツ: Schloss Dagstuhl–Leibniz-Zentrum für Informatik: 47:1–47:22. doi : 10.4230/LIPIcs.APPROX/RANDOM.2020.47 . ISBN 978-3-95977-164-1。
  22. ^マーティン、マテウス;オリベイラ、ホセ・フェルナンド。シルバ、エルサ。モラビト、レイナルド。ムナーリ、ペドロ (2020-11-08)。「制約されたパターンによる三次元ギロチン切断問題: MILP 定式化とボトムアップ アルゴリズム」。アプリケーションを備えたエキスパート システム。168 114257.土井: 10.1016/j.eswa.2020.114257。ISSN 0957-4174。S2CID 228839108。  
  23. ^ Baazaoui, M.; Hanafi, S.; Kamoun, H. (2014-11-01). 「3次元複数ビンサイズビンパッキング問題（MBSBPP）の数学的定式化と下限値：チュニジアの産業事例」2014年国際制御・意思決定・情報技術会議（CoDIT） . pp.  219– 224. doi : 10.1109/CoDIT.2014.6996896 . ISBN 978-1-4799-6773-5. S2CID  18598442 .
  24. ^ Martin, Mateus; Hokama, Pedro HDB; Morabito, Reinaldo; Munari, Pedro (2020-05-02). 「欠陥のある制約付き2次元ギロチン切断問題：ILP定式化、ベンダー分解、CPベースアルゴリズム」 . International Journal of Production Research . 58 (9): 2712– 2729. doi : 10.1080/00207543.2019.1630773 . ISSN 0020-7543 . S2CID 197434029 .  
「 https://en.wikipedia.org/w/index.php?title=ギロチン切断&oldid= 1329507373」より取得