数理解析研究所講究録 1297 巻 2002 年 116-124

116
カッティングストック問題に対する線形計画法に基づく局所探索法の提案(Shunji Umetani)(Mutsunori Yagiura)(Toshihide Ibaraki)
Graduate School of Informatics,
Kyoto University

京都大学情報学研究科

梅谷俊治
柳浦睦憲
茨木俊秀

Abstract
カッティングストック問題は, 様々な形状や大きさの製品を, 顧客の注文に応じて定型の母材から切出し, 母材の材料費や切出しにかかる工程費を最小化する計画を求める問題である. 1
本の母材から切出す製品の組合せはカッテイングパターン (以下, パターンと略す) と呼ぼれる.
過去の素材産業では材料費が総費用の大半を占めていたため, 単に使用する母材の本数を最小化する定式化に基づく手法が多く提案されてきた. しかし, 近年, 材料費の低下に伴いパターン
変更に伴う段取り替え作業回数の削減が重要視されている. そこで, 本研究では, あらかじめ与
えられた段取り替え数 (パターン数) の元で, 使用母材の本数を最小化するカッティングストッ
ク問題に対して, 線形計画法に基づく局所探索法を提案する.

1

カッティングストツク問題, 及び注文数
入力として, 母材長 , 製品種類数 $m$ , 各製品の長さと,使用可能なパターン数 が与えられる. パターン $pj$ が製品 を切出す数を, パターン の適用
回数を $Xj$ とすると, 使用可能パターン数 の元で使用母材の本数を最小化するカッティングストッ
ク問題は以下の通りに定式化できる.
$L$$l_{1},$$l_{2},$$\ldots,$$d_{1},d_{2},$ $\ldots,d_{m}$$l_{m}$$i$$n$$a_{ij}$$p_{j}$

$n$

(CSP)

$\min$$f( \mathrm{I}\mathrm{I}, X)=\sum xj$(1)

pj\epsilon$\mathrm{s}.\mathrm{t}$.

$\sum a_{1j^{X}j}.\leq d_{i}$, for $i\in M$

pj\epsilon$\subseteq S$$|\text{ }|=n$$xj\in Z_{+}$$r_{i}\in Z_{+}$, for$pj\in \mathrm{I}\mathrm{I}$, for $i\in M$ .

兇六藩僖僖拭璽鵑僚弦 $\{p_{1},p_{2}, \ldots,p_{n}\}$ , $X$ は使用パター
ここで, $M$ は製品の集合 $\{1, 2, \ldots, m\}$ ,$\{x_{1}, x_{2}, \ldots, x_{n}\}$ を表す.
ン集合 兇粒謄僖拭璽鵑療 用回数は以下の式 (2) を満たす任意のパター
集
表\mbox{\boldmath $\tau$}.
$S$$\sqrt\mathrm{B}^{\mathrm{a}}\text{ら或る}$$\hat{[]}$$\text{を}$$\sum_{\dot{\iota}\in M}a_{j}.\cdot l:\leq L$

カッテイングストック問題は$\mathrm{N}\mathrm{P}$.

困難のクラスに属する事が知られている.

(2)

117
2

提案解法

本研究では, カツテイングストツク問題に対して局所探索法に基づく解法を提案する. 局所探索
法は, ある初期実行可能解から開始して, 近傍操作により得られる近傍解に暫定解より良い解があ困難に代表される複雑な組合せ最適
れぼ暫定解を入れ替える作業を繰り返し行う解法であり,化に対する代表的な近似解法として多くの問題に適用されている. 局所探索法を組合せ最適化問
題に適用する際には, 以下の点を考慮する必要がある.
$\mathrm{N}\mathrm{P}$・初期実行可能解の生或・近傍解の生或・近傍解の評価
使用パターン数に制限のあるカッテイングストツク問題では, 初期実行可能解を求める問題は NP
完全のクラスに属するビンパッキング問題と等価である. 本研究では 2J 節で, ビンパツキング問
題に対する近似解法の 1 つである First-Fit 法を適用して初期実行可能解を求める. 次に, 近傍解兇鮨靴燭淵僖拭璽 $p_{j}’\in S$ に人替えては, 使用パターン集合 尭發里△襯僖拭璽 $pj\in$$\text{ ^{}\prime}\in N(\text{ })$得られる. しかし, 式 (2) に示される実行可能なパターンの数は製品数 $m$ の指数オーダーとなるため, これら全てを暫定使用パターン集合に対する人替えパターン候補として評価することは困難である. 本研究では 22 節で, 線形計画問題における感度分析を基に, 改善解が得られる見込みのあるパターンのみを生或する手法を提案し, 暫定解に対して $O(n^{2})$ 個の入替えパターン候補を生或す
る. 各パターンの適用回数 $X$ は, 使用パターン集合垣が与えられた際に以下の式 (3) の整数計画問
題を解く事で得られる.
$(\mathrm{I}\mathrm{P}(\text{ }))$$\min$$\mathrm{s}.\mathrm{t}$.

