(57)【要約】  この発明は、複数種類の寸法が異なる母材からなる母材群に、所定寸法を持つ複数個の製品を割り付けるに際し、前記複数個の製品を寸法の大きさの順に配列するソート工程と、その配列順に各製品を取り出して前記母材群に属する各母材に、前記取り出した製品を仮割付けし、複数通りの仮割付状態を生成する仮割付工程と、前記生成された複数通りの仮割付状態のうち、割付けに使用した母材の歩留が最も高い仮割付状態を割付候補として選択する第１基準工程と、前記生成された複数通りの仮割付状態のうち、割付けに使用したすべての母材の残りの寸法の合計が最も小さくなる仮割付状態を割付候補として選択する第２基準工程とを備え、前記第１基準工程と第２基準工程が、所定の仮割付条件が満たされたときに、前記第１および第２基準工程のそれぞれにおいて選択された仮割付状態について、選択された仮割付状態と、その他の仮割付状態とを比較し、使用する各母材の寸法の合計寸法が最小となる仮割付状態を割付候補として選択し直す第３基準工程を備えた、プレカット材料割付方法である。
2009038196.tif 000002
【特許請求の範囲】
【請求項１】
複数種類の寸法が異なる母材からなる母材群に、所定寸法を持つ複数個の製品を割り付けるに際し、
前記複数個の製品を寸法の大きさの順に配列するソート工程と、
その配列順に各製品を取り出して前記母材群に属する各母材に、前記取り出した製品を仮割付けし、複数通りの仮割付状態を生成する仮割付工程と、
前記生成された複数通りの仮割付状態のうち、割付けに使用した母材の歩留が最も高い仮割付状態を割付候補として選択する第１基準工程と、
前記生成された複数通りの仮割付状態のうち、割付けに使用したすべての母材の残りの寸法の合計が最も小さくなる仮割付状態を割付候補として選択する第２基準工程とを備え、
前記第１基準工程と第２基準工程が、所定の仮割付条件が満たされたときに、前記第１および第２基準工程のそれぞれにおいて選択された仮割付状態について、選択された仮割付状態と、その他の仮割付状態とを比較し、使用する各母材の寸法の合計寸法が最小となる仮割付状態を割付候補として選択し直す第３基準工程を備えた、プレカット材料割付方法。
【請求項２】
前記所定の仮割付条件は、
前記第１または第２基準工程において、所定数の製品の母材群への仮割付を実施した後、前記生成された各仮割付状態についての未割付の製品の合計寸法の最小値が、前記母材群に含まれる最大寸法の母材の寸法以下か否かを確認することであり、
前記未割付の製品の寸法の合計が、前記最大寸法の母材の寸法以下のときに、前記第３基準工程を実施し、その他の場合には前記第３基準工程は実施しない請求項１のプレカット材料割付方法。
【請求項３】
前記第１基準工程は、前記仮割付工程で生成した仮割付状態のそれぞれに対して、仮割付けに使用した各母材に割付けられた製品の合計寸法を、その母材の寸法で割った材料歩留をそれぞれ算出する第１算出工程と、
前記算出された各割付状態に対する材料歩留の中で最も大きな値を持つ仮割付状態を、歩留の最も高い仮割付状態として選択する第１選択工程とを備えた請求項１または２のプレカット材料割付方法。
【請求項４】
前記第２基準工程は、前記仮割付工程で生成した仮割付状態のそれぞれに対して、その仮割付に使用した各母材について製品が割付けられていない部分の残材寸法を算出する第２算出工程と、
前記算出された各仮割付状態の残材寸法のうち最も小さな残材寸法を持つ仮割付状態を、選択候補として選択する第２選択工程とを備えた請求項１又は２のプレカット材料割付方法。
【請求項５】
前記第１基準工程で選択された割付候補に対して、割り付けるべきすべての製品の合計寸法をその割付けに使用したすべての母材の合計寸法で割った歩留ｙ１を計算する第１歩留計算工程と、
前記第２基準工程で選択された割付候補に対して、割り付けるべきすべての製品の合計寸法をその割付けに使用したすべての母材の合計寸法で割った歩留ｙ２を計算する第２歩留計算工程と、
前記歩留ｙ１と歩留ｙ２を比較する工程と、
前記比較の結果、大きな歩留を持つ割付候補を最終的な割付状態として決定する割付決定工程とを、さらに備えた請求項１乃至４のいずれかに記載されたプレカット材料割付方法。
【請求項６】
前記仮割付工程において、取り出された１つの製品を、１つの母材に仮割付をしようとするとき、前記取り出された製品の寸法が前記母材の寸法以下であり、またはその母材にすでに仮割付けされた１または複数の製品が存在するときは、前記取り出された製品の寸法とすでに仮割付されたすべての製品の寸法との合計寸法が、前記母材の寸法以下となる場合に、前記取り出された製品を、前記母材に仮割付をする請求項１のプレカット材料割付方法。
【請求項７】
前記母材および製品が１次元方向に長い材料の場合、前記母材および製品の寸法は前記１次元方向の長さである請求項１乃至６のプレカット材料割付方法。
【請求項８】
前記母材および製品は、１次元部材または２次元部材である請求項１乃至６のプレカット材料割付方法。
【請求項９】
前記１次元部材が、木材である請求項８のプレカット材料割付方法。
【請求項１０】
前記２次元部材が、鋼板，布部材あるいは紙部材である請求項８のプレカット材料割付方法。
【請求項１１】
前記請求項１に記載のプレカット材料割付方法の各工程を、コンピュータに実行させるためのプログラム。
【請求項１２】
前記請求項１１に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の定尺長さの原材料から所定長さの製品部材を所定の本数だけ切り出すために、歩留りの良い前記原材料の各定尺長さのものの本数とそれぞれの原材料からどの製品部材を切り出すかを決定するプレカット材料取合せ処理方法に関し、典型的な組み合わせ問題であるビンパッキング問題(Bin Packing Problem: BPP)の一つであるFirst Fit(FF)法をベースに、複数種の母材を扱う場合に適用できるようにしたプレカット材料取合せ最適化処理方法に関するものである。
【背景技術】
【０００２】
プレカット材料取り合わせとは、いくつかの種類の長さの木材母材から、住宅建築で要求される長さの部材製品を切り出す問題(Cutting Stock Problem)で、一次元のビンパッキング問題(Bin Packing Problem: BPP)として考えることができる。但し、通常BPPではビンの容量は一定とされるが、プレカットの場合は数種類の長さの母材を対象とする。【０００３】
プレカット材料の一例としては、住宅構造材のプレカットがあり、断面形状や樹種，等級といった仕様毎に数種類の長さ(3.5m〜6m)の母材が用意され、そこから決められた長さの部材(製品)を切り出す。一般的な大きさの住宅の場合、梁、桁、土台など横架材とよばれるものでは、約20種類の仕様毎に数種類の長さの母材から平均10本、合計約200本の製品が切り出される。【０００４】
図１は、プレカット材料取り合わせの模式的な一例を示す。取り合わせ計算の目標は、製品の仕様毎に用意された数種類の長さの母材群１０１の各長さにより、製品群１０２の長さに合わせて、取り合わせ結果１０３から、要求製品をいかに少ない母材(歩留最大)で切り出すかということにある。また、母材の長さによって調達コストや在庫コストが異なる場合は、必要な母材コストの最小化が目標となる。通常、母材コストは材積単価で決まるため材積歩留の最大を狙うのが一般的である。なお、現在多くのプレカット工場での一次歩留は、概ね85%から90%といわれている。例えば、特許文献１（特許第３５６５２６２号）には、コンピュータを用いたロジックによる割り付け方法を示している。
【特許文献１】特許第３５６５２６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明では、一次元BBPでもっとも簡便な経験的（ヒューリスティック）方法のひとつであるFirst Fit法を、複数種類の母材を扱うプレカット材料の取り合わせ問題に適用できるように改良を加えたアルゴリズムを提案し、きわめて短時間の計算時間で行うように企図したものである。
【課題を解決するための手段】
【０００６】
この発明は、複数種類の寸法が異なる母材からなる母材群に、所定寸法を持つ複数個の製品を割り付けるに際し、前記複数個の製品を寸法の大きさの順に配列するソート工程と、その配列順に各製品を取り出して前記母材群に属する各母材に、前記取り出した製品を仮割付けし、複数通りの仮割付状態を生成する仮割付工程と、前記複数通りの仮割付状態のうち、割付けに使用した母材の歩留が最も高い仮割付状態を割付候補として選択する第１基準工程と、前記複数通りの仮割付状態のうち、割付けに使用したすべての母材の残りの寸法の合計が最も小さくなる仮割付状態を割付候補として選択する第２基準工程とを備え、前記第１基準工程と第２基準工程が、所定の仮割付条件が満たされたときに、前記第１および第２基準工程のそれぞれにおいて選択された仮割付状態について、選択された仮割付状態と、その他の仮割付状態とを比較し、使用する各母材の寸法の合計寸法が最小となる仮割付状態を割付候補として選択し直す第３基準工程を備えた、プレカット材料割付方法を提供するものである。【０００７】
また、この発明の前記所定の仮割付条件は、前記第１または第２基準工程において、所定数の製品の母材群への仮割付を実施した後、前記生成された各仮割付状態についての未割付の製品の合計寸法の最小値が、前記母材群に含まれる最大寸法の母材の寸法以下か否かを確認することであり、前記未割付の製品の寸法の合計が、前記最大寸法の母材の寸法以下のときに、前記第３基準工程を実施し、その他の場合には前記第３基準工程は実施しないプレカット材料割付方法を提供する。
ここで、所定の仮割付条件としては、たとえば後述する数式（９）が用いられる。また、第３基準工程では、後述する数式（１０）、（１１）による処理が行われる。【０００８】
また、前記第１基準工程は、前記仮割付工程で生成した仮割付状態のそれぞれに対して、仮割付けに使用した各母材に割付けられた製品の合計寸法を、その母材の寸法で割った材料歩留をそれぞれ算出する第１算出工程と、前記算出された各割付状態に対する材料歩留の中で最も大きな値を持つ仮割付状態を、歩留の最も高い仮割付状態として選択する第１選択工程とを備える。
さらに、前記第２基準工程は、前記仮割付工程で生成した仮割付状態のそれぞれに対して、その仮割付に使用した各母材について製品が割付けられていない部分の残材寸法を算出する第２算出工程と、前記算出された各仮割付状態の残材寸法のうち最も小さな残材寸法を持つ仮割付状態を、選択候補として選択する第２選択工程とを備える。【０００９】
また、この発明は、前記第１基準工程で選択された割付候補に対して、割り付けるべきすべての製品の合計寸法をその割付けに使用したすべての母材の合計寸法で割った歩留ｙ１を計算する第１歩留計算工程と、前記第２基準工程で選択された割付候補に対して、割り付けるべきすべての製品の合計寸法をその割付けに使用したすべての母材の合計寸法で割った歩留ｙ２を計算する第２歩留計算工程と、前記歩留ｙ１と歩留ｙ２を比較する工程と、前記比較の結果、大きな歩留を持つ割付候補を最終的な割付状態として決定する割付決定工程とを、さらに備えたプレカット材料割付方法を提供する。【００１０】
この発明の前記仮割付工程において、取り出された１つの製品を、１つの母材に仮割付をしようとするとき、前記製品の寸法が前記母材の寸法以下であり、またはその母材にすでに仮割付けされた１または複数の製品が存在するときは、前記取り出された製品の寸法とすでに仮割付されたすべての製品の寸法との合計寸法が、前記母材の寸法以下となる場合に、前記取り出された製品を、前記母材に仮割付をする。
この仮割付工程で行われる処理は、後述する表２に示した処理である。【００１１】
この発明において、前記母材および製品が１次元方向に長い材料の場合、前記母材および製品の寸法は前記１次元方向の長さを意味する。
また、前記母材および製品は、１次元部材または２次元部材のどちらでもよい。
ここで、前記１次元部材としては、たとえば、木材を対象としてもよい。
また、前記２次元部材としては、鋼板，布部材あるいは紙部材などを対象としてもよい。【００１２】
また、この発明は、上記したようなプレカット材料割付方法を実現するコンピュータプログラムを提供し、このプログラムを記録したコンピュータ読み取り可能な記録媒体を提供するものである。
【発明の効果】
【００１３】
本発明では、一次元BBPでもっとも簡便なヒューリスティック法のひとつであるFirst Fit法を、複数種類の母材を扱うプレカット材料の取り合わせ問題に適用できるように改良し、きわめて短時間の計算時間で処理できるとともに、邸別に本発明を適用したところでは、歩留が向上した。
【図面の簡単な説明】
【００１４】
【図１】プレカット材料取り合わせの模式的な一例を示す。
【図２】本発明による複数母材のためのＦＦＤ法を示す。
【図３】本発明による基準３で工程を示す図である。
【図４】本発明のアルゴリズム全体の流れ（フローチャート）図である。
【図５】本発明の実施に用いた邸１での割り付け結果表を示す。
【図６】本発明の材料割付方法の概略フローチャートである。
【符号の説明】
【００１５】
１０１      母材群
１０２      製品群
１０３      取り合わせ結果
【発明を実施するための最良の形態】
【００１６】
以下の実施例では、母材は一次元部材とする。たとえば、一方向に長い木材である。前記寸法は、長さと読みかえる。
また、母材群は、互いに長さが異なる複数種類の母材から構成される。母材は、割付け対象となる製品をすべて割付けることができるほど多数用意されるものとする。
たとえば、図１では、母材群は、長さの異なる３種類の母材１０１から構成される。
製品とは、実際に使用される部材で、要求された長さを持つ部材を意味する。
たとえば、家を造るために必要な柱が製品であり、柱の長さが４種類必要であったとすると、製品（柱）として、４つの異なる長さの柱を母材から切り出すことが要求される。
また、同じ長さの製品が、複数個必要な場合は、その必要な数だけ、母材に割り付けられる。ここで、所定寸法を持つ複数個の製品とは、たとえば、図１に示した長さの異なる７つの製品１０２を意味する。【００１７】
母材群と製品は、この発明の割付方法を実行する前に予め決定される。具体的には、この割付方法をパソコン等のコンピュータで実行する前に母材群のデータ（各母材の識別情報とその長さの情報など）と、各製品のデータ（各製品の識別情報と長さの情報など）とが、コンピュータに入力され、ハードディスクなどのメモリに保存される。
この発明のソート工程では、複数の製品が長さの長い順に配列される。たとえば図１の製品群（１）〜（６）に対しては、図２の（１）〜（６）のように、長い順に並べることを意味する。
ソート工程は、入力された製品のデータを用いて実行される。長さ順に並べられた製品のデータは、メモリに固定記憶しておき、１回だけ実行するものとする。
このように、ソートした結果をメモリに記憶しておけば、次の第１および第２基準工程の中で、再度ソートを行う必要はない。【００１８】
仮割付工程は、ある１つの母材に、メモリから取り出された製品を割り付ける処理を行うものである。割り付けとは、製品を切り出すことが可能な母材を選択することを意味し、仮割付されると製品の情報と母材の情報とが対応づけられ割り付けられたことがわかるようにメモリに記憶される。母材が複数種類ある場合は、その異なる種類の母材それぞれに対して、取り出した製品を割り付けてみる。製品の取り出しは、ソート工程で並べかえられた長さの長いものから順に行われる。したがって、最初は、最も長い製品が取り出される。
取り出された１つの製品について、長さの異なる母材に割り付ける処理を繰り返し行う。たとえば、図２に示したように、１回目の仮割付では、取り出された製品（１）に対して、この製品（１）を母材１に仮割付した状態と、同じ製品（１）を母材２に仮割付した状態の２通りの仮割付状態が生成される。
言いかえれば、取り出された１つの製品について、割り付け可能な母材がＮ個あれば、Ｎ通りの仮割付状態が生成される。仮割付工程は、後述するように第１基準工程と第２基準工程の中で、それぞれ行われ、具体的には、後述する表２に示した処理を行う部分である。【００１９】
図６に、この発明の材料割付方法の概要を説明するための概略フローチャートを示す。
まず、ステップＳ１０１において、上記したソート工程を実行する。これにより、長さの順に並べかえられた製品群のデータが得られる（図２参照）。【００２０】
次に、第１基準工程（ステップＳ１０２）を実行する。
ここで、割付けに使用した母材の歩留が最も高い仮割付状態が、割付候補として選ばれる。たとえば、後述する図２に示すように、１回目の仮割付では、２つの仮割付状態（母材１、母材２）のうち、母材２の割付状態が割付候補として選択される。【００２１】
第１基準工程では、仮割付処理（ステップＳ１３１）に加え、第１算出処理（ステップＳ１３２）と、第１選択処理（ステップＳ１３３）とが実行される。
第１算出処理では、材料歩留が算出される。
ここで、材料歩留とは、ある１つの母材に割り付けられた製品の合計寸法を、その母材の寸法で割った数値を意味し、仮割付けに使用した母材ごとに算出される。たとえば、図２に示すように、１回目の仮割付けでは、２つの母材１と母材２が選択されるが、この２つの母材ごとにそれぞれ材料歩留が算出される。
第１選択処理では、算出された材料歩留が複数個ある場合には、その中で最大の材料歩留を持つ母材が、歩留の最も高い仮割付状態として選択される。
たとえば、図２の１回目の仮割付では、２つの仮割付状態（母材１、母材２）に対して、算出された材料歩留のうち、大きな値を持つ材料歩留の方（すなわち、母材２）が、選択されることになる。
また、図３の仮割付では、３つの仮割付状態（母材１、母材２、母材３）のうち、最も大きい材料歩留を持つ仮割付状態（母材３）が選択される。選択された仮割付状態は、第１基準工程の割付候補としてメモリに記憶される。【００２２】
次に、ステップＳ１０３において、第３基準工程を実施するか否かの判断を行う。
この判断には、上記した所定の仮割付条件を用い、具体的には、後述する数式（９）を用いる。たとえば、後述する図３の場合、この判断は次のようにして行われる。
図３において、３つの仮割付状態（母材１、母材２、母材３）が生成されている。ここで、母材１（第１の仮割付状態）についての未割付の製品は、製品（３）と（４）であり、母材２（第２の仮割付状態）についての未割付製品は、製品（２）と（３）であり、母材３（第３の仮割付状態）についての未割付製品は製品（２）、（３）および（４）である。また、３つの母材のそれぞれについて、まだ割り付けされていない製品の合計寸法（長さ）のうち、最小のものは、図３では、第１の仮割付状態の製品（３）と（４）の合計長さ（３７００）である。【００２３】
すなわち、製品（３）と（４）の合計長さ（３７００）は、製品（２）と（３）の合計長さ（４５５０）よりも短く、製品（２）、（３）および（４）の合計長さ（６０５０）よりも短い。
この未割付の製品（３）と（４）の合計寸法（長さ）が、母材群の中の最大寸法（長さ）の母材１の長さ（６０００）よりも短いとすると、この所定の仮割付条件が満たされたことになる。
そして、この条件が満たされたときは、ステップＳ１０４へ進み、第３基準工程を実行する。
一方、条件が満たされないときは、ステップＳ１０５へ進み、予め入力された製品全体の仮割り付けが終了したか否かを判断する。すべての製品の仮割付けが終了したときは、ステップＳ１０６へ進む。【００２４】
ステップＳ１０４において、第３基準工程において定められた特定の基準のもとで、第１選択処理で選択された割付候補と、選択されなかったその他の仮割付状態とのどちらが適切かを判断し、割付候補の選択の見直しを行う。
この特定の基準とは、ある仮割付状態について、使用される各母材の寸法（長さ）の合計寸法（長さ）を計算し、その合計寸法（長さ）が、最も短いものを選択するという基準である。具体的には、後述する式（１０）と（１１）が、この基準に相当する。【００２５】
また、後述する式（１０）による計算をするために、未割付の製品を割り付ける母材を選定する必要がある。この選定のために、後述する式（７）と式（８）とが利用される。
たとえば、図３の第１の仮割付状態では、製品（１）と（２）が母材１に仮割付されており、未割付の製品（３）と（４）は１つの母材２に割付けることができることがわかるので、式（８）により母材２が選定される。
また、図３の第２の仮割付状態では、製品（１）と（４）が母材２に仮割付されており、未割付の製品（２）と（３）は１つの母材２に割付けることができることがわかる。【００２６】
さらに、図３の第３の仮割付状態では、製品（１）が母材３に割付けられているが、未割付の製品（２）、（３）および（４）をすべて割付けるためには、母材２と母材３とが必要であることがわかる。この場合は、３つの未割付の製品を割り付けるために、２つの母材（２，３）が選定される。
そして、このように残った未割付の製品をすべて割付けるのに必要な母材を選定した後、仮割付処理ですでに選択されていた母材の長さと、上記選定によって選択された未割付製品に使用される母材の長さとの合計長さが、最小となる仮割付状態を割付候補とする処理を行う。【００２７】
たとえば、図３において、３つの仮割付状態に対して、それぞれ、使用する各母材の長さの合計長さが計算される。第１の仮割付状態では、製品（１）と（２）とが母材１に割付られ、残りの製品（３）と（４）とが母材２に割付けられる。この状態では、母材１と母材２とが使用されるので、使用する母材１と母材２の合計長さ（６０００＋４９００＝１０９００）が計算される。【００２８】
同様に、割付候補とはならなかった第２の仮割付状態では、使用する母材は、２つの母材２であるので、使用する母材の合計長さは、４９００×２＝９８００となる。
また、仮割付処理で割付候補とされていた第３の仮割付状態では、使用する母材は、２つの母材３と１つの母材２であるので、使用する母材の合計長さは、３０００×２＋４９００＝１０９００となる。
この場合、計算された３つの合計長さのうち最小のものは、第２の仮割付状態であるので、合計寸法が最小となる第２の仮割付状態を、割付候補として選択し直すことになる。割付候補としてメモリに記憶されていた情報が、選択見直し後の第２の仮割付状態の情報に置きかえられる。【００２９】
すなわち、ステップＳ１０４において、第３基準工程が実行されることにより、ステップＳ１３３で選択された割付候補が、他の仮割付状態に変更されたことになる。ただし、第３基準工程による見直しが行われても、割付候補が変更されない場合もある。
なお、この第３基準工程による選択見直しが実行されると、すべての製品の第１基準工程を利用した割付けが終了したことになる。【００３０】
次に、ステップＳ１０６では、第１歩留計算工程が実行される。
ここでは、具体的には、後述する数式（５）による計算が行われる。これにより、第１基準工程で割付けが終了した全製品と使用した全母材についての全体の歩留（ｙ１）が求められる。
以上により、第１基準工程によって適切と考えられる製品の割付けが終了するので、その割付結果がメモリに記憶される。ここで、割付結果とは、上記歩留（ｙ１）と、使用すべき母材のデータと、その母材それぞれについて対応づけられた製品のデータを含むものである。【００３１】
次に、ステップＳ１０７において、第２基準工程による割付処理が行われる。
ここで、ステップＳ１４１の仮割付処理と、その後のステップＳ１０８と、ステップＳ１０９と、ステップＳ１１０の処理内容は、それぞれステップＳ１３１、Ｓ１０３、Ｓ１０４およびＳ１０５と同様である。
ステップＳ１４２における第２算出処理は、材料歩留を算出する代わりに、ある１つの仮割付状態に対して、その仮割付に使用した各母材について、製品が割り付けられていない部分の残材寸法（長さ）を算出する点が、ステップＳ１３２と異なる。【００３２】
図２の場合で説明すると、１回目の仮割付で２つの仮割付状態（母材１、母材２）が生成されているが、それぞれの仮割付状態の母材について、残材長さを算出する。たとえば、図２の母材１については、製品（１）と（３）とが仮割付されているが、その母材１の長さから、製品（１）と（３）の合計長さを引いたものが、母材１の残材長さである。
同様に、母材２については、母材２の長さから、製品（１）と（６）の合計長さを引いたものが、母材２の残材長さである。ここでは、２つの残材長さが算出される。【００３３】
次の第２選択工程（ステップＳ１４３）では、算出された残材寸法（長さ）のうち、最も小さな残材寸法（長さ）を持つ仮割付状態が、選択候補として選択される。
上記図２の場合は、２つの仮割付状態（母材１、母材２）のうち、母材２の方が残材寸法（長さ）が短いので、母材２の仮割付状態の方が選択候補として選択される。
その後、上記した第１基準工程と同様に、ステップＳ１０８、Ｓ１０９およびＳ１１０の処理が行われ、すべての製品の割付けに使用したすべての母材についての残りの寸法の合計が最も小さくなる仮割付状態が割付候補として選択される。ただし、第３基準工程（ステップＳ１０９）が行われた場合は、割付候補が別の仮割付状態に変更される場合もある。【００３４】
次に、ステップＳ１１１において、第２基準工程を実行することにより選択された選択候補に対して、歩留（ｙ２）の計算を行う。この歩留計算の内容は、ステップＳ１０６と同様の処理である。
さらに、ステップＳ１１２において、計算された２つの歩留ｙ１とｙ２との比較を行い、大きな数値を持つ方の割付候補を、最終的な割付状態として決定する（ステップＳ１１３、Ｓ１１４）。決定された割付状態を示す情報（母材および製品のデータ）は、メモリに保存されると共に、必要に応じて印刷、表示される。【００３５】
以上のような図６のフローは、この発明の割付方法で行われる全体処理の概要を示したものである。この図６の全体処理と同一の処理を、後述する表１と図４に、別の形態で示している。
図６と表１において、主として、ステップＳ１０１とＳｔｅｐ１および２とが対応し、ステップＳ１０２およびＳ１０７とＳｔｅｐ３〜６とが対応する。また、ステップＳ１３１およびＳ１４１とＳｔｅｐ３〜５とが対応し、ステップＳ１３２およびＳ１３３とＳｔｅｐ６とが対応する。さらに、ステップＳ１４２およびＳ１４３も、Ｓｔｅｐ６に対応する。【００３６】
また、ステップＳ１０３およびＳ１０４と、Ｓ１０８およびＳ１０９は、Ｓｔｅｐ７に相当する。
ステップＳ１０５とＳ１１０は、Ｓｔｅｐ８に対応する。
ステップＳ１０６とＳ１１１は、Ｓｔｅｐ９の一部と対応する。
ステップＳ１１２、Ｓ１１３およびＳ１１４は、Ｓｔｅｐ１０に対応する。
以下の実施例で説明する処理や測定結果は、この図６に示した概略処理を実現したものである。【００３７】
図６に示したソート処理（工程）、仮割付処理（工程）、第１基準工程、第２基準工程および第３基準工程の処理、第１および第２算出処理（工程）、第１および第２選択処理（工程）、第１および第２歩留計算処理（工程）、比較処理（工程）、および割付決定処理（工程）は、マイクロコンピュータを搭載したパソコン等のコンピュータで実行される。
また、各処理の機能は、ＣＰＵ，ＲＯＭ，ＲＡＭ，Ｉ／Ｏコントローラ，タイマー等を備えたマイクロコンピュータによって実現され、ＣＰＵが、ＲＡＭやハードディスク等のメモリに保存されたプログラムに基づいて、各種ハードウェアを動作させることにより実現される。【００３８】
この発明の材料分割方法を実現するプログラムは、ＲＯＭ等の半導体記憶素子に固定記録した形態で提供してもよく、その他にＣＤ−ＲＯＭ，ＤＶＤ，フラッシュメモリ等の可搬型の記録媒体に保存した形態で提供してもよい。さらに、このプログラムを遠隔地のサーバに保存しておき、インターネットのようなネットワークを介して、パソコン等の端末へダウンロードするような形態で提供してもよい。【００３９】
プレカットCSPは１次元のBPPとしてモデル化できるが、通常BPPは１種類の容量のビンを扱うが今回のプレカットCSPは母材長が数種類あり、複数容量のビンを想定する意味でより汎用的である。以下に同一断面形状、樹種、等級仕様をもつ製品群毎にGAを適用することとし、まず複数種のビンを扱う一次元マルチBPPを定義する。
ｍ種類の容積ｂt（ｔ＝１，．．，ｍ）ビンが十分にあり、これに容積ｌi（ｉ＝１，．．．，ｎ）のアイテムをすべて入れるとき、容積ｂtのビン種別ｔのビンの使用コストをｃｔ、ビンｋ（ｋ＝１，２，．．．）のビン種別をｔkとすると、一次元マルチBPPは、【００４０】
【数１】
2009038196.tif 000003
【数２】
2009038196.tif 000004
【数３】
2009038196.tif 000005
【数４】
2009038196.tif 000006
【数５】
2009038196.tif 000007
と表せる。(2)式はビンに入れるアイテムの容積合計がビンの容量以下であること、(3)式はすべてのアイテムをどれかのビンに入れること、(4)式は１つのアイテムが同時に複数のビンにははいらないことを示している。
上記に対して、ビンをプレカット母材に、容量別のビンの集合を長さ別の母材（以下、母材種と表記）の集合に、ビンに入れるアイテムを切り出す製品に置き換え、容積を長さに読み替えればプレカットCSPとなる。通常プレカットでは歩留最大を狙うのが一般的である。歩留ｙは次式で表され、【００４１】
【数６】
2009038196.tif 000008
ここで分子の製品長累計は所与であるので、(1)式で使用コストｃtを母材長ｂtに置き換えて
【数７】
2009038196.tif 000009
とすればよい。なお、プレカットでは、母材の両端を整える「鼻切」（母材の両端の形状を整えるための両端切り落としのこと）および製品を切り出す際の「鋸代」（切断時に鋸の厚さ分が切り屑となって損失すること）を考慮する必要があるが、本質的な問題ではない。【００４２】
一般のBPPにおけるFirst Fit 法は、並べられたビンの例えば常に左から順にアイテムを入れるスペースがあるかどうかを調べ、最初に見つかった必要なスペースのあるビンにそのアイテムを当てはめていく解法である。あらかじめ対象とする製品(アイテム)のオーダーがすべて分かっている場合は、すべての製品を大きさ(長さ)の降順にソートし、その順に必要なスペースのあるビンをサーチして当てはめていく(First Fit Descending:FFD)ほうが、ランダムに当てはめるよりいい結果が得られる。【００４３】
一次元BPPにおけるFFDは、大きさの降順に取り出したアイテムに対してそれが入る余地のあるビンを順にサーチし、最初に見つかったビン(該当のビンが無いときは新たなビン)に割付けるというアルゴリズムである。これをビンの側からみると、大きさの順に入れることのできるアイテムをビンが満杯になるまでに入れることになる。本モデルでは母材の長さ(ビンの容量)が複数種類あるためこのFＦDはそのままでは使えない。そこで次のようなアルゴリズムを検討した。
長さの降順にソートした製品をそれぞれの母材種の母材１本に上記FＦDルールで割付けてみて、もっとも「良い割付け」のできた母材とその割付を採用するという操作を、すべての製品が割付済になるまで繰り返す。このとき、先頭の最も長い製品は必ず割付けることにする。これは長い製品を最後のほうに残すことは適当でないという考え方に基づく。【００４４】
図２は、本発明によるＦＦ（ファーストフィット）法の模式的図であり、ここでは、1回目の割付で、母材3への割付は母材3が製品(1)より短いため行われない。
FFDはその時点その時点で最適と想定される割付を行うアルゴリズムであり先まで見通した割付けではないため、終盤になると歩留の悪いビンが発生する傾向がある。本モデルでは複数の母材種を扱うことを生かし、複数の母材種からいかにうまく対象母材を選択し全体の歩留を上げるかを検討する。まず母材への「良い割付け」についての選択基準を以下のように設定した。
基準１：歩留基準・・・最も歩留の高い割付け
基準２：残材長基準・・・最も母材の残材長の短くなる割付け
基準１と２は母材種が1種類のときは同等であるが複数種のときは違ってくる。割付全体の歩留は(5)式で与えられるが、ある割付過程のその時点で最も高い歩留となる選択を与えるのが「基準１」である。一方、「基準２」は、製品の並びが母材に置き換わっていくにつれて、分母の母材長合計が最初は製品長合計であったものが母材長合計と残製品の合計に変わっていくと考えた場合、最も増加分が少ない選択基準である。しかし「基準２」は置き換わった製品の長さとの比率が考慮されていないため、一般には「基準１」のほうが合理的と考えられるが、先に述べたようにFFDは先まで見通した割付けではないため、必ずしも「基準１」が「基準２」よりも良い結果を与えるとは限らない。そこで本モデルでは、それぞれの基準で実行し良い結果が得られた割付を採用することとした。【００４５】
さらに、FFDの特徴である「終盤になると歩留の悪いビンが発生する傾向」を少しでも回避するため次の「基準３」を設け、「基準１」または「基準２」による選択結果を「基準３」によって見直すこととする。
基準３：母材長基準・・・その割付け以降の割付に必要な母材が最小となる割付け「基準３」はすべての割付けに適用すれば(6)式の目標そのものであるが、割付け全体を見通せないと適用できない。未割付製品に対する最終的な割付けが見通せる段階になった時点で適用する。ある段階の母材種tの母材への仮割付の結果まだ未割付となっている製品の長さ合計をｌ(t)resとしたとき、b(t)を次のように定義する。
【数８】
2009038196.tif 000010
【数９】
2009038196.tif 000011
このときb(t)は、「母材種ｔの母材へ割付けた場合、残りの製品をすべて割付けるために少なくとも必要な母材の長さ合計」となる。特に0＜ｌ(t)res≦ｂmaxのときは、次の割付b(t)けでの長さの母材に残りのすべての製品を割付けることができることを意味する。ｂmax＜ｌ(t)resのときは、すべての正確な必要母材を見通すことはできないが、ｌ(t)resが2本以上の母材の組合せで最も短い組合せ(ｂmin+ｂmin)あるいはその次に短い組合せ(ｂmin+ｂmin+1)以下であれば、次回と次々回の割付けでそれぞれの組合せの母材を使えば割付けが終了する。【００４６】
ある段階の製品ｉを先頭とする製品群への仮割付で、「基準１」または「基準２」を適用した結果、母材種ｔｄの母材が選択されたとする。この選択による残製品の合計長ｌtdresと、その他の割付可能母材種ｔの母材への割付で得られるｌtresについて、
【数１０】
2009038196.tif 000012
となった時点から「基準３」による見直しを行う。後半の条件は少なくともひとつの母材への仮割付けは、残りの製品に対する最終的な割付けが見通せる段階になったことを意味する。【００４７】
見直しは以下のように行う。製品ｉを先頭とする製品群への仮割付で、母材種ｔの母材の長さｂｔと(7)式で計算されるｂ(t)について
【数１１】
2009038196.tif 000013
となるｔminに対して
【数１２】
2009038196.tif 000014
ならば先に選択されたｔdの母材への割付けを見直して母材種ｔminの母材への割付けを採用する(図3)。【００４８】
図３は、本発明の基準３による第３の手順工程を示し、(10)式のｔminは、今回割付けた母材と次回以降に割付ける母材の長さの合計がもっと短くなる母材の母材種であり、(11)式はそれが先の「基準１」あるいは「基準２」によって選ばれた母材種ｔdではないことを意味している。【００４９】
以上をまとめると、次の処理の流れとなる（表１に示す）。「基準ｘ」(x=1,2)で選択し「基準3」で見直すプロセスによって得られたロット全体の歩留を歩留(ｘ)と表現する。
【表１】
2009038196.tif 000015
【００５０】
表２には、母材１本に対するＦＦＤ割付けルールを示す。
【表２】
2009038196.tif 000016
【００５１】
図４は、表１をフロー図として示すものである。【００５２】
First Fit法の弱点は先まで見通した割付けではないことであるが、本アルゴリズムでは複数の母材種の母材に対して仮割付けを行い、
（１）２つの基準（「歩留基準」と「残材長基準」）でそれぞれ実行し、良い結果の得られた母材への割付結果を採用する。
（２）さらに未割付製品に対して、次の割付で全体の割付が完了する目処がつく段階になったら、今回使用した母材と次回以降に割付ける母材の長さの合計を各母材について比較し、上記（１）で採用した母材を見直す。
ことによって、この弱点を補っている。
【実施例１】
【００５３】
本願の改良FFD（本願ＦＦＤと呼ぶ）を、ある住宅メーカーが受注した標準的な木造一戸建て住宅の、横架材について行った。これらの横架材は、断面サイズや樹種、等級など同じ母材から切り出すことができる約20のロットにグループに分けることができ、それぞれのロット毎に切り出す製品数や使用する母材群も異なる。本願FFDはロット毎に適用した。なお鼻切は0mm、鋸代は5mmと設定した。【００５４】
比較のため公開されている特許文献１（従来法と呼ぶ）のアルゴリズムを適用する。このアルゴリズムはすべての製品の長さ合計に対してその合計長以上になる複数母材長の母材の組み合わせをリストアップし、リストアップした母材の組み合わせで母材長合計の昇順にすべての製品が割付けられるかを判断するステップと、割付け可能な最小母材長合計の組み合わせに対して、さらに母材長合計が小さくなる母材の組み合わせを探査するステップからなる方法である。【００５５】
16ロット201本の横架材製品からなる邸１と18ロット199本の邸2のデータについての実行結果の比較を表1に示す。図3で示した仕様のパソコンでの本改良FFDの実行時間は1邸分すべてのロット完了までは約1秒である。従来法は別のパソコンによる実運用システムでの結果であり厳密には比較できないが、取り合わせ計算部分の処理時間は数分と想定される。
各ロットにより従来法との優劣は違うが、全体では遜色のない結果が得られた。全体の材積歩留は、邸１では従来法で93.37%に対して本願FFDで93.80%、邸2では従来法94.60%，本願FFDが94.45%となった。
さらに上記を含む10邸の木造住宅について、全体の材積歩留の比較をした結果を表3に示す。この10邸分のデータでは、邸2を除いてすべて本願FFDが優位となっており、邸5および邸6ではほぼ1%の歩留優位となった。【００５６】
【表３】
2009038196.tif 000017
【００５７】
【表４】
2009038196.tif 000018
【００５８】
表５に「基準１」のみを適用した場合とさらに「基準２」と「基準３」を適用した場合の歩留を比較した。基準の「2」と「3」の欄は基準１さらに２つの基準が適用され歩留が向上した場合の原因となった基準を“*”でマークしている。たとえばロット1では、基準１では93.43%であったが基準2を適用して93.74%となった。またロット8では、基準１のみの適用では95.87%であったが、基準3の見直し効果により96.89%となった。【００５９】
【表５】
2009038196.tif 000019
表６には邸別に「基準１」のみを適用した場合とさらに「基準２」と「基準３」を適用した場合の歩留を比較した。また「2」と「3」欄に追加の２つの基準の適用で歩留が向上したロットの数をその原因の基準別に示した。
基準の組み合わせ適用が、歩留向上に明らかに有効であることが確認できる。【００６０】
【表６】
2009038196.tif 000020
尚、邸１での割り付け結果については、付表１として図５に示す。【００６１】
以上の実施例では、木材を割付ける対象とした場合について説明したが、この発明の割付方法を適用することで、ほとんどの場合、従来よりも歩留を向上させることができた。
このように材料の歩留を向上させることは、使用する材料の節約につながり、使用されない廃材がでることをより少なくすることができ、資源の有効活用にもなる。
また、歩留が向上することにより、たとえば１件の家を建築するのに使用する母材の数量を減らすことができるので、建築コストの低減や、母材の運搬作業の効率向上を図ることができる。
さらに、１本当たりの単価が木材よりも高い鋼材の割り付けにこの発明の割付方法を適用した場合は、歩留の向上による材料コストの低減効果は、木材に比べてより大きいものとなる。
たとえば、多量の木材や鋼材を取り扱う業者にとっては、１軒当たりわずかな歩留の向上であったとしても、事業全体としては大きなコストダウンを図ることができる。
また、この発明の割付方法は、上記したように、ほぼリアルタイムに近い短時間で適切な割付結果を得ることができるが、生産計画の見直し、設計変更あるいは母材群の変更などの急な状況の変化があった場合でも、処理時間の短いこの発明の割付方法を再度適用することで、計画業務の効率の向上を図り、その状況変化に合わせて迅速な対応をすることが可能となる。
【産業上の利用可能性】
【００６２】
多くのプレカット工場ではベテラン作業員の経験による操業がされており、90%以下の歩留であることを考えると、当アルゴリズムは簡便に導入ができ簡単な操作で高速に結果が得られる方法として、有効と考えられる。
また、提案した本願の改良FFDは、複数の積載可能量のトラックへの荷物の積載取り合わせなど、多くの適用が可能である。
【図１】
2009038196.tif 000021
【図２】
2009038196.tif 000022
【図３】
2009038196.tif 000023
【図４】
2009038196.tif 000024
【図５】
2009038196.tif 000025
【図６】
2009038196.tif 000026
【国際調査報告】
2009038196.tif 000027
2009038196.tif 000028
2009038196.tif 000029