板取り問題
一般に、可能なパターンの数は製品種類の数 m の関数として爆発的に増大する。製品の種類が増大するにつれて、可能な切断パターンの数の数え上げは事実上不可能になる。
他のアプローチとして、遅延列生成法(英語版)(delayed column-generation)を使うものがある。この手法では、問題を解くのにまず少数のパターンから始めて、必要になるたびにパターンを追加していく。1次元の場合、線形計画の双対変数を使った補助的な最適化問題(この場合ナップサック問題)を解くことで追加するパターンを決定する。ナップサック問題には、分枝限定法や動的計画法といったよく知られた解法がある。遅延列生成法は元の列生成法より一層効率的であり、特に問題のサイズが大きくなっていくとき威力を発揮する。板取り問題への応用としての列生成法アプローチは、 Gilmore と Gomory の1960年代の一連の論文によって切り拓かれた。 Gilmore と Gomory は、列生成法では、前もって可能な全てのパターンを列挙することなしに、解(分数となる場合も含む)へ収束することが保証されることを証明した。
オリジナルの Gilmore と Gomory の手法の難点は端数を上手く扱えないことであり、「解」が分数になり得る(あるパターンを3.67回使用する、のように)。最も近い整数に丸めるのでは上手く行かないことが多い。丸めによって非最適な解や、いくつかの製品を過剰・過少に製造するような解が出てきてしまうからである (さらに、制約条件の上限・下限を満たせなくなるかもしれない)。
品質の問題の例として、母材に除去が必要な不良箇所が生じる場合が考えられる。高品質が要求される高価な素材、例えば印画紙やタイベックであれば、廃棄部分が最小となるように注意深く最適化しなければならない。
複数マシン問題(multi-machine problem)では、大きさの異なる母材を製造する2台以上の機械が利用できるものとする。一般的に、2種類以上の大きさの母材を使用できれば廃棄量を相当に改善することができるが、実際上は追加的な製品の切り出し方法を考慮に入れる必要が生じてくる。
半連続問題(semi-continuous problem)では、製品が全く同一の大きさでなくとも、ある変動範囲に収まっていればよいとする。この状況はシート類の注文において典型的に見られ、11⁄2次元問題(11⁄2 dimensional problem)としても知られている。この変種問題は段ボール(corrugated cardboard)の製造上生じることがあり、幾分混乱を招く呼称であるが corrugator scheduling problem と呼ばれることもある。
ロール紙の製造において、マスターロールの幅が要求される製品ロールより短い場合に、スカイビング(skiving:削ぎ落とし)(または web-welding)と呼ばれる2段階目の加工を採り入れている工場もある。最初の大きなロールから切り出した2本のロールを端と端を少し重ねて繋ぎ合わせる工程である。マスターロールの幅がより短ければ、全体としての廃棄量を減らすことができる。