(3)$f(X)= \sum_{j=1}^{n}xj$$\sum_{j=1}^{n}aijxj-r:=d_{:}$$x_{j}\in Z_{+}$$r:\in Z_{+}$, for $i\in M$, for $j\in N$, for $i\in M$ .

提案解法では, 式 (3) の各変数 $Xj$ の整数制約 $(Xj\in Z_{+})$ を非負実数制約 $(Xj\geq 0)$ に緩和して得られる線形計画問題
を解き, 得られた実数最適解$X$– を丸めて得られる整数近似解 を各パターンの適用回数とする. しかし, 依然として非常に多くの線形計画問題を繰り返し解く必要があるため, 本研究では 23 節で線形計画法の高速化を行う. 最後に局所探索法の概観を 2.4 節でまと$\hat{X}$$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$

める.

2.1

初期解生成

本節では, 初期実行可能解を求める発見的解法について説明する. 使用パターン数が 種類に制限されたカツテイングストツク問題において, 初期実行可能解を求める問題は, 各製品 $i\in M$ が使用パターン集合\Gamma I $=\{p_{1},p_{2}, \ldots,p_{n}\}$ に少なくとも 1 度現れる割当てを求める問題として定式化できる. これは, 以下のビンパッキング問題と等価である.
$n$

ビンパッキング問題

118
入力: 製品集合 $M=\{1,2, \ldots, m\}$ と各製品長
出力: 製品集合 $M$ の分割
満す.

$M_{1},$ $M_{2},$$\ldots,$$M_{n}$$l_{i}$, 使用パターン数 , 母材長$n$, 各部分集合 $Mj\subseteq M$ は$\sum_{i\in M_{j}}$$L$.

$l_{i}\leq L$を

本研究では, ビンパツキング問題に対する発見的解法である First-Fit 法を基本とした発見的解法
を空に初期化する. 初めのパター
INIT を提案する. INIT を実行する前に全使用パターン
ン
では, 全製品 $i\in M$ を注文数 の降順に整列した後に順番に割当てる. 以降の各パターンの昇順で整列した後に順番に$p_{j}(j\geq 2)$ では, 全製品 $i\in M$ をこれまでに現れた回数\lambda iに各製品 $i\in M$ を 1 個ずつしか割当てないので, 母材長に対割当てる. INIT は各パターン
して各製品長が小さい場合には各パターンに大きな切残しができる. 以下にアルゴリズム INIT を$pj\in\text{ }$$d_{i}$$p_{1}$$= \sum_{q=1}^{j-1}a_{\dot{\iota}q}$$Pj\in \mathrm{I}\mathrm{I}$示す. ここで$L_{j}^{res}$はパターン $pj$ の切残し長を表す.

アルゴリズ\Delta INIT

入力:. 各製品の長さ$l_{i}$と注文数$d_{1}.$, 使用パターン数 , 母材長
$n$

$L$

.

出力: 使用パターン集合 n $=\{p_{1},p_{2}, \ldots,p_{n}\}$ .

