(57)【要約】【課題】組み合わせの良い割り付けを先取りする割り付け計算法で後半の割付け結果を改善する。【解決手段】割り付け対象製品を２以上のグループに分割するグループ分け手段２１と、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りする割り付けを実行する第一仮割り付け手段２２と、仮割り付けが終了したグループについて、各グループの後半の割り付け結果を解体する部分解体手段２３と、解体されて未割り付けとなった製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行う第二仮割り付け手段２４と、全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力する割り付け結果出力手段２５とを備えた。【選択図】図１
2011100303.tif 000002
【特許請求の範囲】
【請求項１】
割り付け対象製品を２以上のグループに分割するグループ分け手段と、
各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをする第一仮割り付け手段と、
前記仮割り付けが終了したグループについて、前記先取りした良い割り付け結果を得た材料を除くいずれかの材料についての割り付け結果を解体する部分解体手段と、
解体されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して仮割り付けを行う第二仮割り付け手段と、
前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力する割り付け結果出力手段とを備えたことを特徴とする材料取り合わせシステム。
【請求項２】
割り付け対象製品を２以上のグループに分割するグループ分け手段と、
各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをする第一  仮割り付け手段と、
前記各グループについて、前記仮割り付けが終了する直前で前記仮割り付けを中断する割り付け中断制御手段と、
前記仮割り付けが中断されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行う第二仮割り付け手段と、
前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力する割り付け結果出力手段とを備えたことを特徴とする材料取り合わせシステム。
【請求項３】
請求項１に記載の材料取り合わせシステムにおいて、
前記部分解体手段は、前記仮割り付けが終了したグループについて、最後から数えてＰ番目の材料に製品を割り付けたところまで遡って、遡った部分の割り付け結果を解体することを特徴とする材料取り合わせシステム。
【請求項４】
請求項２に記載の材料取り合わせシステムにおいて、
前記中断制御手段は、前記各グループについて、最初から数えてＱ番目の材料に製品を割り付けたところで製品の仮割付けを中断することを特徴とする材料取り合わせシステム。
【請求項５】
請求項１に記載の材料取り合わせシステムにおいて、
前記部分解体手段は、前記仮割り付けが終了したグループについて、最後から数えてｍ番目の製品を割り付けたところまで遡って、遡った部分の割り付け結果を解体することを特徴とする材料取り合わせシステム。
【請求項６】
請求項２に記載の材料取り合わせシステムにおいて、
前記部分解体手段は、前記仮割り付けが終了したグループについて、最初から数えてｎ番目の製品を割り付けたところで製品の仮割付けを中断することを特徴とする材料取り合わせシステム。
【請求項７】
請求項１に記載の材料取り合わせシステムにおいて、
前記仮割り付けが終了したグループについて、割り付け済みの材料の材料毎の歩留まりを比較して、材料歩留の低い材料から順に、予め決められた数の材料について、割り付け結果を解体することを特徴とする材料取り合わせシステム。
【請求項８】
請求項１乃至７のいずれかに記載の材料取り合わせシステムにおいて、
前記部分解体手段は、未割り付けとなった複数のグループに属する製品の数の総和が、分割された各グループに属していた製品の数と近似するように、割り付け結果を解体することを特徴とする材料取り合わせシステム。
【請求項９】
請求項１乃至８のいずれかに記載の材料取り合わせシステムにおいて、
前記グループ分け手段は、前記分割されたグループ数を２以上４以下とすることを特徴とする材料取り合わせシステム。
【請求項１０】
請求項１乃至９のいずれかに記載の材料取り合わせシステムにおいて、
前記グループ分け手段は、各グループに属する製品を割り付け対象製品の中からランダムに選択して、前記第一仮割付け手段は、前記各グループ毎に得られた仮割付け結果を記憶装置に記憶させるという動作を、各グループに属する製品を変更しながら複数回試行し、
前記結果出力手段は、前記複数回の試行のうち最も良い割付け結果が得られたものを最終結果として取り出すことを特徴とする材料取り合わせシステム。
【請求項１１】
請求項１０に記載の材料取り合わせシステムにおいて、
前記試行回数を前記割り付け対象製品の数の２倍以上３倍以下としたことを特徴とする材料取り合わせシステム。
【請求項１２】
請求項１乃至１１のいずれかに記載の材料取り合わせシステムにおいて、
前記部分解体手段と前記第二仮割付け手段は、前記各グループの仮割付け結果の一部を解体して新たなグループを作り、この新たなグループについて割付けを実行する動作を、前記仮割付け結果を解体する範囲を変えて複数回実行し、前記割付け結果出力手段は、得られた複数の割付け結果のうちの最も良い割付け結果を出力することを特徴とする材料取り合わせシステム。
【請求項１３】
請求項１乃至１２のいずれかに記載の材料取り合わせシステムにおいて、
前記第一仮割付け手段は、
割り付け対象製品の中から最も長い製品を選択し、この製品を割り付けることができる材料を選択して仮割り付けをし、この材料の残りの部分に対して、残りの未割り付け製品の中から総当りで最も材料の残りが少なくなるような製品の組み合わせを見つけ、この製品を仮割付けし、この仮割り付け結果を保存し、前記割り付け対象製品の中から最初にとりだした最も長い製品を割り付けることができる全ての材料について、同様にして仮割り付けと仮割り付け結果の保存処理を実行し、複数の仮割り付け結果が得られたら、それらを比較して、最も歩留まりの良い仮割り付け結果を選択し、その結果から、材料とその材料に割り付けた製品とを示す割り付け結果を得て、その後、残りの未割り付け対象製品について同様の割り付け結果を得る処理を繰り替えして、全ての製品についての割り付け結果を求めるという方法で仮割付けを行うことを特徴とする材料取り合わせシステム。
【請求項１４】
請求項１乃至１３のいずれかに記載の材料取り合わせシステムにおいて、
前記分割前の割り付け対象製品について、任意の方法を使用して最後まで割り付けを行い、その割付け結果を保存し、
前記結果出力手段は、前記グループの分割により得た割付け結果と比較して、良い方を最良の割り付け結果として出力することを特徴とする材料取り合わせシステム。
【請求項１５】
請求項１乃至１４のいずれかに記載の材料取り合わせシステムにおいて、
前記結果出力手段は、前記第一仮割付け手段による前記仮割り付けが終了した全てのグループについて、材料とその材料に割り付けた製品とを示す全ての割り付け結果を集めて、全体としての割付け結果を求め、前記第二仮割付け手段による仮割付けが終了して得られた割付け結果と比較して、良い方を最良の割り付け結果として出力することを特徴とする材料取り合わせシステム。
【請求項１６】
請求項１乃至１５のいずれかに記載の材料取り合わせシステムにおいて、
前記第一仮割付け手段または前記第二仮割付け手段は、前記最も良い割付け結果かどうかを判定する基準を、全ての材料から全ての製品を切り出した残りの残材量の総和が最小となる場合、もしくは最小値に近い場合とすることを特徴とする材料取り合わせシステム。
【請求項１７】
請求項１乃至１５のいずれかに記載の材料取り合わせシステムにおいて、
前記第一仮割付け手段または前記第二仮割付け手段は、最も良い割付け結果かどうかを判定する基準を、全ての材料から全ての製品を切り出した残りの残材量の総和が最小値に近いとき、最も長い残材が存在する場合とすることを特徴とする材料取り合わせシステム。
【請求項１８】
コンピュータを、請求項１に記載の手段を備えたシステムとして機能させる材料取り合わせプログラム。
【請求項１９】
コンピュータを、請求項２に記載の手段を備えたシステムとして機能させる材料取り合わせプログラム。
【請求項２０】
コンピュータを、請求項１に記載の手段を備えたシステムとして機能させる材料取り合わせプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項２１】
コンピュータを、請求項２に記載の手段を備えたシステムとして機能させる材料取り合わせプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項２２】
グループ分け手段が、割り付け対象製品を２以上のグループに分割するステップと、
第一仮割り付け手段が、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをするステップと、
部分解体手段が、前記仮割り付けが終了したグループについて、前記先取りした良い割り付け結果を得た材料を除くいずれかの材料についての割り付け結果を解体するステップと、
第二仮割り付け手段が、解体されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行うステップと、
割り付け結果出力手段が、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力するステップとを備えたことを特徴とする材料取り合わせ方法。
【請求項２３】
グループ分け手段が、割り付け対象製品を２以上のグループに分割するステップと、
第一仮割り付け手段が、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをするステップと、
中断制御手段が、前記各グループについて、前記仮割り付けが終了する直前で仮割り付けを中断するステップと、
第二仮割り付け手段が、前記仮割り付けが中断されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行うステップと、
割り付け結果出力手段が、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力するステップとを備えたことを特徴とする材料取り合わせ方法。
【請求項２４】
請求項１に記載の割り付け結果を使用して、前記材料を選択する材料選択供給装置と、前記材料から前記製品を切り出す材料切断装置とを備えたことを特徴とするプレカット装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、建材のプレカット工場等で採用される、材料取り合わせシステムと材料取り合わせプログラムと記録媒体と材料取り合わせ方法とプレカット装置に関する。
【背景技術】
【０００２】
住宅構造材のプレカット工場では、断面形状や樹種、等級、レイヤといった仕様ごとにいくつもの種類の長さ（３ｍ〜６ｍ）の原材料が用意される。これらの原材料から求められた長さの部材(製品)を切り出す。一般的な大きさの住宅の場合、梁、桁、土台など横架材と呼ばれる構造材には約２０種類の仕様がある。構造材（製品）の仕様ごとに用意された各種の長さの原材料から、これらの構造材がそれぞれ平均１０本程度、１棟分を合計すると約２００本程度切り出される。製品の長さと原材料の長さの組み合わせにより、原材料から切り落とされて無駄になる残材部分の量が異なる。そこで、原材料から効率の良い組み合わせで製品を切り出すための、材料取り合わせ方法に関する技術が各種開発された（特許文献１参照）（特許文献２参照）（特許文献３参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許３５６５２６２号公報
【特許文献２】特開２００９−１６３７０２号公報
【特許文献３】特開２００９−１１６７１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記のような材料取り合わせ方法の計算の目的は、製品の仕様ごとに用意された何種類かの長さの原材料群から要求製品をいかに無駄なく（歩留まり最高で）切り出すかということにある。既知の、各種の技術を利用したプレカット工場での一次歩留は、一般には概ね９０％程度といわれている。一定の規格で設計生産される建物の場合には、原材料のサイズに適合するように構造材のサイズを決めて、歩留を向上させることができる。しかしながら、注文生産により多種多様の設計に基づき、構造材を原材料から切り出す場合には、できるだけ高い精度で歩留まりを向上させる計算方法の開発が求められている。また、条件によっては、ある計算方法で歩留まりが悪くても、他の計算方法で歩留まりが良いという結果も得られる。コンピュータの性能向上により、演算処理時間は十分に短くなっているから、各種の計算方法を試行して最適な結果を選択すればよい。実際に、１％の歩留まりを向上させるだけでも、多量の廃棄物減量を図ることができる。
【０００５】
ある決められたアイテムの一群を一定の容積のビンに入れる時、ビンの使用数を最小にするというビンパッキング問題はよく知られている。この問題の解法のひとつに、Minimum Bin Slack法と呼ばれる方法がある。一定の容積のビンに最も歩留まりよくアイテムを入れる組み合わせを見付け、続いて、残りのアイテムを別のビンに最も歩留良く入れる。以下すべてのアイテムをビンに入れ終わるまでこれを繰り返す方法である。ここで、問題になるのは、良い割り付けを先取りするという性質上、未割付けのアイテムが残り少なくなったときの歩留まりが悪くなるという点にある。本発明者等は、この問題を解決するために、これまでに、後半の割付けに様々な計算手法を採り入れた解法を開発した。
本発明はさらに、後半の割り付け方法を工夫して、これまで以上に良い結果を得ることができる、材料取り合わせシステムと材料取り合わせプログラムと記録媒体と材料取り合わせ方法とプレカット装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
割り付け対象製品を２以上のグループに分割するグループ分け手段と、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをする第一仮割り付け手段と、前記仮割り付けが終了したグループについて、前記先取りした良い割り付け結果を得た材料を除くいずれかの材料についての割り付け結果を解体する部分解体手段と、解体されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して仮割り付けを行う第二仮割り付け手段と、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力する割り付け結果出力手段とを備えたことを特徴とする材料取り合わせシステム。
【０００７】
〈構成２〉
割り付け対象製品を２以上のグループに分割するグループ分け手段と、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをする第一  仮割り付け手段と、前記各グループについて、前記仮割り付けが終了する直前で前記仮割り付けを中断する割り付け中断制御手段と、前記仮割り付けが中断されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行う第二仮割り付け手段と、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力する割り付け結果出力手段とを備えたことを特徴とする材料取り合わせシステム。
【０００８】
〈構成３〉
構成１に記載の材料取り合わせシステムにおいて、前記部分解体手段は、前記仮割り付けが終了したグループについて、最後から数えてＰ番目の材料に製品を割り付けたところまで遡って、遡った部分の割り付け結果を解体することを特徴とする材料取り合わせシステム。
【０００９】
〈構成４〉
構成２に記載の材料取り合わせシステムにおいて、前記中断制御手段は、前記各グループについて、最初から数えてＱ番目の材料に製品を割り付けたところで製品の仮割付けを中断することを特徴とする材料取り合わせシステム。
【００１０】
〈構成５〉
構成１に記載の材料取り合わせシステムにおいて、前記部分解体手段は、前記仮割り付けが終了したグループについて、最後から数えてｍ番目の製品を割り付けたところまで遡って、遡った部分の割り付け結果を解体することを特徴とする材料取り合わせシステム。
【００１１】
〈構成６〉
構成２に記載の材料取り合わせシステムにおいて、前記部分解体手段は、前記仮割り付けが終了したグループについて、最初から数えてｎ番目の製品を割り付けたところで製品の仮割付けを中断することを特徴とする材料取り合わせシステム。
【００１２】
〈構成７〉
構成１に記載の材料取り合わせシステムにおいて、前記仮割り付けが終了したグループについて、割り付け済みの材料の材料毎の歩留まりを比較して、材料歩留の低い材料から順に、予め決められた数の材料について、割り付け結果を解体することを特徴とする材料取り合わせシステム。
【００１３】
〈構成８〉
構成１乃至７のいずれかに記載の材料取り合わせシステムにおいて、前記部分解体手段は、未割り付けとなった複数のグループに属する製品の数の総和が、分割された各グループに属していた製品の数と近似するように、割り付け結果を解体することを特徴とする材料取り合わせシステム。
【００１４】
〈構成９〉
構成１乃至８のいずれかに記載の材料取り合わせシステムにおいて、前記グループ分け手段は、前記分割されたグループ数を２以上４以下とすることを特徴とする材料取り合わせシステム。
【００１５】
〈構成１０〉
構成１乃至９のいずれかに記載の材料取り合わせシステムにおいて、前記グループ分け手段は、各グループに属する製品を割り付け対象製品の中からランダムに選択して、前記第一仮割付け手段は、前記各グループ毎に得られた仮割付け結果を記憶装置に記憶させるという動作を、各グループに属する製品を変更しながら複数回試行し、前記結果出力手段は、前記複数回の試行のうち最も良い割付け結果が得られたものを最終結果として取り出すことを特徴とする材料取り合わせシステム。
【００１６】
〈構成１１〉
構成１０に記載の材料取り合わせシステムにおいて、前記試行回数を前記割り付け対象製品の数の２倍以上３倍以下としたことを特徴とする材料取り合わせシステム。
【００１７】
〈構成１２〉
構成１乃至１１のいずれかに記載の材料取り合わせシステムにおいて、前記部分解体手段と前記第二仮割付け手段は、前記各グループの仮割付け結果の一部を解体して新たなグループを作り、この新たなグループについて割付けを実行する動作を、前記仮割付け結果を解体する範囲を変えて複数回実行し、前記割付け結果出力手段は、得られた複数の割付け結果のうちの最も良い割付け結果を出力することを特徴とする材料取り合わせシステム。
【００１８】
〈構成１３〉
構成１乃至１２のいずれかに記載の材料取り合わせシステムにおいて、前記第一仮割付け手段は、割り付け対象製品の中から最も長い製品を選択し、この製品を割り付けることができる材料を選択して仮割り付けをし、この材料の残りの部分に対して、残りの未割り付け製品の中から総当りで最も材料の残りが少なくなるような製品の組み合わせを見つけ、この製品を仮割付けし、この仮割り付け結果を保存し、前記割り付け対象製品の中から最初にとりだした最も長い製品を割り付けることができる全ての材料について、同様にして仮割り付けと仮割り付け結果の保存処理を実行し、複数の仮割り付け結果が得られたら、それらを比較して、最も歩留まりの良い仮割り付け結果を選択し、その結果から、材料とその材料に割り付けた製品とを示す割り付け結果を得て、その後、残りの未割り付け対象製品について同様の割り付け結果を得る処理を繰り替えして、全ての製品についての割り付け結果を求めるという方法で仮割付けを行うことを特徴とする材料取り合わせシステム。
【００１９】
〈構成１４〉
構成１乃至１３のいずれかに記載の材料取り合わせシステムにおいて、前記分割前の割り付け対象製品について、任意の方法を使用して最後まで割り付けを行い、その割付け結果を保存し、前記結果出力手段は、前記グループの分割により得た割付け結果と比較して、良い方を最良の割り付け結果として出力することを特徴とする材料取り合わせシステム。
【００２０】
〈構成１５〉
構成１乃至１４のいずれかに記載の材料取り合わせシステムにおいて、前記結果出力手段は、前記第一仮割付け手段による前記仮割り付けが終了した全てのグループについて、材料とその材料に割り付けた製品とを示す全ての割り付け結果を集めて、全体としての割付け結果を求め、前記第二仮割付け手段による仮割付けが終了して得られた割付け結果と比較して、良い方を最良の割り付け結果として出力することを特徴とする材料取り合わせシステム。
【００２１】
〈構成１６〉
構成１乃至１５のいずれかに記載の材料取り合わせシステムにおいて、前記第一仮割付け手段または前記第二仮割付け手段は、前記最も良い割付け結果かどうかを判定する基準を、全ての材料から全ての製品を切り出した残りの残材量の総和が最小となる場合、もしくは最小値に近い場合とすることを特徴とする材料取り合わせシステム。
【００２２】
〈構成１７〉
構成１乃至１５のいずれかに記載の材料取り合わせシステムにおいて、前記第一仮割付け手段または前記第二仮割付け手段は、最も良い割付け結果かどうかを判定する基準を、全ての材料から全ての製品を切り出した残りの残材量の総和が最小値に近いとき、最も長い残材が存在する場合とすることを特徴とする材料取り合わせシステム。
【００２３】
〈構成１８〉
コンピュータを、構成１に記載の手段を備えたシステムとして機能させる材料取り合わせプログラム。
【００２４】
〈構成１９〉
コンピュータを、構成２に記載の手段を備えたシステムとして機能させる材料取り合わせプログラム。
【００２５】
〈構成２０〉
コンピュータを、構成１に記載の手段を備えたシステムとして機能させる材料取り合わせプログラムを記録したコンピュータで読み取り可能な記録媒体。
【００２６】
〈構成２１〉
コンピュータを、構成２に記載の手段を備えたシステムとして機能させる材料取り合わせプログラムを記録したコンピュータで読み取り可能な記録媒体。
【００２７】
〈構成２２〉
グループ分け手段が、割り付け対象製品を２以上のグループに分割するステップと、第一仮割り付け手段が、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをするステップと、部分解体手段が、前記仮割り付けが終了したグループについて、前記先取りした良い割り付け結果を得た材料を除くいずれかの材料についての割り付け結果を解体するステップと、第二仮割り付け手段が、解体されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行うステップと、割り付け結果出力手段が、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力するステップとを備えたことを特徴とする材料取り合わせ方法。
【００２８】
〈構成２３〉
グループ分け手段が、割り付け対象製品を２以上のグループに分割するステップと、第一仮割り付け手段が、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをするステップと、中断制御手段が、前記各グループについて、前記仮割り付けが終了する直前で仮割り付けを中断するステップと、第二仮割り付け手段が、前記仮割り付けが中断されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作り、この新たなグループに属する製品について、任意の割り付け方法を使用して割り付けを行うステップと、割り付け結果出力手段が、前記全てのグループの割り付け済みの製品とそれを割り付けた材料とを示す割り付け結果を出力するステップとを備えたことを特徴とする材料取り合わせ方法。
【００２９】
〈構成２４〉
構成１に記載の割り付け結果を使用して、前記材料を選択する材料選択供給装置と、前記材料から前記製品を切り出す材料切断装置とを備えたことを特徴とするプレカット装置。
【発明の効果】
【００３０】
〈構成１の効果〉
割り付け対象製品を２以上のグループに分割して、これらに組み合わせの良い割り付けを先取りする割り付け計算法を適用し、しわ寄せがきた最後のほうの割り付け結果を解体して集めて再割り付けをすると、より良い割り付け結果を得ることが可能になる。
〈構成２の効果〉
仮割付けを最後まで行わず、所定のタイミングで仮割り付けを中断する。しわ寄せがきた最後のほうの仮割付けを中断して、未割り付け製品を集めて新たな割付けをすると、より良い割り付け結果を得ることが可能になる。
〈構成３の効果〉
解体を材料単位で行う場合には、最後から数えてＰ番目の材料までとすれば、仮割付けの最後に近い段階で使用される材料の割付け結果を改善できる。
〈構成４の効果〉
最初から数えてＱ番目の材料に製品を割り付けたところで仮割付けを中断することもできる。
〈構成５の効果〉
各グループについての仮割付けを進めて、最後から数えてｍ番目の製品付近まで割り付け結果を解体すればよい。
〈構成６の効果〉
各グループについての仮割付けを進めて、最後に近い適当な数の製品までの割付けで割付けを中断すればよい。
〈構成７の効果〉
必ずしも最後から順番に割り付け結果を解体する必要はない。歩留まりの悪い材料を選択して解体すると、全体として歩留まりを改善できる。
〈構成８の効果〉
当初の分割されたグループに属する製品数は、所定の演算法で仮割付けをするのに適した数に選定される。従って、未割り付けとなった製品による新たなグループに属する製品数も、この数量に近似することが好ましい。
〈構成９の効果〉
分割数が多いと演算処理時間が長時間になる。また、各グループに属する製品数が少なくなると、最初のほうでみつかるべき製品の良い組み合わせが見つからなくなる。分割されたグループ数を２以上４以下にすると、実用性が高い。
〈構成１０の効果〉
グループ分けの結果は割付け結果に影響を及ぼす。従って、各グループに属する製品をランダムに選択して、各グループに属する製品を変更しながら複数回実行して、最も良い結果が得られるものを探すようにするとよい。
〈構成１１の効果〉
試行回数が多すぎると演算処理時間が長くなる。割り付け対象製品の数の２倍〜３倍試行すると、十分な結果が得られることがわかった。
〈構成１２の効果〉
解体数によっても割付け結果が異なることがあるから、解体数を変更しながら複数回計算をして、その結果のうち最良のものを得るようにした。
〈構成１３の効果〉
この方法は最初のほうに良い割付けがくる典型的な方法である。その最後のほうの割付け結果を改善すれば、全体としてよりよい割付け結果が得られる。
〈構成１４の効果〉
分割前の割り付け対象製品について全く別の方法で割り付けをした場合に、良い結果が得られるなら、それを採用すればよい。
〈構成１５の効果〉
分割をして仮割付けをした結果が最良という場合もあり得るので、比較評価の対象に加えた。
〈構成１６の効果〉
残材量の総和が最小となる場合とは、歩留まりが最大という基準に該当する。また、最小値に近いという場合も含めると、判定条件が緩和されて、演算時間を短縮することができる。
〈構成１７の効果〉
残材量の総和が最小値に近い場合に、同じ量の残材が生じても、長い残材を残す割付けをすると、その残材は別の用途に使用でき、無駄を少なくできる。
【図面の簡単な説明】
【００３１】
【図１】本発明の材料取り合わせシステムの実施例を示す機能ブロック図である。
【図２】材料取り合わせシステムの本体制御部の内部ブロック図である。
【図３】RMBS法の動作説明図である。
【図４】RMBS法の動作説明図である。
【図５】R-RMBS法の説明図である。
【図６】記憶装置に記憶された実施例のデータ構造説明図である。
【図７】システムの初期値計算処理動作例フローチャートである。
【図８】グループ分け手段の動作フローチャートである。
【図９】システムのメインルーチンの動作フローチャートである。
【図１０】グループの解体処理の動作フローチャートである。
【図１１】グループの仮割り付け中断処理の動作フローチャートである。
【図１２】具体的な実行結果の比較データである。
【図１３】具体的な実行結果の比較データである。
【図１４】住宅プレカット問題の説明図である。
【図１５】具体的な実行結果の比較データである。
【発明を実施するための形態】
【００３２】
過去に、材料取り合わせの最適化のために、firstfit法、bestfit法、MBS法といった各種の方法が開発されている。例えば、 MBS(Minimum Bin Slack)法は、材料単位に総当りで製品を割付けていく方法である。
【００３３】
典型的な方法を例示する。初めに、複数の割り付け対象製品と、それを割付けるための複数種類（長さ）の材料とを用意する。材料はどの長さのものも十分に供給できるようにしておく。そして、対象製品の中から最も長い製品を選択し、この製品を割り付けることができる材料を選択して仮割り付けをする。この材料に対して、残りの未割り付け製品の中から選択した、割り付け可能な最も長い製品を仮割り付けする。この処理を、割り付け可能な製品がなくなるまで繰り返してこの仮割り付け結果を保存する。割り付け対象製品の中から最初にとりだした最も長い製品を割り付けることができる全ての材料について、同様にして仮割り付けと仮割り付け結果の保存処理を実行する。複数の仮割り付け結果が得られたら、それらを比較して、最も歩留まりの良い仮割り付け結果を選択する。そして、その結果から、材料とその材料に割り付けた製品とを示す割り付け結果を得る。その後、残りの未割り付け対象製品について同様の割り付け結果を得る処理を繰り替えす。全ての製品について割り付け結果を求めれば、処理を終了する。
【００３４】
上記のような方法では、前半の材料は極めてよい歩留となる。しかしながら、後半で割付ける製品が少なくなるにつれて次第に歩留が悪くなるという弱点を持っている。そこで、これを改善するために、本発明者等は、Revised MBD(RMBS)法およびこれを使ったRecursive RMBS(R-RMBD)法を開発した。
【００３５】
図３と図４は、RMBS法の動作説明図である。
この方法は、複数の長さの材料を扱う、Multiple Stock Lengthの材料取り合わせに適用できる方法である。まず、それぞれの長さの１本の材料に、One-Packing MBS法で製品を仮に割付けてみる。何種類かの割付け結果が得られる。それぞれの割付け結果を、「良い割付け」と判断するための判断基準に照らして評価する。「良い割付け」とする判断基準とは、例えば、その材料について、歩留まり最大という基準である。そして、ある長さの材料と割付けられた製品グループを選択して、その結果を保存する。さらに、残りの製品について、再び同様の処理を繰り返す。こうして、すべての製品が割り付け済みになるまで繰り返す。図３はその結果を示している。n回目の仮割付けで、材料１に製品（１）と（３）が、材料２に製品（１）と（６）が、それぞれ仮割付けされている。材料３が仮割付け対象外なのは、最長製品(1)が割付けられない長さのためである。
【００３６】
「良い割付け」とする判断基準には、それぞれの仮割付け結果が最も高い歩留かどうかを判断する、「歩留基準」と、仮割付けした製品も含めた残りの製品すべてを割付けるのに、必要な材料の長さが最小となる割り付けかどうかを判断する「材料基準」というものがある。「歩留基準」は、仮割付けのつど、材料単位で最良の割付けを選択するので、良い結果を先取りしていく。一方、「材料基準」は、最終的に目標としている最も経済的な割付けを選択するということである。「材料基準」は、残りの割付け全体を見通せないと適用できない。図３のｎ回目では、材料（２）への仮割付け結果が「歩留基準」で選択されている。ｎ＋１＋回目も同様の要領で処理をしている。
【００３７】
RMBS法では、仮割付けの開始から残りの製品数が少なくなるまで、「歩留基準」を採用し、最後の数回で割付けが終了するところまできたときに、「材料基準」を採用する。この段階で歩留基準から材料基準へ基準を変更することを「最終調整」と呼ぶことにする。この最終調整で「良い結果を先取り」することによる最後の材料の歩留の悪化を防止する。図４はその例で、残り２回で割付けが終了するという段階で、全ての製品を最後まで割付ける方法を可能な限り試行して、それらの仮割付け結果を「材料基準」で比較する。これにより、最終段階で歩留まりの悪い組み合わせが残ってしまうのを防ぐことができる。即ち、RMBSでは「最終調整」によって終盤の歩留の低下を緩和している。
【００３８】
図５は、R-RMBS法の説明図である。
上記のRMBS法で、もし「材料基準」を最初のステップから最良の割付け処理を判断するために適用できれば、より最適解に近い結果が得られるはずである。そこで製品を取り出して各材料に仮割付けするとき、残りの製品もRMBS法を使用して最後まで割付けしてみる。そして、得られた最終歩留を比較してみる。図５はその例を示す。図の「選択」と表示した部分で、材料１に割付けをしたときと、材料２に割付けをしたときと、材料３に割付けをしたときを比較する。この場合に、例えば、材料１に割付けをしたときには、その後、材料１，材料２，材料２、材料１材料３という順番に材料を選択して、仮割付けをするという結果となる。この処理を試行という。この試行の結果、全体の最終歩留まりが９２．３％となった。
【００３９】
「選択」の部分で、材料２を選択したときには、全体の最終歩留まりが９５．６％となった。材料２を選択したときには、全体の最終歩留まりが８９．６％となった。これにより、「選択」の部分で材料２を選択することが良いと判断できる。これが、「材料基準」で判断をするということである。なお、最後まで割付けをしてみる試行の部分では、長い製品から順に割付けることを利用して、冗長な処理を省略することで、演算処理を高速化することができる。また、最終調整にはRMBS法を使用するとよい。即ち、R-RMBSでは、割付けを選択するときに最後までRMBSで割付けを試行して、その結果に基づく比較をして材料選択をする。こうして、後半で歩留まりが悪くなる点を改善できる。
【００４０】
この「材料基準」は、最も良い割付け結果かどうかを判定する基準を、「全ての材料から全ての製品を切り出した残りの残材量の総和が最小となる場合」、もしくは「・・・残材量の総和が最小値に近い場合」と表現することができる。また、このほかにも、最も良い割付け結果かどうかを判定する基準が知られている。これは、全ての材料から全ての製品を切り出した残りの残材量の総和が最小値に近いとき、最も長い残材が存在する場合を最も良いとするものである。残材量の総和が最小値に近い場合に、同じ量の残材が生じても、長い残材を残す割付けをすると、その残材は別の用途に使用でき、無駄を少なくできるという論理である。最終的に最も良い割付けを選択する判断基準としてこの方法を採用してもよい。
【００４１】
次に本発明の説明をする。本発明は、上記の方法と区別するために、Grouping RMBS(G-RMBS)法と呼ぶことにする。この方法では、RMBSといった割付け法が、初めの方の材料は歩留が良好であることを利用して、例えば、以下のようなアルゴリズムを採用する。
（１）割付対象製品群をいくつかのグループに分割する。
（２）分割したグループごとに、以下の処理を行う。
例えば、RMBS法で割付けを実行する（最終調整なしで行う）
できるだけ初めのほうに良い結果が得られる割り付け方法を採用する。
割付けた材料のうち、最後に割付けた材料からさかのぼって割付け結果を解体する。
各グループから、解体して未割付けとなった製品を集める。
これらの製品全部に対して、後半を改善した例えば、R-RMBSで割付けを実行する。
これで、全体としての歩留まりを向上させる。
【００４２】
上記のアルゴリズムでは、割り付け対象製品を異なる組み合わせでグルーピングすると、結果がその都度変化する。そこで、ランダムにグルーピングを変化させて、同じ操作を繰り返し、最も良い結果となった割付けを採用することが好ましい。また、全ての割り付け対象製品をR-RMBS法で割付けた結果を初期値として記憶しておき、グルーピングをして求めた割り付け結果と比較し、良い結果が得られたほうを採用するとよい。
【００４３】
MBS法では、ビンに対して総当りで最も空きスペース（Slack）が少なくなるアイテムの組み合わせをサーチして採用するという手法をとる。しかしサーチ中に空きスペース＝０（満杯）となる組み合わせが見つかったときは、総当りサーチを中止してその組み合わせを採用する。こうすれば、その後の無駄な仮割り付け計算を省略できる。なお、この「満杯」であるという判断を緩和することができる。
空きスペース＜ビン容量×許容率    但し、0≦許容率＜1
このように緩和した条件を採用する方法はRelaxed MBS法と呼ばれている。空きスペース＝０とした場合のMBS法の解は固定的であるが、許容率を変化させるRelaxed MBSの場合には解を変化させることができる。また、満杯にならなくても、許容値で処理を終了させることができるから、処理時間の短縮も図れる。
【００４４】
この方法は既に知られた方法であるが、これを、上記の「歩留基準」「材料基準」とともに、判断基準に投入することができる。しかも、グルーピングの組み合わせを変化させるときに、同時にRelax許容率を変化させることで、解にさらに多様性を持たせることができる。解に多様性を持たせてその結果を比較すれば、より良い結果を得ることができる。後で説明するように、グループ毎の割付け処理をする第一仮割り付け手段２２は、「歩留基準」とRelax許容率とを使用するとよい。
【００４５】
なお、上記の方法を実行するためのパラメータは次の４つとなる。
（１）グルーピング分割数・・・多いと割付け対象が細分化され、処理時間は早くなるが、良い組み合わせが多く見つからない危険がある。実験によれば、分割数が２〜４の範囲が実用上最適であった。各グループに属する製品の数は完全に一致する必要は無いが、ほぼ近似していることが好ましい。
（２）解体数・・・多いと、再割付けで良い組み合わせが見つかるチャンスが増えるが、処理時間がかかる。実験によれば、解体される材料の枚数が１〜４の範囲が実用上最適であった。解体された製品数は、当初のグループに属する製品数に近似していることが好ましい。例えば、当初のグループに属する製品数の平均値の０．９〜１．１倍以内程度に設定するとよい。
（３）Relax許容率の変化範囲・・・大きいと、処理時間は早くなるが、空きスペースが多くあっても「満杯」と判断されて、良い組み合わせを得る計算ができなくなる可能性がある。変化範囲は０〜０．１が実用上最適であった。
（４）試行回数・・・多ければ多いほど、良い割付け結果を得るチャンスは増えるが、処理時間も増える。実験により、試行回数は製品数の２倍から３倍程度で十分であった。なお、ここでいう試行とは各グループに属する製品の組み合わせを変える試行のことである。
【００４６】
上記の方法の特徴は、「良い組み合わせが先取りされる」弱点を持つRMBS法の弱点を利用したところにある。したがってRMBS法を、同じ弱点を持つアルゴリズムで置き換えることができる。たとえばRMBS法をRBFD（Best Fit Decreasing）法に、R-RMBS法をさらに改良されたR-RBFD法に置き換えても良い結果が得られる。
【００４７】
分割数と解体数の関係は、様々な方法で最適化できる。例えば、分割数は割付け対象製品の数と一つの材料あたりの平均割付け製品数で決定する。割付け対象製品の数が多ければ、分割数を多くできる。一つの材料あたりの平均割付け製品数が多いときは、分割数は少なめがよい。また、解体数はあらかじめ固定しないで、割付けの逆順に「材料を１つ解体してR-RMBSで再割付ける」という処理を、歩留が向上している間は、解体数を増やして繰り返すという方法も可能である。
【実施例１】
【００４８】
図１は、本発明の材料取り合わせシステムの実施例を示す機能ブロック図である。
以下に、図面を用いて、本発明を実施するためのシステムの具体例を説明する。図１と図２は、本発明を実施するための装置の構成例である。図１の材料取り合わせシステム１０は、既知の構造のパーソナルコンピュータ１２等により実現することができる。図のコンピュータ１２は、ディスプレイ２と本体制御部３とキーボード４とマウス５とを備えている。キーボード４とマウス５とは、演算処理条件を入力する入力手段である。ディスプレイ２は、演算処理の結果を出力する出力手段である。
【００４９】
上記のコンピュータ１２の本体制御部３には、演算処理装置２０と記憶装置４０とが収容されている。演算処理装置２０には、グループ分け手段２１、第一仮割り付け手段２２、部分解体手段２３、第二仮割り付け手段２４、割り付け結果出力手段２５等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。記憶装置３０には、材料データ４１、割り付け対象製品データ４２、グループデータ４３、仮割り付けデータ４４、解体製品データ４５、新たなグループデータ４６、仮割り付け済みデータ４７、解体分割り付けデータ４８、総割り付けデータ４９、初期値データ５０、最良値データ５１といったデータが記憶されており、演算処理に使用される。また、演算処理中に使用するパラメータとして、選択製品数５２、グループ数５３、繰り返し回数５４、解体材料数ｎ５５、解体製品数５６等が記憶されている。これらのプログラムの機能やデータの構成は、後で詳しく説明する。
【００５０】
図２は、上記の材料取り合わせシステムの本体制御部の内部ブロック図である。
コンピュータの内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５とネットワークインタフェース１１６が接続されている。入出力インタフェース１１５には、ディスプレイ２とキーボード４とマウス５とプリンタ１１が接続されている。
【００５１】
図１に示した記憶装置２０は、ＲＯＭ１１２やＲＡＭ１１３やＨＤＤ１１４により構成される。演算処理装置４０は、ＣＰＵ１１１、ＲＯＭ１１２、ＲＡＭ１１３等により構成される。演算処理に必要なデータは主としてＨＤＤ１１４に記憶されて保存される。ＣＰＵ１１１が実行するコンピュータプログラムは、ＲＯＭ１１２に記憶され、あるいはＲＡＭ１１３に適時ロードされる。
【００５２】
ネットワークインタフェース１１６は、ネットワーク１４を介して、プレカット工場の端末装置１６と接続されている。本発明の材料取り合わせシステムの出力した、最適化された最も良い割り付け結果は、端末装置１６により取得され、プレカット装置１７の制御に使用される。プレカット装置１７は、材料を選択する材料選択供給装置１２０と、材料から製品を切り出す材料切断装置１２１と、切り出した製品を搬送するコンベア等の製品搬送装置１２２を備えている。
【００５３】
図６は、図１に示した記憶装置に記憶されたデータの説明図である。
この図により、上記の各手段の機能と、システムの動作中に登場する各データの具体的な構成とを説明する。まず、割り付け対象製品データ４２は、割付け対象の製品を特定するデータを、その長さ順にソートして表示したものである。このデータに対して、例えば、乱数データ「２，３，６，８，１２，１３，１５，１６，１８，」を適用して、グループデータＧ１を得る。即ち、割り付け対象製品データ４２を最初から数えたときに、乱数で発生した数値の場所にあるデータを抽出する。そして、残りの製品をグループデータＧ２とする。こうして２つのグループデータ４３が得られる。グループ分け手段２１（図１）はこのように、割り付け対象製品を２以上のグループに分割する機能を持つ。
【００５４】
次に、各グループに属する製品について、材料に対する製品の組み合わせの良い割り付けを先取りしながら、全ての製品をいずれかの材料に割り付けるように仮割り付けをする。これを第一仮割り付け手段２２（図１）が実行する。グループデータＧ１とグループデータＧ２について、それぞれ仮割り付けデータ４４が得られる。仮割り付けデータ４４は、どの材料にどの製品を割付けたというように、材料と製品の組み合わせを示すデータである。
【００５５】
ここで、部分解体手段２３（図１）が、仮割り付けが終了したグループについて、先取りした良い割り付け結果を得た材料を除くいずれかの材料についての割り付け結果を解体する。前半は先取りした良い割り付け結果である。最後の付近に良くない割付け結果が残るはずである。そこで、得られた２つの仮割り付けデータ４４について、最後付近で割付けられた材料についての割付けデータを解体する。それぞれ、図のように、解体製品データ４５が得られる。なお、仮割り付けデータ４４のうち解体されない部分は、仮割り付け済みデータ４７となる。
【００５６】
次に、第二仮割り付け手段２４（図１）は、解体されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作る。その内容を表示したのが新たなグループデータ４６である。第二仮割り付け手段２４は、この新たなグループに属する製品について、再割り付けを行う。その結果、解体分割り付けデータ４８が出力される。新たなグループデータ４６とグループデータ４３（Ｇ１とＧ２）の２つの仮割り付け済みデータ４７とを集計すると、総割り付けデータ４９が得られる。割り付け結果出力手段２５（図１）は、総割り付けデータ４９から、全てのグループの割り付け済みの製品とそれを割り付けた材料との組み合わせを示す割り付け結果を出力する機能を持つ。
【００５７】
このように、割り付け対象製品を２以上のグループに分割して、これらに組み合わせの良い割り付けを先取りする割り付け計算法を適用し、しわ寄せがきた最後のほうの割り付け結果を集めて解体、再割り付けをすれば、より良い割り付け結果を得ることが可能になる。以上が本発明の基本的な処理である。以下、さらに具体的な処理例を説明する。
【実施例２】
【００５８】
図７は、システムの初期値計算処理動作例フローチャートである。
以下は、本発明のシステムを動作させるコンピュータプログラム処理例である。はじめにプレカット用の一種類または複数種類の材料を十分な数だけ用意して、これに、プレカットすべき複数種類の製品を長いものから順番に割り付ける処理を開始する。その準備のために、図７の処理を実行する。この図７の処理は、第一仮割り付け手段２２が実行する。以下、図１も合わせて参照する。
【００５９】
ステップＳ１１では、記憶装置４０から割り付け対象製品データ４２を読み込む。次に、ステップＳ１２で、製品を大きさの降順にソートする。これで、図６の左上に示したような割り付け対象製品データ４２が得られる。次に、ステップＳ１３で、第一仮割り付け手段２２が、割り付け対象製品データ４２と材量データ４１を読み取りながら、Ｒ−ＲＭＢＳ法で割付け処理を実行する。ここでは、既知の最良の割付け演算処理方法を使用して結果を求めておくとよい。ステップＳ１４で、その割付け結果を初期値データ５０として、記憶装置４０に記憶させる。その後の処理で、この初期値データ５０よりも良い結果がえられなかったら、初期値データ５０が最良値データ５１に採用される。
【００６０】
図８は、グループ分け手段２１の動作フローチャートである。
ここでは、グループ分けに、図６を用いて説明した乱数を使用する。まず、ステップＳ２１で乱数を発生する。次に、ステップＳ２２で乱数を使って製品を選択する。図６を用いて説明したとおりの処理である。ステップＳ２３では、記憶装置４０に記憶した既定値の選択製品数５２の範囲内かどうかという判断をする。この例は、グループに含まれる製品数の範囲を例えば、ほぼ等しく揃えた例である。
【００６１】
一方、もっとランダムに各グループに属する製品数を決めても構わない。例えば、ソート済みの製品に対して、製品毎に下式によってその製品の分類すべきグループを決定する。
グループＮｏ．＝ Int（(0,1)乱数×グループ規定値）＋１
乱数は製品の数だけ発生させる。グループに属する製品の数はグループによってばらばらでよい。場合によっては製品のないグループ（つまりグループが形成できない場合）が発生したり、製品がひとつのグループも発生する。これにより、さらに広範囲に良い結果を求めることができる。ステップＳ２３の判断の結果がイエスのときはステップＳ２４の処理に移行し、ノーのときはステップＳ２２の処理に戻る。
【００６２】
割り付け対象製品データ４２の中から降順で発生させた乱数で製品を選択したときには、ステップＳ２４で、並び順を変えずにグループ化をするとよい。はじめにソートされている製品群から長い順に製品を選択していくと、グループに含まれた製品はソートされた状態で出力される。従って、そのまま、割付け処理に進むことができる。ステップＳ２５では、記憶装置４０に記憶した既定値のグループ数５３かどうかという判断をする。記憶装置に記憶したグループ数５３を参照する。この判断の結果がイエスのときはステップＳ２６の処理に移行し、ノーのときはステップＳ２１の処理に戻る。即ち、ステップＳ２１からステップＳ２５までの処理を、求める数のグループが得られるまで繰り返す。なお、図６の例では、ステップＳ２１からステップＳ２４の処理を１回実行するだけで、グループ数は２個になる。ステップＳ２６では、得られた複数のグループデータ４３を出力する。このデータは、演算処理のため記憶装置４０に記憶される。
【００６３】
図９は、システムのメインルーチンの動作フローチャートである。
ステップＳ３１で初期値計算をする。これは、図７で説明をした処理である。ステップＳ３２では、第一仮割り付け手段２２が初期値データ５０を、記憶装置４０に最良値データ５１として記憶させる。この最良値データ５１は、より良い結果が得られる度に更新される。ステップＳ３３では、グループデータ４３の取得をする。これは、図８で説明した処理である。
【００６４】
これから、第一仮割り付け手段２２が、グループ毎の割付けを開始する。ステップＳ３４では、ひとつのグループを選択をする。ステップＳ３５では、そのグループについて、ＲＭＢＳ法により仮割付けするをする。ステップＳ３６では、そのグループの仮割付けデータ４４を保存する。ステップＳ３７では、図６で説明したとおり、部分解体手段２３が仮割付けデータ４４の一部解体をする。解体した結果は解体製品データ４５として記憶する。ステップＳ３８では、全グループデータ４３について、仮割付けが終了したかどうかという判断をする。この判断の結果がイエスのときはステップＳ３９の処理に移行し、ノーのときはステップＳ３４の処理に移行する。こうして、全てのグループについて仮割付け処理を繰り返す。
【００６５】
次に、ステップＳ３９で、第一仮割り付け手段２２が全ての解体製品データ４５を集合する。そして、ステップＳ４０で、集めた製品を大きさの順にソートする。その結果得られた新たなグループデータ４６は記憶装置４０に記憶される。そして、ステップＳ４１で、第二仮割り付け手段２４が、新たなグループデータ４６について、Ｒ−ＲＭＢＳ法で割付け処理をする。さらに、ステップＳ４２で、総割付けデータ４９の集計をする。ステップＳ４３では、ここで得られた歩留まりを、記憶装置４０に記憶された最良値データ５１と比較する。そして、より良い結果が得られたときには、最良値データ５１を今回の結果と置き換えて更新をする。
【００６６】
ステップＳ４４では、記憶装置４０に記憶した既定値の繰り返し回数５４に達したかどうかという判断をする。この判断の結果がイエスのときは全ての処理を終了する。ノーのときはステップＳ３２の処理に移行する。この実施例では、グループ分けの方法をランダムに変更して、ステップＳ２３からステップＳ４４までの処理を、例えば、１０００回繰り返すことができる。
【００６７】
グループ分けの結果は割付け結果に影響を及ぼす。以上のように、グループ分け手段２１が、各グループに属する製品をランダムに選択して、第１仮割付け手段２２が、各グループ毎に得られた仮割付け結果を記憶装置に記憶させるという動作を、各グループに属する製品を変更しながら複数回実行することで、より良い割付け結果を得る確率を高めることができる。
【００６８】
また、第１仮割付け手段２２による仮割り付けが終了した全てのグループについて、材料とその材料に割り付けた製品とを示す全ての割り付け結果を集めて、全体としての割付け結果を求めておくとよい。その結果を、第２仮割付け手段による仮割付けが終了して得られた割付け結果と比較して、良い方を最良の割り付け結果として出力することが好ましい。例えば、初期値計算の結果や、グループ分け直後の割付け結果で、偶然、歩留まりが１００％に近い割付け結果が得られる場合もあり得るからである。しかし、経験的には、ほとんどの場合には、上記のようにグループの後半の割付け結果を集めて再度割付けをすると、歩留まりが改善されるということが言える。
【実施例３】
【００６９】
図１０は、グループの解体処理の動作フローチャートである。
例えば、最後からＰ枚分の材料について解体処理を実行するときにはこのような処理をする。ステップＳ５１では、いずれかのグループの仮割付け処理を実行する。そして、仮割り付けデータが得られたら、ステップＳ５２で、Ｐ＝１と、パラメータをセットする。ステップＳ５３では、仮割り付けデータ中の最後からＰ番目の材料を選択する。そして、ステップＳ５４で、その材料に割付けた製品を解体する。ステップＳ５５では、解体分のデータを削除して仮割付け済みデータの更新をする。ステップＳ５６では、解体製品データを記憶装置に書き出すようにして出力をする。ステップＳ５７では、Ｐをインクリメントする。ステップＳ５８では、Ｐは既定値かどうかという判断をする。最後からＰ枚分の材料について解体処理を実行するときにはＰが３のときが記憶装置４０に記憶した既定値の解体材料数５５＝Ｐである。この判断の結果がイエスのときは処理を終了し、ノーのときはステップＳ５１の処理に戻る。なお、ステップＳ５５とステップＳ５６の処理は、ステップＳ５８の後側に設けても構わない。
【００７０】
上記のように、解体は材料単位で行うことが好ましい。このとき、最後から数えてＰ番目の材料とすれば、仮割付けの最後に近い段階で使用される材料の割付け結果を改善できる。なお、例えば、試算の結果、使用される材料枚数がわかっているような場合には、最後からＰ番目という計算でなく、最初から数えてＱ番目の材料に製品を割り付けたところで製品の仮割付けを中断するということも可能である。即ち、各グループについて、仮割り付けが終了する直前で、仮割り付けを中断することもできる。あとは、仮割り付けが中断されて未割り付けとなった複数のグループに属する製品を集めて新たなグループを作ればよい。
【００７１】
また、新たなグループに属する製品数を予め指定したいときには、最後から数えてｍ番目または最初から数えてｎ番目の製品を割り付けたところまで遡って割付け結果を解体するとよい。なおこのときには、仮割付け中で、未だいずれかの製品をさらに割付け可能な材料が残る。この材料は解体の対象とする。従って、解体製品数５６を決めておいても、実際の解体総数とは一致しない。解体されて未割り付けとなった複数のグループに属する製品の数の総和が、分割された各グループに始めに属していた製品の数とほぼ等しくなるようにす  にことが好ましい。また、最後まで仮割り付けを行って、割り付け済みの材料の材料毎の歩留まりを比較する。そして、材料歩留の低い材料から順に、予め決められた数の材料について、割り付けの解体をしてもよい。なお、図７の処理により得た初期値と割り付け済みの材料の材料毎の歩留まりを比較して、初期値より歩留まりの悪い材料を解体することで、初期値より改善された結果が期待できる。
【００７２】
当初の分割されたグループに属する製品数は、所定の演算法で仮割付けをするのに適した数に選定される。従って、未割り付けとなった製品による新たなグループに属する製品数も、この数量に近いことが好ましい。例えば、当初の分割されたグループに属する製品数の最大値と最小値の間の数になるように選定するとよい。
【００７３】
また、第１仮割付け手段２２は、解体してから仮割付け結果を記憶装置４０に記憶させる動作を、解体する割付け範囲を変更しながら複数回実行することもできる。解体数によって、結果が異なる場合があるからである。結果出力手段２５は、複数回のうち最も良い割付け結果が得られたものを最終結果として取り出せばよい。
【００７４】
図１１はグループの仮割り付け中断処理の動作フローチャートである。
図のステップＳ６１で、ひとつのグループの仮割付け処理を開始する。ステップＳ６２では残り製品の数をカウントする。ステップＳ６３では、残り製品数が解体目標値かどうかという判断をする。この判断の結果がイエスのときはステップＳ６４の処理に移行し、ノーのときはステップＳ６２の処理に戻る。ステップＳ６４では、仮割付け処理を終了する。ここで中断をするということである。ステップＳ６５では、これまでの分の仮割付け済み結果を記憶装置に保存する。ステップＳ６６では、残り製品リストを出力する。これで、仮割り付け処理を所定の基準で中断して、新たなグループを生成することができる。
【００７５】
図１２〜図１５は、具体的な実行結果の比較データである。
図１２において、G-RMBSと表示した左半分は本発明の実施例による計算結果で、ＥＰと表示した右半分は比較例で、既知のきわめて優れた手法による計算結果（Liangらの報告値）を利用したものである。Liangは、50回の独立した繰返し処理の結果に対する平均値を示す。G-RMBS法でも比較のために３０回繰り返した結果を示した。この例では、上記の解体数を３とし、分割数は２または３とした。Relax許容範囲は0.1とした。
【００７６】
Ｐｒｏｂは、ケース番号である。ＲｅｑＩｔｅｍは、割り付け対象製品の数を示す。Trialsと表示した部分は、図９ステップＳ４４の繰り返し回数を示す。右側の比較例は遺伝的手法であって、Trialsに相当する部分はｇｅｎ（世代）である。Found欄は、G-RMBSでは、何回目の試行でCostの最小値が得られたかを示し、EPでは何世代目でCostの最小値が得られたかを示している。ＷｅｓｔａｇｅＭｅａｎは、残材の平均値である。ＣｏｓｔＭｅａｎは、コストの平均値である。Ｆｏｕｎｄが１となっている部分は、図７の初期値計算でR-RMBSによって最良値が得られた場合である。実施例と比較例を比較してみると、ケース５ａで、実施例が若干良いものの、他のケースでは同じ結果が得られている。しかしながら、何回目の試行でCostの最小値が得られたかという部分を比較すると、実施例が圧倒的に速く計算できることが分かる。一方が全ての計算に数秒であるのに対して、他方は数分というほどの違いも生じる。
【００７７】
図１３も全く同様の形式でまとめたデータである。ケース６ａ〜１０ａをみると、残材が十分に少なくなっており、比較例よりも実施例のほうが安定的に良い結果が得られることが分かる。
【００７８】
次に、典型的な木造戸建住宅10戸のプレカットデータに本発明を適用した例を示す。図１４の左の表が、各住宅の製品数を示す。使用したのは梁や土台となる横架材のデータで、プレカットでは3mから6mの長さの材料から要求された長さ(0.5m〜4m)の部材製品を切り出す。図１４の右の表に示すように、1邸あたり約200本の製品は、断面サイズや樹種、等級によって約20のロットに分かれ、それぞれのロットごとに切り出す製品数や使用する材料長の種類の数が異なる。そのためロットごとに材料取り合わせシステムによる計算を実行する。各種パラメータは、以下のとおりとする。グループ数は原則として2とした。但し製品数が４以下のときは分割しない。解体数は１〜４、試行回数は製品数の２倍とした。
【００７９】
実行結果とその計算の実行時間とを図１５に示す。比較例は、既に説明したR-RFFD法 R-RMBS法と、遺伝的手法を使用したGA法(Toyoda et al., 2008)である。ここでのG-RMBSは、10回実行した結果すべて同じ歩留となり安定していることがわかったため、1回の実行結果を記載している。1回の処理時間は、きわめて高速なR-RFFDやR-RMBSに比べても2倍程度で収まっている。なおGAは、個体数100、世代数1000世代の処理を10回の繰返し結果の最大値を採用しており、1邸あたりおよそ20分程度の時間を必要する。G-RMBSはGAに比較して圧倒的に短い数秒以内の時間で、GAに同等でなおかつ一部で勝る結果を出したことになり、きわめて実用的なシステムであることがわかった。
【００８０】
なお、上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組み合わせて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。
【符号の説明】
【００８１】
１０  材料取り合わせシステム
１２  コンピュータ
１４  ネットワーク
１６  端末装置
１７  プレカット装置
２０  演算処理装置
２１  グループ分け手段
２２  第一仮割り付け手段
２３  部分解体手段
２４  第二仮割り付け手段
２５  割り付け結果出力手段
４０  記憶装置
４１  材料データ
４２  割り付け対象製品データ
４３  グループデータ
４４  仮割り付けデータ
４５  解体製品データ
４６  新たなグループデータ
４７  仮割り付け済みデータ
４８  解体分割り付けデータ
４９  総割り付けデータ
５０  初期値データ
５１  最良値データ
５２  選択製品数
５３  グループ数
５４  繰り返し回数
５５  解体材料数ｎ
５６  解体製品数
【図１】
2011100303.tif 000003
【図２】
2011100303.tif 000004
【図３】
2011100303.tif 000005
【図４】
2011100303.tif 000006
【図５】
2011100303.tif 000007
【図６】
2011100303.tif 000008
【図７】
2011100303.tif 000009
【図８】
2011100303.tif 000010
【図９】
2011100303.tif 000011
【図１０】
2011100303.tif 000012
【図１１】
2011100303.tif 000013
【図１２】
2011100303.tif 000014
【図１３】
2011100303.tif 000015
【図１４】
2011100303.tif 000016
【図１５】
2011100303.tif 000017