(57)【特許請求の範囲】
【請求項１】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【請求項２】
請求項１に記載の部材割付システムにおいて、
探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材割付システム。
【請求項３】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材加工装置。
【請求項４】
請求項２に記載の部材加工装置において、
探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材加工装置。
【請求項５】
コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラム。
【請求項６】
コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項７】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、
前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、
前記探索制御手段が、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するステップと、
前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置に関する。
【背景技術】
【０００２】
住宅構造材のプレカットには、断面形状や樹種，等級、レイヤといった仕様ごとに数種類の長さ (主に3m〜6m)の原材料が用意される。そこから決められた長さの部材(製品)を切り出す。一般的な大きさの住宅の場合、梁、桁、土台など横架材とよばれる構造材には約20種類の仕様がある。製品の仕様ごとに用意された数種類の長さの原材料から、これらの構造材がそれぞれ平均10本、１棟分を合計すると約200本の製品が切り出される。製品の仕様と、製品のサイズと、切り出される原材料の組合せにより、原材料から切り落とされて無駄になる部分の量が異なる。そこで、部材割付方法を改善する技術が開発された（特許文献１参照）。
【特許文献１】特許３５６５２６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記のような部材割付方法の計算の目的は、製品の仕様ごとに用意された数種類の長さの原材料群から要求製品をいかに少ない原材料（歩留最高）で切り出すかということにある。他にも、各種の技術が開発されているが、これらの技術を利用したプレカット工場での割付方法では概ね90%程度といわれている。一定の規格で設計生産される建物の場合には、原材料のサイズに適合する構造材のサイズを決めておくと、さらに歩留を向上させることができる。しかしながら、注文生産により多種多様の設計に基づき、構造材を原材料から切り出す場合には、さらに歩留を向上させる計算方法の開発が求められている。実際に、１％の歩留を向上させるだけでも、多量の廃棄物減量を図ることができる。本発明は既存の部材割付方法の計算結果を利用して、製品の仕様ごとに用意された数種類の長さの原材料群から要求製品を切り出す組合せの最適化をする部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【０００５】
予め任意の方法で求めた初期実行可能解を割付パターンベクトルに含めてシンプレックス演算処理をするので、多数の組合せのある演算処理の最適解探索範囲を当初から狭めることができる。また、始めに、緩和した第３制約条件式０≦ｘi≦１を使用して、シンプレックス演算処理をさせるので、目的関数値の最小値を容易に探索できる。即ち、初期実行可能解の目的関数の値を最大値とし、シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し第２制約条件式Ｃｘ＝ｄと緩和した第３制約条件式０≦ｘi≦１を生成して、改めてシンプレックス演算処理を実行できる。これにより、さらに短時間で、最適値を求める演算処理が実行できる。また、単に原材料長の合計値の減少だけでなく、原材料の種類に応じた加工費用等の成分を、原材料長に含める。これにより、計算は原材料長についてのみ行われても、原材料の価格を考慮した割付の最適化ができる。
【０００６】
〈構成２〉
構成１に記載の部材割付システムにおいて、探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材割付システム。
【０００７】
組合せリストのリストアップ量が多量の場合の長時間の演算処理継続を防止する。
【０００８】
〈構成３〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材加工装置。
【０００９】
構成１の演算処理機能を組み込んだ部材加工装置は、該当する製品長や材料長を指定すると、自動的に、最適割り付けで製品の切り出しを行う。
【００１０】
〈構成４〉
構成２に記載の部材加工装置において、探索制御手段は、２回目以降のシンプレックス演算処理の繰り返し回数に上限値を設けることを特徴とする部材加工装置。
【００１１】
〈構成５〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラム。
〈構成６〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【００１２】
〈構成７〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘi≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、
前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、
前記探索制御手段が、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するステップと、
前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【発明を実施するための最良の形態】
【００１３】
本発明では、既存の任意の方法で得られた実用性のある解を基礎にして、それをシンプレックス法で評価し、さらに改善した解を求める。シンプレックス法は、線形計画問題の最適解を探索する方法として知られている。しかし、求められた製品長の種類や原材料の種類が数十種類にも及ぶと、組合せの数は数十万組を越えることがある。ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける、といった条件に基づいてそのまま演算処理のためのパラメータを作ると、最適値探索のためのシンプレックス演算処理に時間がかかりすぎるおそれがある。そこで、本発明では、シンプレックス法による演算処理のための制約条件を付加して、比較対象範囲の絞り込みをしながら、効率よく計算をする。以下、本発明の実施の形態を実施例ごとに詳細に説明する。
【実施例１】
【００１４】
図１は実施例１の部材割付システム１０のブロック図である。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、建物の構造材をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献１に記載されたとおりのものを使用することができる。
【００１５】
コンピュータ１２には、演算処理装置２０と記憶装置４０とが設けられている。演算処理装置２０には、図のように、製品長設定手段２１、原材料長設定手段２２、初期設定手段２３、割付パターンベクトル生成手段２４、割付パターン行列生成手段２５、制約条件生成手段２６、費用係数ベクトル生成手段２７、目的関数生成手段２８、シンプレックス演算処理手段２９、及び探索制御手段３０等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。
【００１６】
記憶装置４０には、図のように、製品長ベクトルLp４１、製品要求数量ベクトルｂ４２、原材料長ベクトルLm４３（または費用係数ベクトル）、初期実行可能解４４、原材料使用予定数量ベクトルｄ４５、割付パターン行列４６、原材料使用行列Ｃ４７、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０、目的関数５１、組合せリスト５２及び部材割付データ５３等のデータが記憶されている。これらのデータはいずれも、上記のコンピュータプログラムの動作により生成されて、記憶装置４０に記憶されるものである。続いて、これらのコンピュータプログラムと記憶装置４０に記憶されるデータの具体的な説明をする。
【００１７】
図２は、部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
部材割付システム１０の具体的な機能を説明する前に、部材割付システム１０のハードウエアを説明する。図のように、コンピュータ１２の本体ケース３中に収められた内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５と、ネットワークインタフェース１１６とが接続されている。入出力インタフェース１１５には、ディスプレイ３とキーボード４とマウス５とが接続されている。ネットワークインタフェース１１６には、ネットワーク１４を介して、端末装置１６が接続されている。以上のハードウェアは一般的によく知られたパーソナルコンピュータに備えられているものと変わらない。端末装置１６は、プレカット装置１７の部材選択供給装置１２０に、部材割付データを５３を供給する。これにより、指定された原材料が部材切断装置１２１に供給され、指定された割付パターンで切断される。切断された製品は製品搬送装置１２２により搬送され排出される。
【００１８】
図１に示した記憶装置４０は、ＲＯＭ１１２やＲＡＭ１１３やＨＤＤ１１４により構成される。図１に示した演算処理装置２０は、ＣＰＵ１１１、ＲＯＭ１１２、ＲＡＭ１１３等により構成される。各種の情報は主としてＨＤＤ１１４に記憶されて保存される。ＣＰＵ１１１が実行するコンピュータプログラムは、ＲＯＭ１１２に記憶され、あるいはＲＡＭ１１３に適時ロードされる。端末装置も同様の構成で構わない。ネットワークはインターネットでもイントラネットでも構わない。
【００１９】
図３は、演算処理のパラメータを説明するための説明図である。
この図を参照しながら、演算処理に使用するパラメータの定義と、上記の各コンピュータプログラムの機能を説明する。
［製品長ベクトルLp］
生産されるべき製品の数量をｍとする。図の例では、ｍ＝７である。
製品長をLp1,Lp2,…,Lpmと表現する。単位は例えば、ｍ（メートル）である。
ｍ次の製品長ベクトルLpを下記のように定義する。
Lp＝（Lp1,Lp2,…,Lpm）
但し、（Lp1≧Lp2≧…≧Lpm）
図の例では、Lp＝（Lp1,Lp2,Lp3,Lp4,Lp5,Lp6,Lp7）である。
【００２０】
［製品要求数量ベクトルｂ］
数量ｍの製品の生産が要求されているとき、製品要求数量ベクトルｂを、下記のように定義する。なお、この実施例では、全てｂi＝１として説明をする。ｂiは任意の正の整数でよい。
ｂ＝（ｂ1,ｂ2,…,ｂm）T
（上付きＴは転置を表す。ｂは列ベクトルである。以下も同様）
図の例では、ｂ＝（１，１，１，１，１，１，１）Tである。
製品長設定手段２１は、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLp４１と、製品要求数量を要素とする製品要求数量ベクトルｂ４２を生成して、記憶装置に記憶させる記憶装置４０に記憶させる。
【００２１】
［原材料データ］
原材料にはｋ種類の長さのものが含まれている。図の例では、ｋ＝３である。
原材料長をLm1,Lm2,…,Lmkと表現する。単位は例えば、ｍ（メートル）である。
ｋ次の原材料長ベクトルLmを下記のように定義する。
Lm＝（Lm1,Lm2,…,Lmk）
但し、（Lm1＞Lm2＞…＞Lmk）
図の例では、Lm＝（Lm1,Lm2,Lm3）である。
原材料長設定手段２２は、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLm４３を生成し、記憶装置４０に記憶させる。
【００２２】
［原材料使用予定数量ベクトルｄ］
原材料使用予定数量ベクトルｄ４５は、実現可能なある解に対して、ｋ種類の長さの材料がそれぞれ何本ずつ使用されるかを示す。これを下記のように定義する。
ｄ＝（ｄ1,ｄ2,…,ｄk）T
図の例では、ｄ＝（ｄ1,ｄ2,ｄ3）T＝（１，２、１）Tである。原材料使用予定数量ベクトルｄ４５は、後で説明する第３制約条件式で使用される。
【００２３】
［使用本数ベクトルｘ］
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、選択したｎ本の原材料の使用本数を表すｎ次の使用本数ベクトルｘを、下記のように定義する。なお、ｋ種類の原材料からｎ本の原材料を選択するとき、同一の原材料を２度以上重複して選択して構わない。下記の例では、,原材料長Lm2の原材料が２本重複して選択されている。
ｘ＝（ｘ1,ｘ2,…,ｘn）T
例えば、上記の具体例では、Lm1,Lm2,Lm2,Lm3と列挙された４本の原材料に対して、それぞれ求められている製品を割り付けた。このとき、最初のLm1に対してｘ1、２番目のLm2に対してｘ2、３番目のLm2に対してｘ3、４番目のLm3に対してｘ4を設定する。図の例では、ｘ1＝ｘ2＝ｘ3＝ｘ4＝１である。選択される原材料と選択されない原材料とを列挙したとき、選択されない原材料に設定されるｘｉの値は０である。即ち、ｎ次の使用本数ベクトルｘの各要素ｘiは０または１である。使用本数ベクトルｘは制約条件式で使用される。この取り扱いは実施例３でより具体的に説明する。
【００２４】
［割付パターンベクトルａj］
いずれか１本の原材料から、数量ｍの製品のうちのいずれかを切り出すように割り付けたデータを、ｍ次の割付パターンベクトルａjで表す。これを下記のように定義する。
ａj＝（a1,a2,…,am）T
下記に、図の例における割付パターンベクトルを示す。
Lm1にLp2とLp6をそれぞれ１本割付ける  （０，１，０，０，０，１，０）T
Lm2にLp1を１本割付ける                （１，０，０，０，０，０，０）T
Lm2にLp3とLp5をそれぞれ１本割付ける  （０，０，１，０，１，０，０）T
Lm3にLp4とLp7をそれぞれ１本割付ける  （０，０，０，１，０，０，１）T
【００２５】
上記の割付パターンベクトルａjは、下式を満足するように生成される。
Ｌp・ａj≦Ｌ  （ｊ＝1,2,…,n）
この式の左辺の積（Ｌp・ａj）は、選択された原材料に割り付けられた、１本の製品長もしくは複数本の製品長の総和である。この長さを割り付けることができる最小長さLmiの原材料が選択される。Ｌは、その選択された原材料の長さLmiを示す。なお、実加工では、矩を出すためのハナ切り長、刃物厚が考慮されるが、ここでは無視する。
【００２６】
例えば、図の例では、Lm2にLp3とLp5をそれぞれ１本割付けるとき、原材料Lm1またはLm2のいずれにも割付ができる。しかし、Lm1＞Lm2だから、割付対象をLm2とする。こうして、経済的に割り付けできる関係を見つける。
図の例は、実行可能解に相当する一組の割付パターンベクトルを列挙した。しかしながら、シンプレックス法で最適解を求めるための準備として、想定可能なできるだけ多くの割付パターンベクトルを予め列挙しておく。
割付パターンベクトル生成手段２４は、求められているｍ本の製品の製品長データと用意されたｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトル４６ａを生成し、記憶装置４０に記憶させる。
【００２７】
［割付パターン行列］
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付けるときには、上記の割付パターンベクトルをｎ個並べる。ａjをｎ個並べたｍ×ｎ次の割付パターン行列を下記に定義する。
Ａ＝（ａij）  （ｉ＝1,2,…,ｍ、ｊ＝1,2,…,ｎ）
割付パターン行列生成手段２５は、割付パターンベクトル生成手段２４の生成した割付パターンベクトル４６ａをｎ個並べたｍ×ｎ次の割付パターン行列を生成し、記憶装置４０に記憶させる。
【００２８】
［第１制約条件］
割付パターン行列Ａと使用本数ベクトルｘとの積は、選択された各原材料から、それぞれ該当する割り付けパターンで切り出した製品数になる。従って、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならない。求められている各製品の数量は、製品要求数量ベクトルｂに相当する。従って、少なくとも、下式を満足しないと、必要な数の製品が得られない。
Σａij・ｘj≧ｂi
なお、不等号が成立するときは作りすぎである。計算の便宜上、上記の不等式を制約条件とする。この制約条件式は、Ａｘ≧ｂと表す。
図の例では、生産された製品数も必要な製品数も７であって、等号が成立する。
制約条件生成手段２６は、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上であるとする第１制約条件式を生成して、記憶装置４０に記憶させる。
【００２９】
［原材料使用行列Ｃ］
ｋ種類の原材料のうちのどの原材料を使用するかを示す、ｋ次の原材料使用ベクトルｃjを次のように定義する。
ｃj＝（ｃ1j,ｃ2j,…,ｃkj）T
但し、ｃ1j,ｃ2j,…,ｃkjはいずれも、０または１である。
上記のように、ｋ種類の原材料から選択したｎ本の原材料を表すのに、原材料使用行列Ｃを用いる。これをｃjをｎ個並べたｋ×ｎ次の行列で定義する。
Ｃ＝（ｃij）（ｉ＝1,2,…,ｋ、ｊ＝1,2,…,n）
図の例でｃijは、下記のとおりである。
ｃ1＝（１、０、０）T
ｃ2＝（０，１，０）T
ｃ3＝（０，１，０）T
ｃ4＝（０，０，１）T
割付パターン行列生成手段２５は、各割付パターンで、ｋ種類の原材料のうちのどの原材料を使用するかを示す原材料使用ベクトルｃjを列挙した、ｋ×ｎ次の原材料使用行列Ｃを生成して、記憶装置に記憶させる。
【００３０】
［第２制約条件］
なお、ｃjはｋ種類の原材料のうちの一つを指定するベクトルだから、下式を満足する。
Σｃij＝１
ｋ個の数字のうち１個だけが１で他は全て０ということである。
また、各原材料の長さは、割付けできる最小長さのものが選択される。
ΣＬmi・ｃij＝Ｌ
このLは、割付パターンベクトルの生成条件Ｌp・ａj≦Ｌで示した値である。
【００３１】
また、既に定義したとおり、ｎ本の原材料の使用本数ベクトルｘは、ｘ＝（ｘ1,ｘ2,…,ｘn）であった。また、原材料使用予定数量ベクトルｄは、原材料長さごとの使用数を示すものであった。
従って、下式の条件が満足されなければならない。
Σｃij・ｘj＝ｄi（ｉ＝1,2,…,ｋ）
この制約条件式は、Ｃｘ＝ｄと表す。
これは、どの長さの原材料を何本選択して実際の割付に使用するかを定める。なお、Ａｘ≧ｂとＣｘ＝ｄの制約条件の具体的な関係は、実施例３でより明確に説明をする。
制約条件生成手段２６は、割付パターン行列生成手段２５が生成した原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が、原材料使用予定数量ベクトルｄと等しいとする第２制約条件式を生成して、記憶装置に記憶させる。
【００３２】
［第３制約条件］
上記の使用本数ベクトルｘの各要素ｘiは０または１である。列挙された多数の割付パターンベクトルの中のいずれを選択するかどうかを決める意味をもつからである。従って、下式のような制約条件式が成立する。
ｘi∈｛０，１｝
なお、この実施例では、この制約条件を緩和する。即ち、０≦ｘi≦１という制約条件式を設定する。
制約条件生成手段は、使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１である旨を示す第３制約条件式を生成して、記憶装置に記憶させる。  
【００３３】
［費用係数ベクトル］
長さの違う原材料ごとに、価格だけでなく、運搬費、保管費、加工賃等が異なる。計算に含めるべき全ての費用要素をｎ次の費用係数ベクトルｆに含め、下記のように定義する。
ｆ＝（ｆ1,ｆ2,…,ｆn）
費用係数ベクトルｆは選択されたｎ種類の原材料にのみ適用されるから、ｎ次のベクトルになっている。なお、計算の便宜上、ｆ1,ｆ2,…,ｆnは、費用換算してしまい、単位を円とする。従って、目的関数値が小さいほど、少ないコストで製品を得ることができる。
【００３４】
原材料の価格が長さに比例する場合は、歩留が最高になる場合と総費用が最小になる場合とは同意である。しかし、単位長さ当たりの価格が原材料長により異なる場合には、費用係数を調整する。
費用係数ベクトル生成手段２７は、原材料長ベクトルLmの各要素に価格成分を含めてｎ次の費用係数ベクトルｆを生成する。費用係数ベクトルｆの要素ｆiは、単位が円のデータである。費用計数係数ベクトル生成手段２７は原材料長ベクトルLmを費用係数ベクトルｆで置き換えるようにすれば、以下は、費用係数ベクトルｆを意識することなく演算処理ができる。
【００３５】
［目的関数］
この計算では、ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、目的関数値が小さいほど少ないコストで製品を得ることができる。そこで、選択したｎ本の原材料にかかる費用の総和を示す目的関数を下記のように定義する。
Ｍｉｎ  Σｆi・ｘi
目的関数生成手段２８は、選択したｎ本の当該原材料にかかる費用の総和を示す目的関数を生成して、記憶装置に記憶させる。
【００３６】
［整数計画を連続緩和問題とする］
シンプレックス法による演算処理を実行するために、目的関数と制約条件を次のように定義する。
Ｍｉｎ        Σｆi・ｘi
subject to.     Ａｘ≧ｂ
Cｘ＝ｄ
０≦ｘi≦１
第１番目の式は、目的関数生成手段により生成された目的関数である。
第２番目の式は、制約条件生成手段により生成された第１制約条件式である。
第３番目の式は、制約条件生成手段により生成された第２制約条件式である。
第４番目の式は、制約条件生成手段により生成された第３制約条件式である。
目的関数は、選択したｎ本の当該原材料にかかる費用の総和を示す。
第１制約条件式は、割付パターン行列Ａと使用本数ベクトルｘと製品要求数量ベクトルｂの関係を示す。
第２制約条件式は、原材料使用行列Ｃと原材料の使用本数ベクトルｘと原材料使用予定数量ベクトルｄの関係を示す。
第３制約条件式は、ｘiが０以上１以下であることを示す。
【００３７】
初期設定手段２３は、任意の方法で取得した任意の初期実行可能解４４を受け付ける。そして、シンプレックス演算処理のためのパラメータを生成する。任意の方法とは、例えばFirst Fit法、特許文献１に記載された方法等である。初期実行可能解は、上記の割付パターン行列Ａ４６から選択される割付パターンベクトルを指定する原材料の使用本数ベクトルｘで表すことができる。これも、実施例３でより具体的に説明をする。最初のシンプレックス演算処理のために入力するパラメータは、目的関数Σｆi・ｘiと第１制約条件式Ａｘ≧ｂと第３制約条件式０≦ｘi≦１を構成するデータである。
【００３８】
探索制御手段３０は、シンプレックス演算処理手段に対して、Cｘ＝ｄの制約条件を除外したパラメータを入力して最初の演算処理を実行させる。シンプレックス演算処理手段は、目的関数の値を改善するようにシンプレックス表の基底変数を変更して解を出力する。第３制約条件式０≦ｘi≦１は、ｘi∈｛０，１｝という制約条件を緩和したものである。従って、解には、ｘi＝０．５といった整数以外のものが含まれる場合もある。また、目的関数の値が同一の解が複数存在することもある。
【００３９】
探索制御手段３０は、得られた解の中に、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解を検出する。検出されたときは、その解を最適解として、部材割付データ５３を生成して、処理を終了する。それ以外の場合には、探索制御手段は、次のシンプレックス演算処理のためのパラメータを再生成する。まず、初期設定をした実行可能解の目的関数の値Ｆ０を最大値に設定する。初期設定の解を改善するのが目的だからである。また、最初のシンプレックス演算処理で得られた解の目的関数の値Ｆ１を最小値に設定する。条件を緩和して得られた解であるから、そのときの目的関数値が限界値と判断する。
【００４０】
次に、探索制御手段３０は、目的関数の値がＦ１以上、Ｆ０以下となる、原材料の本数の組合せを列挙して、組合せリストを生成する。これは、原材料使用予定数量ベクトルｄに該当する。この組合せリストの中から目的関数の値が最小のものを次候補に選定する。この具体例は実施例３で説明するが、制約条件生成手段２６は、第２制約条件式Cｘ＝ｄを生成する。目的関数や割付パターンベクトル等のパラメータに変更があれば第１制約条件式Ａｘ≧ｂも生成する。その後、探索制御手段３０は、シンプレックス演算処理手段２９に対して、生成したパラメータを入力して演算処理を実行させる。第３制約条件式０≦ｘi≦１は変更しない。
【００４１】
その結果、得られた解に、ｘiの値がいずれも０または１であって、それ以外の値を含まないものを検出する。検出されたときは、その解を最適解と了する。それ以外の場合には、原材料の本数の組合せのリスト中で、目的関数の値が２番目に小さいものを次候補に選定する。そして、前回と全く同様にして、第２制約条件式Cｘ＝ｄを生成し、パラメータを変更して、シンプレックス演算処理手段に対して、生成したパラメータを入力して演算処理を実行させる。
【００４２】
こうして、シンプレックス演算処理を繰り返して、最適解を探索する。なお、原材料の本数の組合せのリストが多数生成されたときは、原材料の本数の組合せの選択回数に上限を設けて、一定回数以上探索しても最適解がみつからなければ、初期実行可能解を最適解として、部材割付データ５３を出力するとよい。また、以上の演算処理では、割付パターン行列Ａと使用本数ベクトルｘと製品要求数量ベクトルｂの関係を示す制約条件を使用したので、シンプレックス演算処理のパラメータに製品長が含まれず、計算が煩雑にならない。また、各要素が０または１のみの値をとる原材料の使用本数ベクトルｘが基底変数になるようにパラメータを設定し、０≦ｘi≦１という緩和した制約条件でシンプレックス演算処理を実行するので、最適解が得られない場合でも目的関数の最小値を得て、探索範囲を限定することができる。
【実施例２】
【００４３】
図４は、初回のシンプレックス演算処理動作フローチャートである。
これらの図を用いて、上記のシステムを制御するコンピュータプログラムの実施例を説明する。
ステップＳ１１では、原材料長設定手段２２が原材料データの受け付けをする。端末装置１６から、使用される全ての原材料長データの入力を受け付けて、原材料長ベクトルLm４３に対応するデータを生成し、記憶装置４０に記憶させる。ステップＳ１２では、製品長設定手段２１が、製品長と数量の入力受け付けをする。端末装置１６から、求められている製品長データの入力を受け付けて、製品長ベクトルLp４１と製品要求数量ベクトルｂ４２に対応するデータを生成し、記憶装置４０に記憶させる。
【００４４】
ステップＳ１３では、初期設定手段２３が初期実行可能解４４の入力を受け付ける。その結果は  記憶装置４０に記憶される。ステップＳ１４では、割付パターンベクトル生成手段２４が、製品長ベクトルLp４１や原材料長ベクトルLm４３等を比較して、割付パターンベクトルの生成をする。割付パターンベクトルは、記憶装置４０に記憶される。続いて、ステップＳ１５で、割付パターン行列生成手段２５が割付パターン行列４６の生成をして、記憶装置４０に記憶させる。次に、ステップＳ１６で、制約条件生成手段２６が、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０を生成して、記憶装置４０に記憶させる。
【００４５】
ステップＳ１７では、費用係数ベクトル生成手段２７が費用係数ベクトルの生成をし、ステップＳ１８では、目的関数生成手段２８がその費用係数ベクトルを使用して目的関数５１の設定をする。その結果が記憶装置４０に記憶される。次に探索制御手段３０が、ステップＳ１９で最初の演算用パラメータをシンプレックス演算処理手段２９に入力する。ステップＳ２０では、この演算用パラメータを使用したシンプレックス演算を実行する。解が得られたら探索制御手段３０は、ステップＳ２１で、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから、ステップＳ２３で部材割付データを出力して処理を終了する。ノーのときはステップＳ２２の処理に移行する。ステップＳ２２では、探索制御手段３０が、制約条件の変更とシンプレックス法による再演算を制御する。この処理を次の図５を用いて説明する。
【００４６】
図５は、１回目のシンプレックス演算終了後の演算処理のフローチャートである。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数の範囲で、原材料の組合せリストの生成をする。その結果を目的関数の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、Ｃｘ＝ｄの制約条件の設定をする。
【００４７】
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ステップＳ３８のピボット演算処理を繰り返したかどうかを判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。
【実施例３】
【００４８】
図６から図１１までは、具体的な計算例の説明図である。
これらの図を用いて、実際の計算例により、上記の装置の動作をより具体的に説明する。
（原材料データ）
例えば、用意された原材料は５種類である。その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lm1＝６００００
Lm2＝４９０００
Lm3＝４５０００
Lm4＝４００００
Lm5＝３００００
（製品長データ）
求められている製品は７本で、その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lp1＝５３０５０
Lp2＝４４３５０
Lp3＝３０７００
Lp4＝２６２５０
Lp5＝２１０５０
Lp6＝１７８４０
Lp7＝１７１５０
【００４９】
（割付パターンベクトル）
図６の（ａ）は、割付パターンベクトルの説明図である。
図の最も左側の上から下に向かう縦１列に、上記の７種類の製品長が列挙されている。また、最も上段の左から右に向かう横１列に、原材料長が列挙されている。各原材料長の下の縦一列が、それぞれ割付パターンベクトルである。例えば、原材料長が４５０００のものには、製品長が４４３５０のものを１本割り付けることができる。例えば、原材料長が４９０００のものには、製品長が３０７００と１７８４０のものを各１本割り付けることができる。この表には、この要領で、７本の製品の製品長データと５種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す７次の割付パターンベクトルを列挙した。ここで、ｘ１〜ｘ５は初期実行可能解から得られた割付パターンベクトルで、ｘ６〜ｘ１８は追加生成した割付パターンベクトルである。
【００５０】
ｘ１〜ｘ１８は、原材料の使用本数ベクトルｘの各要素である。それぞれその下側に表示した長さの原材料を該当する割付パターンで使用するかどうかを、０または１の数値で表示する。ｘ１〜ｘ１８の値が０のときはその原材料を使用しない、１のときは使用することを示す。この原材料の使用本数ベクトルｘにより、列挙された割付パターンベクトルのうちのいずれを選択するかを表示する。
【００５１】
既に、特許文献１等に示す方法で、初期実行可能解を得ておく。例えば、Ｆｉｒｓｔ  Ｆｉｔ法でｘ１＝ｘ２＝ｘ３＝ｘ４＝ｘ５＝１、という解が得られる。他のＸ６〜ｘ１８の値は０という解とする。即ち、７本の製品を、ｘ１〜ｘ５の下に示した５本の原材料から、該当する割付パターンで切り出すと、求められる製品が得られる。原材料と製品の組合せをさらに改善し最適化を図る。
【００５２】
ｘ１〜ｘ１８の下側に示す７次の割付パターンベクトルを１８個並べたものが割付パターン行列Ａである。割付パターン行列Ａと使用本数ベクトルｘとの積は、選択された原材料から該当する割り付けパターンで切り出した製品数になる。図の左上にある必要数という表示の下の縦１列は、求められている製品の数を示す。これは、製品要求数量ベクトルｂに相当する。従って、上記の割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないという、Ａｘ≧ｂの制約条件が成立する。
【００５３】
（目的関数）
説明を簡略化するために、費用係数ベクトルｆの各要素を原材料長と一致させる。すなわち、長さの数値をそのまま円と読み替える。
図６（ａ）の原材料長の右側の１８個の数値が、費用係数ベクトルｆの要素である。従って、初期値として入力する実行可能解の目的関数Σ（ｆｉ・ｘｉ）の値は、ｘ１〜ｘ５の使用原材料長の総和で、２３３０００となる。以下の計算ではこれを改善する解を求めるのだから、目的関数の上限値を２３３０００に定める。
【００５４】
（原材料使用行列Ｃ）
図６の（ｂ）は、同図（ａ）の各割付パターンベクトル対応する原材料使用ベクトルｃjを示す。ｘ１〜ｘ１８の割付パターンベクトルが選択されたときに使用される原材料を示している。従って、原材料使用ベクトルｃjと原材料の使用本数ベクトルｘの積は、各原材料長の原材料の使用本数の内訳を示す。
【００５５】
（シンプレックス法演算処理）
下記の目的関数と制約条件をシンプレックス法演算モジュールに入力して、連続緩和問題を解く。Ｃｘ＝ｄという制約条件を除外し、０≦ｘｉ≦１という緩和条件で演算処理をする。
ｍｉｎ：Σ（ｆｉ×ｘｉ）  
ｓｕｂ．ｔｏ  Ａｘ≧ｂ
原材料の使用本数ベクトルｘの要素ｘ１〜ｘ１８は、０または１でなければならない。そこで、まず、ｘｉが０≦ｘｉ≦１の範囲をとり得るという条件でシンプレックス演算処理を実行する。そしてｘｉが０または１という解があるかどうか調べる。
【００５６】
図７と図８は、シンプレックス法演算処理により得られた解の説明図である。
図６（ａ）に示したとおりの原材料長群を目的関数とし、割付パターン行列Ａを制約条件として入力する。シンプレックス演算処理では、目的関数の値が、演算を進めるごとに小さくなるように、割付パターンベクトルの組合せが入れ替えられる。シンプレックス演算処理により、目的関数値＝２２１０００となる連続緩和問題の解が得られた。このシンプレックス演算処理には、市販の汎用的なプログラムモジュールを使用できる。
【００５７】
図７と図８の表では、解の値が０の割付パターンベクトルの表示を除外した。即ち、図７は、ｘ４＝ｘ１＝ｘ１６＝１、ｘ１２＝ｘ９＝ｘ３＝０．５で、他は０という解である。図８は、ｘ４＝ｘ１＝１、ｘ２＝ｘ９＝ｘ１０＝ｘ１６＝ｘ３＝０．５で、他は０という解である。例えば、図７の例では、原材料長が６００００，４５０００，４９０００のものを各１本、原材料長が４００００，４９０００，４５０００のものを各０．５本使用すると、目的関数値が２２１０００になるという結果が得られた。たしかに、目的関数値は初期値よりも小さい。しかしながら、ｘi∈｛０，１｝という制約条件を０≦ｘｉ≦１というように緩和したので、ｘｉ＝０．５という、実行不可能な解が得られた。
【００５８】
本発明では、上記の解が得られたときの目的関数値を、最適値の下限値に設定する。即ち、初期実行可能解を改善することを目的とするから、目的関数値の初期値を最大値２３３０００に設定し、最初のシンプレックス演算処理により得られた目的関数値２２１０００を最小値に設定する。この範囲に最適値があるとし、再度探索をする。ここで、原材料を任意の本数だけ組合せて、目的関数値が２２１０００以上、２３３０００より小さい値になる場合を列挙する。例えば、組合せを選択しながら集計する演算処理結果を昇順にソートすればよい。
【００５９】
全ての組合せを列挙する必要はない、原材料長の和、即ち、目的関数値が小さいものから順に列挙しながら、第２回目以降のシンプレックス演算処理を実行し、実行可能解、即ち、最適解が得られたら処理を終了すればよい。従って、例えば、Ｎｏ．１〜Ｎｏ．１０位までの組み合わせを列挙し、探索範囲を十分に狭めてシンプレックス演算処理を実行することにより、演算処理時間を短縮することができる。
【００６０】
例えば、Ｎｏ．１は、原材料長４９０００が３本、４５０００が１本、３００００が１本、という組合せである。即ち、２回目以降のシンプレックス演算処理では、原材料使用予定数量ベクトルｄを定め、Ｃｘ＝ｄという制約条件を追加する。そして、再び、シンプレックス演算処理を実行する。初回と同様に制約条件を０≦ｘｉ≦１と緩和して解を求める。全てのｘｉが０または１という解が得られたら、その結果をもとに、プレカットデータを生成する。それ以外の場合には、列挙された原材料の組合せのうちの、次の候補を選択して、原材料使用予定数量ベクトルｄを定め、図６（ｂ）に示した原材料使用行列を書き換える。
【００６１】
図９はシンプレックス法演算処理により得られた解の説明図である。
Ｎｏ．１の例では、使用する原材料長の最大値が４９０００だから、製品長５３０５０の製品は明らかに得られない。Ｎｏ．２では、原材料長４９０００が２本、４５０００が１本、４００００が２本、という組合せにする。Ｎｏ．３では、原材料長４９０００が１本、４５０００が１本、４００００が１本、３００００が３本という組合せにする。Ｎｏ．４では、原材料長６００００〜３００００の全てが１本という組合せにする。上記の演算処理を繰り返すことにより、原材料の本数の組合せのＮｏ．４で、シンプレックス表の基底変数が全て１の整数解が得られた。原材料長が、６００００．４００００．４５０００．３００００．４９０００のものを各一本選択して、それぞれ切り出す製品を割り付ける。これにより、原材料長の総和が２２４０００になる。初期実行可能解の原材料長の総和は２３３０００であったから、９０００だけ、原材料を節約できる割付パターンを見つけることができた。この列挙した組み合わせを示すデータを、部材割付データとして出力し、端末装置に送信する。
【００６２】
図１０は、実施例３における演算処理の効果を説明する部材加工装置のブロック図である。
以上の処理により、部材割付データ５３が得られた。これは、プレカット工場でプレカット装置１７に供給される。原材料は図１０に示した順に選択されて、対応する割付パターンで切り分けられ、製品が得られる。この実施例では、初期実行可能解の場合の歩留まりが０．９０３であったものが、改善後に０．９３９になった。大量の原材料に大量の製品を割り付けて切り出すプレカット工場では、このように、約１％の歩留まり改善ができただけで多額のコストダウンが可能になる。また、廃棄物量を１％減少させることができれば、廃棄物処理のための設備や費用も節約することができる。上記の例では、原材料の種類や要求される製品の種類や量を単純化したが、多種多様の原材料と製品とを取り扱えばさらに従来法では到達できなかったレベルまで大幅な歩留まりの改善を見込むことができる。
【００６３】
なお、上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組合せて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。  
【図面の簡単な説明】
【００６４】
【図１】実施例１の部材割付システム１０のブロック図である。
【図２】部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
【図３】演算処理のパラメータを説明するための説明図である。
【図４】初回のシンプレックス演算処理動作フローチャートである。
【図５】１回目のシンプレックス演算終了後の演算処理のフローチャートである。
【図６】具体的な計算例の説明図で、（ａ）は割付パターンベクトルの説明図、（ｂ）は原材料使用ベクトルｃjの説明図である。
【図７】シンプレックス法演算処理により得られた解の説明図である。
【図８】シンプレックス法演算処理により得られた別の解の説明図である。
【図９】シンプレックス法演算処理により得られた解の説明図である。
【図１０】実施例３における演算処理の効果を説明する部材加工装置のブロック図である。
【符号の説明】
【００６５】
１０  部材割付システム
１２  コンピュータ
１４  ネットワーク
１６  端末装置
２０  演算処理装置
２１  製品長設定手段
２２  原材料長設定手段
２３  初期設定手段
２４  割付パターンベクトル生成手段
２５  割付パターン行列生成手段
２６  制約条件生成手段
２７  費用計数係数ベクトル生成手段
２８  目的関数生成手段
２９  シンプレックス演算処理手段
３０  探索制御手段
４０  記憶装置
４１  製品長ベクトルLp
４２  製品要求数量ベクトルｂ
４３  原材料長ベクトルLm
４４  初期実行可能解
４５  原材料使用予定数量ベクトルｄ
４６  割付パターン行列
４６ａ  割付パターンベクトル
４７  原材料使用行列Ｃ
４８  第１制約条件式
４９  第２制約条件式
５０  第３制約条件式
５１  目的関数
５２  組合せリスト
５３  部材割付データ
【図１】
0004909869.tif 000002
【図２】
0004909869.tif 000003
【図３】
0004909869.tif 000004
【図４】
0004909869.tif 000005
【図５】
0004909869.tif 000006
【図６】
0004909869.tif 000007
【図７】
0004909869.tif 000008
【図８】
0004909869.tif 000009
【図９】
0004909869.tif 000010
【図１０】
0004909869.tif 000011