Step 1: 全パターン $pj\in$兇魘 (こする $(\forall ia_{1j}.:=0)$ . $j:=1,$ $L^{res}:=L$ とする.

Step 2: $j=1$ ならば全製品 $i\in M$ を注文数 の降順に整列する. そうでなければ, 全を整列後の k 番目の昇順に整列する.
製品 $i\in M$ を出現回数\lambda |.
の製品とする. $k:=1$ とする.
$d_{i}$$\sigma(k)$$= \sum_{q=1}^{j-1}a_{iq}$Step 3:$l_{\sigma(k)}\leq L_{j}^{res}$

ならば $a_{\sigma(k)j}:=1,$$L_{j}^{res}:=L_{j}^{r\mathrm{e}s}-l_{\sigma(k)}$とする.

$k<m$ ならぼ

$k:=k+1$ として Step 3 に戻る.

. そうでなけれぼ, $j:=j+1$
Step 4: $j=n$ ならば使用パターン集合 兇鮟侘呂靴峠 了として Step 2 に戻る.

22

パターン生成提案する局所探索法では, 使用パターン集合垣の探索に, 以下に示す 1 パターン入替え近傍 $N$ (垣)$\text{を}$ffl$\mathrm{A}\mathrm{a}\text{る}$

.

,

(4)

$N(\text{ })=\{\mathrm{I}\mathrm{I}\mathrm{U}\{p(i’,j’)\}\backslash \{pj\}|pj’\in \mathrm{I}\mathrm{I}, i’\in M’(\mathrm{I}\mathrm{I})\}$$p(i’,j’)$ は後で説明するアルゴリズム PATGEN で生或されるパターンを表す.

また,$M’(\mathrm{I}\mathrm{I})$は製品集合 M の部分集合で, 以下の式 (5) で定義される.
$M’(\text{ })=\{i|\overline{y}_{i}>0, i\in M\}$

ここで,
ある.

$\overline{\mathrm{Y}}=\{\overline{y}_{1},\overline{y}_{2}, \ldots,\overline{y}_{m}\}$は以下に示す線形計画問題(DLP(II))$\max$$\mathrm{s}.\mathrm{t}$.

.

$\mathrm{L}\mathrm{P}(\text{ })$(5)の双対問題 DLP(II) の最適解で(6)$\sum_{i=1}^{m}d_{1}.y_{i}$.

$\sum_{i=1}^{m}a:jy_{1}$$y_{i}\geq 0,$$\leq 1$

, for

$pj\in\text{ }$for $i\in M$ .

及び $(i’,j’)$ を人力とし, パターン $Pj’\in$
パターン生或アルゴリズム PATGEN は暫定解を変更して得られるパターン候補 $p(i’,j’)$ を出力する. まず, パターン p.j’ 内の製品 i’ を 1 増やし,$(\text{ }, X)$

119の値で整列し,式 (2) を満たすならぼ終了. そうでなければ I 以外の製品をから式 (2) を満すまで順に 1 ずつ減らす. 以下の式 (7) を満たすならば終了.

$\ovalbox{\tt\small REJECT}_{i}/l_{i}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}_{i}$の小さ$\nu\backslash$(7)$L- \sum_{i\in M}a_{ij}l_{i}<\min_{i\in M}l_{i}$

そうでなければ,$\overline{y}_{i}/l_{i}$製品の大きい順に式 (2) の制約のもとで製品

$i$

を加える.

アルゴリズム PATGEN

入力: 製品 $i’\in M$ , パターン $pj’=(a_{1j’}, a_{2j’}, \ldots, a_{mj’})$ , 各製品の長さ
使用パターン数 , 母材長 L. 双対問題 DLP(II) の最適解–Yと注文数$d_{i}$$=\{\overline{y}_{1},\overline{y}_{2}, \ldots,\overline{y}_{m}\}$$n$

製品集合 M’($l_{i}$,,)M.

出力: パターン $p(i’,j’)=(a_{1j}’,, a_{2j}’,, \ldots, a_{mj}’,)$ .

Step 1: 全製品 $i\in M$ を$\overline{y}_{i}/l_{i}$の降順に整列する.

$\sigma(k)$を整列後の k 番目の製品とする.

$k:=1$ とする.

Step 2:$a_{i’j}’,$$:=a_{i’j’}+1,$$a_{ij}’,$$:=a_{\dot{\iota}j’}(\forall i\neq i’)$とする. $L^{res}:=L- \sum_{i\in M}a_{ij}’$ , とする.

