カッティングストック問題をわかりやすく解説

カッティングストック問題とは何か、なぜNP困難なのか。1次元・2次元の最適化（ギロチン切断とトゥルーネスティング）がどう良解を高速に見つけるか。

カッティングストック問題とは

在庫の長さ（バー、板材、シート）と必要な部品リストが与えられたとき、できるだけ少ない在庫ですべての部品を切り出す問題です。単純に聞こえますが、数学的にはNP困難です — 部品リストが伸びるにつれ組合せの数が爆発します。

1次元はパイプ、形材、間柱のような1つの寸法です。2次元は幅が加わります — 合板、ガラス、板金。ギロチン切断は端から端まで走る切断（パネルソーが行う方式）で、トゥルーネスティングは任意の回転と非ギロチンの配置を許します（レーザーやルーターの方式）。

厳密に解けるのは小規模なインスタンスだけです（動的計画法や整数計画法）。実務はヒューリスティクスに依存しています — First Fit Decreasing、Best Fit Decreasing、シェルフ（棚割り）法などで、通常ミリ秒単位で最適解の数%以内に着地します。

切断のたびに材料が消えます。切り幅3 mmのブレードなら1切断で3 mm、50切断で150 mmが黙って在庫を食べます。端材の再利用、木目方向、トリム損失は、詰め込み自体と同じくらい重要です。

棒材切断計算はバーと形材のリストを最適化し、板取り計算は回転と切り幅を扱うギロチンの板材レイアウトを処理します。リストを貼り付けて、前後の総在庫量を比べてください。