板取り問題
板取り問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/04 14:33 UTC 版)
オペレーションズ・リサーチにおける板取り問題（いたどりもんだい、英: cutting stock problem）、またはカッティングストック問題とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた数学的な最適化問題の1つであり、また計算複雑性理論においてはナップサック問題に還元されるNP困難問題の1つである。整数計画問題として定式化することができる。
1次元の例
ペーパーロール製造機が、幅5600mmのマスターロールを無限に生産できるとする。ここから下表に示したような13種類の製品ロールを切り出さなければならない。
重要なのは、同一のマスターロールから様々な方法で製品ロールを切り出せること（この切り出し方のそれぞれを「パターン」と呼ぶことにする）である。パターンの総数は一般に膨大な数に上り、列挙することは容易ではない。
この状況で、廃棄部分が最小限となるような製品ロールの最適な切り出し方を求めるのが板取り問題である。
幅 本数 1380 22 1520 25 1560 12 1710 14 1820 18 1880 18 1930 20 2000 10 2050 12 2100 14 2140 16 2150 18 2200 20
下限の確認
必要なマスターロールの本数の単純な下限は、全ての製品ロールの幅の総和をマスターロール1本の幅で割ることで求められる。この場合、総長は 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm で、マスターロールは 5600 mm なので、割り算をすると72.7本、よって73本は最低でも必要ということになる。
解
この簡単な例には、最適解が308通り存在する。どれもマスターロールを73本必要とし、廃棄率は0.401%となる。廃棄率最適（0.401%）という条件の下で、用いる切り出し方（パターン）の数を最小に抑えるような方法をコンピュータで探索すると、その最小値は10であり、それを与えるパターンの組み合わせ方は19通りあることがわかっている。19通りのうちの1つを下表に示す。
反復数 パターン 2 1820 + 1820 + 1820 3 1380 + 2150 + 1930 12 1380 + 2150 + 2050 7 1380 + 2100 + 2100 12 2200 + 1820 + 1560 8 2200 + 1520 + 1880 1 1520 + 1930 + 2150 16 1520 + 1930 + 2140 10 1710 + 2000 + 1880 2 1710 + 1710 + 2150 73
分類
板取り問題はいくつかの方法で分類できる[1]。1つの方法は切断対象の次元による分類である。上に挙げた例は1次元の問題だった。1次元の問題は他にもパイプ、ケーブル、鋼棒を切断するといった場合に適用できる。2次元の問題は家具類や布製品、ガラス製品に当てはまる。母材もしくは製品が 特殊な形状をしている場合（皮革、生地、板金等の加工ではしばしば見られる）は、ネスティング問題（Nesting problem）と呼ばれる。
3次元の切断への適用例はあまり知られていないが、この問題と密接に関連した3次元パッキング問題には、船荷の積み込み等、幅広い産業上の応用がある（例えばコンテナ輸送を参照。これに関連した球充填の問題は17世紀以来研究されている（ケプラー予想））。
紙、フィルム、金属加工品の製造において
板取り問題の製造業への応用は、比較的大きな母材からより小さな製品ユニットが切り出される場合に顕著である（参考：ロールスリッター）。これには紙やプラスチックフィルムの他、鉄や真鍮の板金も該当する。機械や製造過程での制約、顧客からの要求、品質の問題等から、多くの変種問題・追加的制約が生じる。以下はその例である:
- 2ステージ制約：（切断）加工が2段階を経る場合。例えば、オフィス用文房具(例：ヨーロッパでのA4サイズ、アメリカでのレターサイズ) はそのように製造される。第2段階では使用できる機械がより限定されたものになるため、問題が複雑になる。製造の両段階においてエネルギーと資材を効率的に利用することは重要だが、第1段階での効率化が第2段階での非効率を生むかもしれない（トレードオフが起こる）。スナック菓子の包装に使われる金属蒸着フィルムや、飲料包装紙に使われる紙へのプラスチックの押出し加工においてもこうした制約が生じる。
- 巻付機に起因する、スリット加工（マスターロールを切断し、各ロールを巻き取る過程）上の物理的・論理的な制約：非常によく見られるのは、限られた種類のスリッターナイフしか使用することができず、1度の切り出しで切り出せる製品ロールの本数に上限が課される状況である。巻付機が標準化されていないために、これ以外にも非常に多くの制約が生じることがある。
- 顧客からの要求の例として、母材の端部分からの切り出しが基準不適合となる場合が考えられる。シートの辺縁部分は厚みの変動が大きくなりやすく、製品によってはこのことが重大な問題となる。
- 品質の問題の例として、母材に除去が必要な不良箇所が生じる場合が考えられる。高品質が要求される高価な素材、例えば印画紙やタイベックであれば、廃棄部分が最小となるように注意深く最適化しなければならない。
- 複数マシン問題（multi-machine problem）では、大きさの異なる母材を製造する2台以上の機械が利用できるものとする。一般的に、2種類以上の大きさの母材を使用できれば廃棄量を相当に改善することができるが、実際上は追加的な製品の切り出し方法を考慮に入れる必要が生じてくる。
- 半連続問題（semi-continuous problem）では、製品が全く同一の大きさでなくとも、ある変動範囲に収まっていればよいとする。この状況はシート類の注文において典型的に見られ、1½次元問題（1½ dimensional problem）としても知られている。この変種問題は段ボール（corrugated cardboard）の製造上生じることがあり、幾分混乱を招く呼称であるが corrugator scheduling problem と呼ばれることもある。
- ロール紙の製造において、マスターロールの幅が要求される製品ロールより短い場合に、スカイビング（skiving：削ぎ落とし）（または web-welding）と呼ばれる2段階目の加工を採り入れている工場もある。最初の大きなロールから切り出した2本のロールを端と端を少し重ねて繋ぎ合わせる工程である。マスターロールの幅がより短ければ、全体としての廃棄量を減らすことができる[2]。
ガラス製造において
ギロチンカット問題は、定形のガラス板から、端から端までの裁断のみによって（ギロチンカット制約）、指定された大きさのいくつかの長方形を切り出す問題である。
割当問題
これに関連した1次元の決定問題、つまり、与えられた製品要求を満足するような最適な母材の大きさを定める問題は、割当問題（assortment problem）として知られている[3]。
歴史
板取り問題はレオニート・ヴィタリエヴィチ・カントロヴィチによって1939年に初めて定式化された[4]。1951年、まだコンピュータが広く実用化されていなかった頃、カントロヴィチとヴィクター・アブラモヴィッチ・ザルガラーは、切断段階における資材の効率的な利用の問題を線形計画法を用いて解くことを提案した[5]。この手法は後に列生成法と呼ばれることになる。
数学的定式化と解探索
板取り問題を数学的に定式化するには（これが唯一の方法ではないが）、まず製品種類の数 m と、各製品が要求されている単位数 
- 板取り問題のページへのリンク