Step 3: $L^{res}\geq 0$ ならぱ $k:=m$ として Step 5 へ行く. そうでない場合 $k>m$ ならば終了.
Step 4: (7(k)\neq i’ かつ$a_{\sigma(k)j}’,$$>0$ ならぽ,$a_{\sigma(k)j}’,$$:=a_{\sigma(k)j}’,$$-1,$ $L^{res}:=L^{res}+l_{\sigma(k)}$ とする. $k:=k+1$ として Step 3 に戻る.

Step 5:$l_{\sigma(k)}\leq L^{res}$ならば$a_{\sigma(k)j}’,$$:=a_{\sigma(k)j}’,$$+1,$ $L^{res}:=L^{res}-l_{\sigma(k)}$. $k>1$ なら$[] \mathrm{f}^{\backslash }$$k:=k-1$ として Step 5 に戻る, そうでなけれぼパターン $p(i’,j’)$ を出力して
終了.

2.3

線形計画問題を解く必要を評価するたびに線形計画問題
提案する局所探索法では, 近傍解 ’を解くたびに単体表を作り直す必要があがあるため, 単体法をそのまま適用したのでは,$X$ を計算する際にり計算効率が悪い. そこで, 本研究では暫定解 兇砲 ける各パターンの適用回数
得られた単体表 T から, 近傍解 ’ に対する単体表 T’ を生或し, これに対して線形計画法の一種である十文字法 [4] を適用して, 近傍解垣’ の各パターンの適用回数 X’ を計算する.
T の基底変数に対する列集合を $B$ , コスト係数 , 非基底変数に対する暫定解 兇砲 ける単体表$B^{-1}$
列集合を $N$ , コスト係数$cN$ とする. 新たな単体表 T’ は, 22 節で生或したパターン $p(i’,j’)$ にを掛けて得られる列 $\tilde{p}(",j’)=B^{-1}p(i’,j’)$ を $N$ に加えた後, これとパターン $Pj’$ に対応する列入替えるピボット操作を適用することで得られる. この時, パターン $Pj’$ に対応する相対コストと計算できる. 得られた単体表 T’ は必ずしも実行可能で [よなは d\tilde j’が, 任意の単体表から最適解に収束する性質を持つ十文字法 [4] を適用する事で, 近傍解 ’ に対す$\mathrm{L}\mathrm{P}(\text{ ^{}\prime})$$\in N(\text{ })$$\mathrm{L}\mathrm{P}(\text{ ^{}\prime})$$c_{B}$$\text{を}$$\tilde{p}j’$$d_{j’}^{\sim}$$\mathrm{A}\mathrm{a}$$= \tilde{c}j’-\sum_{i\in M}\overline{y}_{i}(a_{ij}’, -aij’)$

る単体表 P が得られる.
アルゴリズム SOLVE-LP

入力:$\mathrm{L}\mathrm{P}(\text{ })$の最適解–X$=\{\overline{x}_{1},\overline{x}_{2}, \ldots,\overline{x}_{n}\}$$p(i’,j’)=(a_{1j’}’,a_{2j’}’, \ldots, a_{mj’}’)$

出力:LP(垣’) の最適解–X’, 単体表 $T=(B, N,\tilde{c}B,\tilde{c}N)$ .

$J\backslash \mathrm{Q}$.

$=\{\overline{x}_{1}’,\overline{x}_{2}’, \ldots,\overline{x}_{n}’\}$, 単体表$T=(B’, N’,\tilde{c}_{B}’,\tilde{c}_{N}’)$

.

ターン

120
Step 1: 列 $\tilde{p}(i’, j’):=B,$$\overline{x}_{j}’,$$:=0,\tilde{c}_{j}’,$$:= \tilde{c}j’-\sum_{i\in M}\overline{y}_{i}(a_{ij’}’-a_{ij’})$を単体表 T の非基底列集合 N に加える.

入れ替えた後, 十文字法を適用して新たな最適解–X’ およびその単体表 $T’$ を得て終了.

Step 2: ピボット操作を施し列

24$\tilde{p}(i’,j’)$と$\tilde{p}j^{\prime \text{を}}$局所探索法

本節では 21-23 節の INIT, PATGEN, SOLVE-LP を用いた局所探索法の概要をまとめる. ( , $X$ )を暫定解とする. 提案する局所探索法では, 暫定解 兇龍疔に改善解 ’ が見つかった場合には,即座に暫定解 兇魏 善解’ で置き換える. また, 解を評価する指標として目的関数 f( , $X$ ) 以外に, 余
剰製品数の合計 over( , $X$ ) $= \max\{0,\sum:\epsilon Maijxj-di\}$ を用いる. つまり, f( ’, X’)<f( , $X$ ),もしくは f( ’, $X’$ ) $=f(\text{ },X)$ かつ over(II’, $X’$ ) $<over(\text{ },X)$ を満す近傍解 ( ’, $X’$ ) を改善解と見なす.
$N(\mathrm{I}\mathrm{I})$アルゴリズム LS

入力: 各製品の長さ$l_{i}$と注文数$d_{1}.$, 使用パターン数 , 母材長
$n$

$L$

.

出力: 使用パターン集合 n $=\{p_{1},p_{2}, \ldots,p_{n}\}$ , 各パターンの適用回数 $X=\{x_{1}, x_{2}, \ldots, x_{n}\}$ .

Step 1: アルゴリズム INIT を適用して初期使用パターン集合\Gamma I $=\{p_{1},p_{2}, \ldots,p_{n}\}$ を得る. SOLVE-LP を適用して各パターンの適用回数 $X=\{x_{1}, x_{2}, \ldots, x_{n}\}$ を得る. 実行不可能解が出力されたら終了. $i^{*}:=1,$ $j^{*}:=1,$ $i’:=i^{*},$ $j’:=j^{*}$ とする.
Step 2:
生或し,$i’\in M’(\mathrm{I}\mathrm{I})$’ならぼ, アノレゴリズム PATGEN を適用してパターン $p(i’,j’)$ をとする. そうでなけれぼ Step 5 に行く.

$=\mathrm{I}\mathrm{I}\cup\{p(i’,j’)\}\backslash \{Pj^{\prime\}}$Step 3: 使用パターン集合 ’ に対してアルゴリズム SOLVE-LP を適用して, 各パターンの適用回数 $X=\{x_{1}, x_{2}, \ldots, x_{n}\}$ を求める. アルゴリズム SOLVE-LP が実行
不可能解を出力した場合は Step 5 へ行く.

Step 4: $f(\text{ ^{}\prime},X’)<f(\text{ }, X)$ , もしくは f( ’, X’)=f( , $X$ ) かつ over( ’, $X’$ )$i^{*}:=i^{*}+1$ (mod $m$ ), $j^{*}:=j^{*}+$over( , $X$ ) ならば, ( , $X$ )$i’:=i$ “, $j’:=j^{*}$ として Step 2 に戻る.
1$<$$:=(\mathrm{I}\mathrm{I}’, X’),$$(\mathrm{m}\mathrm{o}\mathrm{d} n),$Step 5: $i’:=i’+1$ (mod $m$ ) とする.
=i\sim 全ての e が走査済み) ならば, $j’:=$をとする. $j’$ =j’(全ての , J が走査済み) ならば, 暫定解
出力して終了, そうでなければ Step 2 へ戻る.
$i’$

$i’$

$j’+1(\mathrm{m}\mathrm{o}\mathrm{d} n)$3$(\text{ }, X)$

数値実験

例題生或アルゴリズム CUTGEN[2] により様々な問題例を作或した. CUTGEN は入カパラメー
タに $L,$
は母材に対する各製品長の割合, d-は各製品の注文数の, d-を持ち, は母材長,平均を表す. 本実験では, 入カパラメータを組合せて 18 クラスの問題例 (各クラス 100 題) を作或$\nu_{1},$$L$$\nu_{2}$$[\nu_{1},\nu_{2}]$, $m=10,20,40,\overline{d}=10,100$ , クラス 1-6 では $(\nu_{1}, \nu_{2})=(0.01,0.2)$ , クラ
ス 7-12 では $(\nu_{1},\nu_{2})=(0.01,0.8)$ , クラス 13-18 では $(\nu_{1}, \nu_{2})=(0.2,0.8)$ と設定した.
した. ここで,$L=1\mathrm{O}\mathrm{O}\mathrm{O}$

まず, 23 節で提案した十文字法を用いた手法の評価を行った. 局所探索法 1 回の実行の間に, 線を解くのに要したピボット操作の平均回数を, 改訂単体法と提案する十文字法
形計画問題$\mathrm{L}\mathrm{P}(\mathrm{I}\mathrm{I})$121
を用いた方法で比較を行った (表$\mathfrak{y}$. 表 1 に示す様に, 改訂単体法は製品数にほぼ比例したピボッ

ト回数を要しているのに比較して, 提案手法ではほとんどの問題例において 1-2 回のピボット操作
で最適解に収束している.

次に, 提案解法 LS とパターン数最小化を考慮した発見的解法である SHP[3], KOMBI[I] との比較を行った. SHP は使用パターンを逐次生或するアルゴリズムである. SHP はパターン候補を列挙した後に, 残り需要をなるべく満しかつ適用回数が大きくなるパターンを発見的に選択して割当
てる. KOMBI は使用パターン数制限の無いカッティングストック問題に対する近似解を初期解として, 複数の使用パターンを繰り返し併合する事で使用パターン数を最小化する. SHP と LS は
AT 互換機 (Pentium III lGHz, IGB Memory) 上で実行した. KOMBI の結果については文献 [1]から引用した. 1 節で述べたように, LS において使用パターン数 l よ入カパラメータとして与えられる. 本実験では, 使用パターン数 $n=\beta,$ $\beta-1,\beta-2$ について LS を実行した.
は以下の式で与$n$$\beta$えられる.
$\beta=\min\{n_{shp}, n_{shp}-\lceil\overline{n}_{shp}-\overline{n}_{k\circ mbi}\rceil\}$,

ここで $n_{shp},$ $n_{kombi}$ は各例題に対して SHP, KOMBI を適用して得られる使用パターン数を,$\overline{n}kombi$(8)$\overline{n}_{\epsilon hp}$,

はそれらの 100 例題での平均値を表す.

の計算実験結果を示す. 表中の (95/100) 等は LS を 100 例題に実行した際に 95 例題において実行可能解が得られた事を表す. 表 2 より, KOMBI を適用して得られる使のそれより少ない事が確かめられる. これは, KOMBI が使用パターン数
用母材の本数は,制限の無いカッティングストック問題の近似解を初期解としているためである. 一方で, LS は入カパラメータである使用パターン数 を変える事により, 様々な使用パターン数において近似解を得ることができる利点がある.
表 2に$\mathrm{S}\mathrm{H}\mathrm{P},\mathrm{K}\mathrm{O}\mathrm{M}\mathrm{B}\mathrm{I},\mathrm{L}\mathrm{S}$$\mathrm{S}\mathrm{H}\mathrm{P},\mathrm{L}\mathrm{S}$

$n$

122

次に, 表 2 において各解法の計算に要した時間を表 3 に示す. LS は n=\beta の場合の計算時間を示す. 使用計算機の速度を考慮すると SHP, KOMBI の方が LS よりも短時間で解を得ている. しかし,$\mathrm{L}\mathrm{S}$でも 300 秒以内に解を得ることが可能であり実用上十分な性能だと考えられる.

123

4

まとめ

過去の素材産業では材料費が総費用の大半を占めていたため, 使用母材の本数を最小化する定式化に基づく手法が多く提案されてきた. しかし, 近年では材料費の定価に伴い, 段取り替えによって生じる費用の削減が重要視されている. そこで本研究では, あらかじめ与えられた段取り替え数(パターン数) の元で, 使用母材の本数を最小化するカッテイングストツク問題に対して, 1 パターン入れ替え近傍に基づく局所探索法を提案した. カツテイングストツク問題では, 近傍解の構或要
素である実行可能なパターンが莫大な数に及ぶ. そこで, 提案解法では子問題の線形計画問題から得られる相対コストの情報を用 いて, 改善解を構或できるパターン候補のみを用いた近傍を定義した. また, 近傍解ごとに子問題の線形計画問題を繰り返し解く必要があるため, 本研究では, 暫定解に対する単体表を利用して線形計画問題を高速に解く方法を提案した. 最後に数値実験を行い, 他$\circ$の発見的解法には若干劣るものの様々な使用パターン数に対して良好な精度を持つ解が得られる
事が確かめられた.

参考文献[1] H. Foerster and G. Wicher, Pattern reduction in one-dimensional cutting stock problems,, pp.1657-1676, 2000.
International Journal of Production Research,$\mathrm{v}\mathrm{o}\mathrm{l}.38$

124[2] T. Gau and G. Wischer, CUTGENI: aproblem generator for the standard one-dimensional, pp.572-579, 1995.
cutting stock problem, European Journal of Operational Research,$\mathrm{v}\mathrm{o}\mathrm{l}.84$[3] LE. Haessler, Controlling cutting pattern changes in one-dimensional trim problems, Op.
erations Research,$\mathrm{v}\mathrm{o}\mathrm{l}.23,$$\mathrm{p}\mathrm{p}.483-493,1975$[4] S. Zionts, The criss-cross method for solving linear programming problems, Management, 1969.
Science,$\mathrm{v}\mathrm{o}\mathrm{l}.15,$$\mathrm{p}\mathrm{p}.426-445$