(57)【特許請求の範囲】
【請求項１】
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とするｍ次の製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件、wpi+wpj≦wml またはhpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、ｍ次の初期割付パターンベクトルと初期割付パターン行列を生成して、記憶装置に記憶する初期設定手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データが同一な場合に、前記同一な製品をまとめて１つの要素とし、前記同一な製品の横長を要素とするｍ次未満の製品横長ベクトルwp１と、前記同一な製品の縦長を要素とするｍ次未満の製品縦長ベクトルhp１と、前記同一な製品の面積を要素とするｍ次未満の製品面積ベクトルsp１と、ｍ次未満の製品要求数量ベクトルｂ１を生成する製品再設定手段と、
初期割付パターンベクトルを前記同一な製品に対応するｍ次未満の割付パターンベクトルに変換し、初期割付パターン行列を前記m次未満の割付パターンベクトルに対応する割付パターン行列に変換して記憶装置に記憶する初期設定変換手段と、
求められている前記ｍ次未満の製品横長ベクトルwp１に含まれる製品横長データと、前記ｍ次未満の製品縦長ベクトルｈp１に含まれる製品縦長データとを、用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次未満の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれ前記ｍ次未満の製品横長ベクトルwp１と前記ｍ次未満の製品縦長ベクトルhp１に含まれる製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択された割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂ１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算処理手段と、
最適解を探索して出力する演算処理を制御する探索制御手段とを備え、
この探索制御手段は、
前記シンプレックス演算処理により、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を、前記制約条件生成手段に依頼し、
前記第１制約条件式と前記第２制約条件式の制約条件下で、シンプレックス演算処理手段に演算処理を依頼し、シンプレックス演算処理により得られた、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記シンプレックス演算処理により、非整数解を伴う実行可能解が得られて、さらにその後のシンプレックス演算処理で、非整数解を伴う実行可能解が得られたとき、ｘｉのうち、整数であるｘｉの個数を求める評価式Σ（ｘｉが整数である個数）を定義して、前記評価式の値を求めて、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、非整数解が整数解に近づき、評価式の値が減少していく場合は非整数解が整数解に近づかないと判定する判定手段が、前記シンプレックス演算処理を繰り返しても非整数解が整数解に近づかないと判定したときには、前記第２制約条件式を変更して前記シンプレックス演算処理を繰り返すように制御して、
列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算処理手段に演算処理を依頼するという動作を繰り返すように制御することを特徴とする部材割付システム。
【請求項２】
前記切り出されるべき製品に正方形及び長方形以外の多角形が含まれるとき、該当する多角形については、その多角形を含む最小の、前記横長データと縦長データを有する長方形（みなし長方形と呼ぶ）を、前記ｍ枚の製品に含めるように条件を設定するみなし長方形設定手段とを備え、
前記割付パターンベクトル生成手段は、
前記原材料から製品を切り出した残りの部分も原材料に含めるとともに、前記みなし長方形から前記多角形を切り出した残りの部分も原材料に含めて、前記原材料に割り付ける製品の組合せを決定することを特徴とする請求項１に記載の部材割付システム。
【請求項３】
前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする請求項１乃至２に記載の部材割付システム。
【請求項４】
前記割付パターンベクトル生成手段は、
前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶し、
この判定結果を使用して、製品を割り付けた原材料から、横もしくは縦方向のギロチンカット方向を選択した後、切断可能な全ての切断線を検出する処理と、この方向の切断線が無くなったら、切断後の原材料をひとつずつ選択して、別の方向の切断線を検出する処理とを順に実行するような、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成するカッティングデータ生成手段を備えたことを特徴とする請求項１乃至３に記載の部材割付システム。
【請求項５】
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の長さデータの入力を受け付けて、製品の長さを要素とするｍ次の製品長ベクトルwpと、製品要求数量を要素とするｍ次の製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の原材料データの入力を受け付けて、原材料の長さを要素とするｋ次の原材料長ベクトルwmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の長さは原材料長ベクトルwmの要素のうちのいずれかの原材料の長さ以下であるとする１次元モデル条件（wp，ａｊ）（内積）≦wmを生成して、記憶装置に記憶させる１次元モデル条件生成手段と、
予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、ｍ次の初期割付パターンベクトルと初期割付パターン行列を生成して、記憶装置に記憶する初期設定手段と、
求められている前記ｍ本の製品の製品長データが同一な場合に、前記同一な製品をまとめて１つの要素とし、前記同一な製品の長さを要素とするｍ次未満の製品長ベクトルwp１と、ｍ次未満の製品要求数量ベクトルｂ１を生成する製品再設定手段と、
初期割付パターンベクトルを前記同一な製品に対応するｍ次未満の割付パターンベクトルに変換し、初期割付パターン行列を前記m次未満の割付パターンベクトルに対応する割付パターン行列に変換して記憶装置に記憶する初期設定変換手段と、
求められている前記ｍ次未満の製品長ベクトルwp１に含まれる製品長データを、用意された前記ｋ種類の原材料の原材料長データと比較して、前記１次元モデル条件を満たす、１本または複数本の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次未満の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれ前記ｍ次未満の製品長ベクトルwp１に含まれる製品のうちのいずれかの製品を割り付けたとき、選択したｎ本の原材料の使用本数を表すために、要素がｘｉのｎ次の使用本数ベクトルｘを定義し、前記ｎ本の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択された割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂ１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算処理手段と、
最適解を探索して出力する演算処理を制御する探索制御手段とを備え、
この探索制御手段は、
前記シンプレックス演算処理により、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を、前記制約条件生成手段に依頼し、
前記第１制約条件式と前記第２制約条件式の制約条件下で、シンプレックス演算処理手段に演算処理を依頼し、シンプレックス演算処理により得られた、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として割付データを出力し、それ以外の場合には、前記シンプレックス演算処理により、非整数解を伴う実行可能解が得られて、さらにその後のシンプレックス演算処理で、非整数解を伴う実行可能解が得られたとき、ｘｉのうち、整数であるｘｉの個数を求める評価式Σ（ｘｉが整数である個数）を定義して、前記評価式の値を求めて、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、非整数解が整数解に近づき、評価式の値が減少していく場合は非整数解が整数解に近づかないと判定する判定手段が、前記シンプレックス演算処理を繰り返しても非整数解が整数解に近づかないと判定したときには、前記第２制約条件式を変更して前記シンプレックス演算処理を繰り返すように制御して、
列挙された前記原材料の使用本数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算処理手段に演算処理を依頼するという動作を繰り返すように制御することを特徴とする部材割付システム。
【請求項６】
前記予め定めた割付け方法は、製品を長いものから順に配列し、原材料を長いものから順に配列して、ファーストフィット法で割付けを実行する処理であることを特徴とする請求項５に記載の部材割付システム。
【請求項７】
コンピュータを、請求項１乃至６に記載の各手段として機能させる部材割付プログラム。
【請求項８】
請求項７に記載の部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項９】
請求項１乃至４に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、原材料から様々な形状の製品を切り出す場合に、その板取りを最適化するための演算処理を高速化する、部材割付システムと部材割付プログラムと記録媒体と部材加工装置に関する。
【背景技術】
【０００２】
住宅構造材のプレカットには、断面形状や樹種，等級、レイヤといった仕様ごとに何種類かの原材料が用意される。そこから求められる寸法の部材(製品)を切り出す。製品の仕様と、製品の寸法と、切り出される原材料の組合せにより、原材料から切り落とされて無駄になる部分の量が異なる。柱や一定の幅の板といった線状材料については、シンプレックス演算処理を利用し、山登り法、ランダムリスタート法、焼き鈍し法等により、歩留あるいは費用を最小にするための最適値を探索する技術が開発された（特許文献１参照）。続いて、種々の縦横寸法を持つ製品を原材料から切り出す場合に、予め既存の方法で求めた初期実行可能解を起点にして、所定の演算処理を実行して歩留向上を図る技術が開発された（特許文献２参照）。さらに、原材料を縦横に切断するための、製品と原材料との最適な組み合わせを求めるとともに、具体的なプレカット作業のための指示書を作成する技術も開発された（特許文献３参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−９８９２４号
【特許文献２】特許３０７９１８９号公報
【特許文献３】特許５８３８０４７号公報
【特許文献４】特許３４４１４２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
原材料に各製品を縦長に割り付けた場合と横長に割付けた場合とでは、歩留が異なることがある。さらに、製品を切り出した残りの原材料に新たに別の製品を割り付けることもできる。これらを含めた割付けのための最適化計算は、製品数が多いと場合の数がきわめて多くなり、演算処理に時間がかかるという課題があった。
【０００５】
本発明は、以上の課題を解決するためになされたもので、原材料から様々な形状の製品を切り出すための割付計算のための、演算処理時間の短縮も可能にする、部材割付システムと部材割付プログラムと記録媒体と部材加工装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
【０００７】
＜構成１＞
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とするｍ次の製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件、wpi+wpj≦wml またはhpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、ｍ次の初期割付パターンベクトルと初期割付パターン行列を生成して、記憶装置に記憶する初期設定手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データが同一な場合に、前記同一な製品をまとめて１つの要素とし、前記同一な製品の横長を要素とするｍ次未満の製品横長ベクトルwp１と、前記同一な製品の縦長を要素とするｍ次未満の製品縦長ベクトルhp１と、前記同一な製品の面積を要素とするｍ次未満の製品面積ベクトルsp１と、ｍ次未満の製品要求数量ベクトルｂ１を生成する製品再設定手段と、
初期割付パターンベクトルを前記同一な製品に対応するｍ次未満の割付パターンベクトルに変換し、初期割付パターン行列を前記m次未満の割付パターンベクトルに対応する割付パターン行列に変換して記憶装置に記憶する初期設定変換手段と、
求められている前記ｍ次未満の製品横長ベクトルwp１に含まれる製品横長データと、前記ｍ次未満の製品縦長ベクトルｈp１に含まれる製品縦長データとを、用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次未満の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれ前記ｍ次未満の製品横長ベクトルwp１と前記ｍ次未満の製品縦長ベクトルhp１に含まれる製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択された割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂ１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算処理手段と、
最適解を探索して出力する演算処理を制御する探索制御手段とを備え、
この探索制御手段は、
前記シンプレックス演算処理により、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を、前記制約条件生成手段に依頼し、
前記第１制約条件式と前記第２制約条件式の制約条件下で、シンプレックス演算処理手段に演算処理を依頼し、シンプレックス演算処理により得られた、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記シンプレックス演算処理により、非整数解を伴う実行可能解が得られて、さらにその後のシンプレックス演算処理で、非整数解を伴う実行可能解が得られたとき、ｘｉのうち、整数であるｘｉの個数を求める評価式Σ（ｘｉが整数である個数）を定義して、前記評価式の値を求めて、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、非整数解が整数解に近づき、評価式の値が減少していく場合は非整数解が整数解に近づかないと判定する判定手段が、前記シンプレックス演算処理を繰り返しても非整数解が整数解に近づかないと判定したときには、前記第２制約条件式を変更して前記シンプレックス演算処理を繰り返すように制御して、
列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算処理手段に演算処理を依頼するという動作を繰り返すように制御することを特徴とする部材割付システム。
【０００８】
＜構成２＞
前記切り出されるべき製品に正方形及び長方形以外の多角形が含まれるとき、該当する多角形については、その多角形を含む最小の、前記横長データと縦長データを有する長方形（みなし長方形と呼ぶ）を、前記ｍ枚の製品に含めるように条件を設定するみなし長方形設定手段とを備え、
前記割付パターンベクトル生成手段は、
前記原材料から製品を切り出した残りの部分も原材料に含めるとともに、前記みなし長方形から前記多角形を切り出した残りの部分も原材料に含めて、前記原材料に割り付ける製品の組合せを決定することを特徴とする構成１に記載の部材割付システム。
【０００９】
＜構成３＞
前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする構成１乃至２に記載の部材割付システム。
【００１０】
＜構成４＞
前記割付パターンベクトル生成手段は、
前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶し、
この判定結果を使用して、製品を割り付けた原材料から、横もしくは縦方向のギロチンカット方向を選択した後、切断可能な全ての切断線を検出する処理と、この方向の切断線が無くなったら、切断後の原材料をひとつずつ選択して、別の方向の切断線を検出する処理とを順に実行するような、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成するカッティングデータ生成手段を備えたことを特徴とする構成１乃至３に記載の部材割付システム。
【００１１】
＜構成５＞
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の長さデータの入力を受け付けて、製品の長さを要素とするｍ次の製品長ベクトルwpと、製品要求数量を要素とするｍ次の製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の原材料データの入力を受け付けて、原材料の長さを要素とするｋ次の原材料長ベクトルwmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の長さは原材料長ベクトルwmの要素のうちのいずれかの原材料の長さ以下であるとする１次元モデル条件（wp，ａｊ）（内積）≦wmを生成して、記憶装置に記憶させる１次元モデル条件生成手段と、
予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、ｍ次の初期割付パターンベクトルと初期割付パターン行列を生成して、記憶装置に記憶する初期設定手段と、
求められている前記ｍ本の製品の製品長データが同一な場合に、前記同一な製品をまとめて１つの要素とし、前記同一な製品の長さを要素とするｍ次未満の製品長ベクトルwp１と、ｍ次未満の製品要求数量ベクトルｂ１を生成する製品再設定手段と、
初期割付パターンベクトルを前記同一な製品に対応するｍ次未満の割付パターンベクトルに変換し、初期割付パターン行列を前記m次未満の割付パターンベクトルに対応する割付パターン行列に変換して記憶装置に記憶する初期設定変換手段と、
求められている前記ｍ次未満の製品長ベクトルwp１に含まれる製品長データを、用意された前記ｋ種類の原材料の原材料長データと比較して、前記１次元モデル条件を満たす、１本または複数本の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次未満の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれ前記ｍ次未満の製品長ベクトルwp１に含まれる製品のうちのいずれかの製品を割り付けたとき、選択したｎ本の原材料の使用本数を表すために、要素がｘｉのｎ次の使用本数ベクトルｘを定義し、前記ｎ本の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択された割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂ１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算処理手段と、
最適解を探索して出力する演算処理を制御する探索制御手段とを備え、
この探索制御手段は、
前記シンプレックス演算処理により、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を、前記制約条件生成手段に依頼し、
前記第１制約条件式と前記第２制約条件式の制約条件下で、シンプレックス演算処理手段に演算処理を依頼し、シンプレックス演算処理により得られた、ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解として割付データを出力し、それ以外の場合には、前記シンプレックス演算処理により、非整数解を伴う実行可能解が得られて、さらにその後のシンプレックス演算処理で、非整数解を伴う実行可能解が得られたとき、ｘｉのうち、整数であるｘｉの個数を求める評価式Σ（ｘｉが整数である個数）を定義して、前記評価式の値を求めて、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、非整数解が整数解に近づき、評価式の値が減少していく場合は非整数解が整数解に近づかないと判定する判定手段が、前記シンプレックス演算処理を繰り返しても非整数解が整数解に近づかないと判定したときには、前記第２制約条件式を変更して前記シンプレックス演算処理を繰り返すように制御して、
列挙された前記原材料の使用本数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算処理手段に演算処理を依頼するという動作を繰り返すように制御することを特徴とする部材割付システム。
【００１２】
＜構成６＞
前記予め定めた割付け方法は、製品を長いものから順に配列し、原材料を長いものから順に配列して、ファーストフィット法で割付けを実行する処理であることを特徴とする構成５に記載の部材割付システム。
【００１３】
＜構成７＞
コンピュータを、構成１乃至６に記載の各手段として機能させる部材割付プログラム。
【００１４】
＜構成８＞
構成７に記載の部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【００１５】
＜構成９＞
構成１乃至４に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【発明の効果】
【００１６】
原材料から様々な形状の製品を切り出すとき、同一寸法の原材料や製品を多用する場合に、要素がｘｉのｎ次の使用枚数ベクトルｘを定義して、ｘｉが０以上とする計算と所定の評価式により、演算時間の大幅な短縮が可能になる。
【図面の簡単な説明】
【００１７】
【図１】実施例１の部材割付システム１０のブロック図である。
【図２】部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
【図３】演算処理のパラメータを説明するための説明図である。
【図４】初回のシンプレックス演算処理動作フローチャートである。
【図５】１回目のシンプレックス演算終了後の演算処理のフローチャートである。
【図６】原材料から製品を切り出す手順と新たな原材料の説明図である。
【図７】部材切断手段の主要部と原材料の横断面図である。
【図８】演算処理条件データの例説明図である。
【図９】ファーストフィットで求められた初期実行可能解の例説明図である。
【図１０】演算処理の結果得られた最適割付パターンの例説明図である。
【図１１】初期実行可能解の割付パターン例平面図である。
【図１２】最適解の割付パターン例平面図である。
【図１３】演算処理時間を短縮する計算によるデータ例説明図である。
【図１４】演算処理時間を短縮する計算によるデータ例説明図である。
【図１５】演算処理時間を短縮する計算によるデータ例説明図である。
【図１６】演算処理時間を短縮する計算によるデータ例説明図である。
【図１７】シンプレックス演算処理実行のための前処理例フローチャートである。
【図１８】シンプレックス演算処理実行例フローチャートである。
【発明を実施するための形態】
【００１８】
本発明では、特許文献３に記載されたように、既存の任意の方法で得られた実用性のある解を基礎にして、それをシンプレックス法で評価し、さらに改善した解を求める。シンプレックス法は、線形計画問題の最適解を探索する方法として知られている。しかし、求められた原材料や製品の縦横寸法が数十種類にも及ぶと、組合せの数は数十万組を越えることがある。ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付ける、といった条件に基づいてそのまま演算処理のためのパラメータを作ると、最適値探索のためのシンプレックス演算処理に時間がかかりすぎることがある。そこで、シンプレックス法による演算処理のための制約条件を新たに付加して、比較対象範囲の絞り込みをしながら、効率よく計算をする。そして、シンプレックス法によるピボット演算処理の過程で実行可能解が得られたときに、所定の評価式を使用してその後の見通しをたてる。その結果に応じて探索条件を変更し、無駄な演算処理を回避する。以下、本発明の実施の形態を実施例ごとに詳細に説明する。
【実施例１】
【００１９】
図１は実施例１の部材割付システム１０のブロック図である。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、原材料から製品をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献４に記載されたとおりのものを使用することができる。
【００２０】
コンピュータ１２には、演算処理装置２０と記憶装置４０とが設けられている。演算処理装置２０には、図のように、製品設定手段２１、原材料設定手段２２、初期設定手段２３、割付パターンベクトル生成手段２４、割付パターン行列生成手段２５、制約条件生成手段２６、費用係数ベクトル生成手段２７、目的関数生成手段２８、シンプレックス演算処理手段２９、探索制御手段３０、判定手段３１等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。この実施例では、さらに、製品再設定手段３６と初期設定変換手段３７と原材料使用行列生成手段とカッティングデータ生成手段３４と、みなし長方形設定手段３５を設けている。
【００２１】
記憶装置４０には、図のように、製品横長ベクトルwp、製品縦長ベクトルhp、製品面積ベクトルsp、原材料横長ベクトルwm、原材料縦長ベクトルhm、原材料面積ベクトルsm、製品要求数量ベクトルｂ４２、初期実行可能解４４、原材料使用予定数量ベクトルｄ４５、割付パターン行列４６、原材料使用行列Ｃ４７、第１制約条件式４８、第２制約条件式４９、目的関数５１、組合せリスト５２、部材割付データ５３、及び評価式５４等のデータが記憶されている。これらのデータは、予め外部から入力されるか、あるいは、上記のコンピュータプログラムの動作により生成されて、記憶装置４０に記憶されるものである。続いて、これらのコンピュータプログラムと記憶装置４０に記憶されるデータの具体的な説明をする。
【００２２】
図２は、部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
部材割付システム１０の具体的な機能を説明する前に、部材割付システム１０のハードウエアを説明する。図のように、コンピュータ１２の本体ケース３中に収められた内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５と、ネットワークインタフェース１１６とが接続されている。入出力インタフェース１１５には、ディスプレイ２とキーボード４とマウス５とが接続されている。ネットワークインタフェース１１６には、ネットワーク１４を介して、端末装置１６が接続されている。以上のハードウェアは一般的によく知られたパーソナルコンピュータに備えられているものと変わらない。端末装置１６は、プレカット装置１７の部材選択供給装置１２０に、部材割付データを５３（図１）を供給する。これにより、指定された原材料が部材切断装置１２１に供給され、指定された割付パターンで切断される。切断された製品は製品搬送装置１２２により搬送され排出される。
【００２３】
図１に示した記憶装置４０は、図２のＲＯＭ１１２やＲＡＭ１１３やＨＤＤ１１４により構成される。図１に示した演算処理装置２０は、図２のＣＰＵ１１１、ＲＯＭ１１２、ＲＡＭ１１３等により構成される。各種のデータは主としてＨＤＤ１１４に記憶されて保存される。ＣＰＵ１１１が実行するコンピュータプログラムは、ＲＯＭ１１２に記憶され、あるいはＲＡＭ１１３に適時ロードされる。端末装置１６も同様の構成で構わない。ネットワーク１４はインターネットでもイントラネットでも構わない。
【００２４】
図３は、演算処理のパラメータを説明するための説明図である。
この図を参照しながら、演算処理に使用するパラメータの定義と、上記の各コンピュータプログラムの機能を説明する。
［製品長ベクトル］
生産されるべき製品の数量をｍ枚とする。
製品長を例えば、単位ｍ（メートル）で表現する。
ｍ次の製品横長ベクトルwp（行ベクトル）を下記のように定義する。
wp＝（wp1,wp2,…,wpm）
ｍ次の製品縦長ベクトルhp（行ベクトル）を下記のように定義する。
hp＝（hp1,hp2,…,hpm） 
ｍ次の製品面積ベクトルsp（行ベクトル）を下記のように定義する。
sp＝（sp1,sp2,…,spm）
なお、spi＝wpi×hpi（i=1,2,…,m）である。
【００２５】
［製品要求数量ベクトルｂ］
数量ｍの製品の生産が要求されているとき、製品要求数量ベクトルｂを、下記のように定義する。なお、特許文献３では、製品形状がすべて異なることを前提として、全てｂi＝１とした。本発明では、同一形状の製品がある場合を取り扱うために、ｂiを任意の正の整数とした上で、その後特殊な計算をする。本発明との比較のために、特許文献３の演算処理を先に説明して、その後、本発明の実施例の説明を行う。
ｂ＝（ｂ1,ｂ2,…,ｂm）T
（上付きＴは転置を表す。即ち、ｂは列ベクトルである。以下も同様）
図３の例では数量ｍ＝７で、ｂ＝（１，１，１，１，１，１，１）Tである。
製品設定手段２１は、求められているｍ枚の製品について、横長データと縦長データの入力を受け付けて、製品横長ベクトルwpと製品縦長ベクトルhpと製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂ４２を生成して、記憶装置４０に記憶させる。
【００２６】
［原材料データ］
原材料はｋ種類ある。原材料の縦横寸法を、例えば、単位ｍ（メートル）で表現する。
ｋ次の原材料横長ベクトルwm（行ベクトル）を下記のように定義する。
wm＝（wm1,wm2,…,wmk）
ｋ次の原材料縦長ベクトルhm（行ベクトル）を下記のように定義する。
hm＝（hm1,hm2,…,hmk）
ｋ次の原材料面積ベクトルsm（行ベクトル）を下記のように定義する。
sm＝（sm1,sm2,…,smk）
なお、smi＝wmi×hmi（i=1,2,…,k）である。
ｋ次の原材料番号ベクトルnm（行ベクトル）を下記のように定義する。
nm＝（1,2,…,k） このi番目の要素「i」は横長がwmi、縦長がhmi、面積がsmiの原材料番号を表す。
原材料設定手段２２は、用意されたｋ種類の原材料について、横長データと縦長データの入力を受け付けて、ｋ次の原材料横長ベクトルwmとｋ次の原材料縦長ベクトルhmとｋ次の原材料面積ベクトルsmとｋ次の原材料番号ベクトルnmを生成し、記憶装置４０に記憶させる。
【００２７】
［原材料使用予定数量ベクトルｄ］
原材料使用予定数量ベクトルｄ４５（列ベクトル）は、実行可能なある解に対して、ｋ種類の長さの材料がそれぞれ何枚ずつ使用されるかを示す。これを下記のように定義する。
ｄ＝（ｄ1,ｄ2,…,ｄk）T
例えば、図３はｋ＝３で、原材料を、それぞれ１枚、２枚、１枚と、合計４枚使用する場合には、
ｄ＝（ｄ1,ｄ2,ｄ3）T＝（１，２，１）Tである。
原材料使用予定数量ベクトルｄ４５は、後で説明する第２制約条件式で使用される。
【００２８】
［使用枚数ベクトルｘ］
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付ける。このとき、選択したｎ枚の原材料の使用枚数を表すｎ次の使用枚数ベクトルｘを、下記のように定義する。なお、ｋ種類の原材料からｎ枚の原材料を選択するとき、同一の原材料を２度以上重複して選択して構わない。
ｘ＝（ｘ1,ｘ2,…,ｘn）T
なお、特許文献３では、製品形状がすべて異なることを前提として、製品要求数量ベクトルｂの要素を全てｂｉ＝１としたので、ｍ次の使用枚数ベクトルｘの各要素ｘｉは０≦ｘｉ≦１となり、部材割付の結果として意味を持つのは、ｘｉが０または１の場合である。一方、本発明では、後で説明するように、ｂｉを任意の整数としたことから、０≦ｘｉ≦Ｎ（Ｎは任意の整数）として計算をする。また、この条件を緩和した場合には、０≦ｘｉとなるから、本発明では計算を実行する上で制約条件式は不要になる。
【００２９】
図３（Ｃ）の記号において、wm1、hm1、sm1に相当する原材料をwm1で代表して表記する。
上記の原材料使用予定数量ベクトルが、ｄ＝（ｄ1,ｄ2,ｄ3）のときには、例えば、原材料を(wm1,wm2,wm2,wm3）と列挙する。これら４枚の原材料に対して、それぞれ求められている製品を割り付ける。このとき、最初のwm1に対してｘ1、２番目のwm2に対してｘ2、３番目のwm2に対してｘ3、４番目のwm3に対してｘ4を設定する。図の例では、ｘ1＝ｘ2＝ｘ3＝ｘ4＝１である。選択される原材料と選択されない原材料とを列挙したとき、選択される原材料に設定されるｘｉの値は１である。選択されない原材料に設定されるｘｉの値は０である。使用枚数ベクトルｘは制約条件式で使用される。
【００３０】
［割付パターンベクトルａj］
いずれか１枚の原材料から、数量ｍの製品のうちのいずれかを切り出すように割り付けたデータを、ｍ次の割付パターンベクトルａj（列ベクトル）で表す。これを下記のように定義する。
ａj＝（a1j,a2j,…,amj）T   （ｊ＝1,2,…,n）
即ち、ｍ次のベクトルがｎ個ある。
例えば、、下記に、図３（ｃ）の例における割付パターンベクトルを示す。なお、図３（ｃ）の図は下式とは整合していない。
wm1にwp2とwp6をそれぞれ１枚割付けたとすると、
（０，１，０，０，０，１，０）T
wm2にwp1を１枚割付けたとすると
（１，０，０，０，０，０，０）T
wm2にwp3とwp5をそれぞれ１枚割付けたとすると、
（０，０，１，０，１，０，０）T
wm3にwp4とwp7をそれぞれ１枚割付けたとすると、
（０，０，０，１，０，０，１）T
【００３１】
上記の割付パターンベクトルａjは、 （１式）（２式）を満足するように生成される。
（sp，aj）≦Ｓ  （ｊ＝1,2,…,n）・・（１式）
Ｓは、（１式）と（２式）を満たすsmi  の最小値である。但し（i＝1,2,…,k）
即ち、（１式）は、割付け製品の面積は原材料の面積以下であるという条件式である。
wpi+wpj =〈wml  or  hpi+hpj=〈hml ・・・（２式）
但し（i＝1,2,…,m）（ｊ＝1,2,…,m）（l＝1,2,…,k）
即ち、同一原材料に隣接して割付けられた製品は互いに重なり合わないという条件式である。
なお、（１式）の左辺の（sp，aj）は、選択された原材料に割り付けられた、１枚の製品もしくは複数枚の製品面積の総和である。割付パターンベクトルａjを生成するときには、割り付けることができる最小面積の原材料が選択される。実加工では、矩を出すためのハナ切り長、刃物厚が考慮されるが、ここでは無視する。
【００３２】
例えば、製品wp3とwp5をそれぞれ１枚割付けるとすると、原材料wm1またはwm2のいずれにも割付ができるものとする。ここで、wm1 の費用係数がwm2の費用係数より大きければ、割付対象をwm2というように原材料を選択する。こうして、経済的に割り付けできる関係を見つける。
図の例は、実行可能解に相当する一組の割付パターンベクトルを列挙した。シンプレックス法で最適解を求めるための準備として、必要に応じてシンプレックス演算処理の結果に基づき、割付パターンベクトルを列挙する。
【００３３】
割付パターンベクトル生成手段２４は、求められているｍ枚の製品の製品横長データと製品縦長データと製品面積データと、用意されたｋ種類の原材料の原材料横長データと原材料縦長データと原材料面積データとを比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトル４６ａを生成し、記憶装置４０に記憶させる。
【００３４】
［割付パターン行列］
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けるときには、上記の割付パターンベクトルをｎ個並べる。ａjをｎ個並べたｍ×ｎ次の割付パターン行列を下記に定義する。これを図３（ｄ）に示す。
Ａ＝（ａij）  （ｉ＝1,2,…,ｍ、ｊ＝1,2,…,ｎ）
割付パターン行列生成手段２５は、割付パターンベクトル生成手段２４の生成した割付パターンベクトル４６ａをｎ個並べたｍ×ｎ次の割付パターン行列を生成し、記憶装置４０に記憶させる。
【００３５】
［第１制約条件］
割付パターン行列Ａと使用枚数ベクトルｘとの積は、選択された各原材料から、それぞれ該当する割付パターンで切り出した製品数になる。従って、割付パターン行列Ａから選択された原材料から該当する割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならない。求められている各製品の数量は、製品要求数量ベクトルｂに相当する。従って、少なくとも、下式を満足しないと、必要な数の製品が得られない。
Σａij・ｘj≧ｂi  （j=1,2,・・・,n）（i=1,2,・・・,m）
【００３６】
この制約条件式は、Ａｘ≧ｂと表す。図３の例では、生産された製品数も必要な製品数も７であって、等号が成立する。制約条件生成手段２６は、割付パターン行列Ａから選択された原材料から該当する割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上であるとする第１制約条件式を生成して、記憶装置４０に記憶させる。
【００３７】
［原材料使用行列Ｃ］
ｋ種類の原材料のうちのどの原材料を使用するかを示す、ｋ次の原材料使用ベクトルｃjを次のように定義する。これを図３（ｅ）に示す。
ｃj＝（ｃ1j,ｃ2j,…,ｃkj）T  （ｊ＝1,2,…,n）
但し、ｃ1j,ｃ2j,…,ｃkjはいずれも、０または１である。
上記のように、ｋ種類の原材料から選択したｎ枚の原材料を表すのに、原材料使用行列Ｃを用いる。これをｃjをｎ個並べたｋ×ｎ次の行列で定義する。
Ｃ＝（ｃij）（ｉ＝1,2,…,ｋ、ｊ＝1,2,…,n）
【００３８】
既に説明した図３の例でｃijは、下記のとおりである。
ｃ1＝（１、０、０）T
ｃ2＝（０，１，０）T
ｃ3＝（０，１，０）T
ｃ4＝（０，０，１）T
原材料使用行列生成手段３８は、各割付パターンで、ｋ種類の原材料のうちのどの原材料を使用するかを示す原材料使用ベクトルｃjを列挙した、ｋ×ｎ次の原材料使用行列Ｃを生成して、記憶装置に記憶させる。
【００３９】
［第２制約条件］
なお、ｃjはｋ種類の原材料のうちの一つを指定するベクトルだから、下式を満足する。
Σｃij＝１（ｉ＝1,2,…,ｋ）（ｊ＝1,2,…,n）
ｋ個の数字のうち１個だけが１で他は全て０ということである。また、原材料は、割付けできる最小のものが選択される。
【００４０】
また、既に定義したとおり、ｎ枚の原材料の使用枚数ベクトルｘは、ｘ＝（ｘ1,ｘ2,…,ｘn）であった。また、原材料使用予定数量ベクトルｄは、原材料ごとの使用数を示すものであった。従って、下式の条件が満足されなければならない。
Σｃij・ｘj＝ｄi（ｉ＝1,2,…,ｋ）（ｊ＝1,2,…,n）
この第２制約条件式は、Ｃｘ＝ｄと表す。
これは、どの原材料を何枚選択して実際の割付に使用するかを定める。制約条件生成手段２６は、割付パターン行列生成手段２５が生成した原材料使用行列Ｃと原材料の使用枚数ベクトルｘの積が、原材料使用予定数量ベクトルｄと等しいとする第２制約条件式を生成して、記憶装置に記憶させる。
【００４１】
［第３制約条件］
上記の使用枚数ベクトルｘの各要素ｘiは、特許文献３の例では０または１である。列挙された多数の割付パターンベクトルの中のいずれを選択するかどうかを決める意味をもつからである。従って、下式のような制約条件式が成立する。
ｘi∈｛０，１｝
特許文献３の例では、この制約条件を緩和する。即ち、０≦ｘi≦１という制約条件式を設定する。制約条件生成手段２６は、使用枚数ベクトルｘの各要素ｘiが０≦ｘi≦１である旨を示す第３制約条件式を生成して、記憶装置に記憶させる。
【００４２】
（２次元モデル条件）
２次元モデルを対象にすることから、新たな条件を設定する。割付け製品の面積は原材料の面積Ｓ以下である。これを第１評価条件（sp，aj）（内積）≦Sとする。隣接する製品は重ならない。これを第２評価条件wpi+wpj≦wmi または hpi+hpj≦hmiとする。割付パターンベクトルａｊが予め定めた割付け方法で割付け可能でなければならない。これを第３評価条件とする。２次元モデル条件生成手段３２は、これらの２次元モデル条件６３を生成して、記憶装置４０に記憶させる。予め定めた割付け方法とは、例えば、特許文献３や特許文献４に示した方法、あるいはFirst Fit法である。予め定めた割付け方法で割付けできなければ、最終的にカッティング手順データ５５を生成できないから、実行可能解としない。
【００４３】
［費用係数ベクトル］
ｋ種類の原材料ごとに、価格だけでなく、運搬費、保管費、加工賃等が異なる。計算に含めるべき全ての費用要素をｎ次の費用係数ベクトルｆに含め、下記のように定義する。
ｆ＝（ｆ1,ｆ2,…,ｆn）
費用係数ベクトルｆは選択されたｎ種類の原材料にのみ適用されるから、ｎ次のベクトルになっている。なお、計算の便宜上、ｆ1,ｆ2,…,ｆnは、費用換算してしまい、単位を円とする。従って、目的関数値が小さいほど、少ないコストで製品を得ることができる。
【００４４】
費用係数ベクトルの要素は費用（コスト）である。コストが面積に比例する場合は、歩留が最高になる場合と総費用が最小になる場合とは同意である。しかし、単位面積当たりの価格が原材料により異なる場合には、費用係数を調整する。費用係数ベクトル生成手段２７は、原材料面積ベクトルsmの各要素に価格成分を含めてｎ次の費用係数ベクトルｆを生成する。費用係数ベクトルｆの要素ｆiは、単位が円のデータである。費用係数ベクトル生成手段２７が、原材料面積ベクトルsmを費用係数ベクトルｆで置き換えるようにすれば、以下は、費用係数ベクトルｆを意識することなく演算処理ができる。
【００４５】
［目的関数］
この計算では、ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付ける。このとき、目的関数値が小さいほど少ないコストで製品を得ることができる。そこで、選択したｎ枚の原材料にかかる費用の総和を示す目的関数を下記のように定義する。
Ｍｉｎ  Σｆi・ｘi
目的関数生成手段２８は、選択したｎ枚の当該原材料にかかる費用の総和を示す目的関数を生成して、記憶装置に記憶させる。
【００４６】
［整数計画を連続緩和問題とする］
シンプレックス法による演算処理を実行するために、特許文献３のように単純化した例では、目的関数と制約条件を次のように定義する。
Ｍｉｎ        Σｆi・ｘi
subject to     Ａｘ≧ｂ
Cｘ＝ｄ
０≦ｘi≦１
【００４７】
第１番目の式は、目的関数生成手段により生成された目的関数である。
第２番目の式は、制約条件生成手段により生成された第１制約条件式である。
第３番目の式は、制約条件生成手段により生成された第２制約条件式である。
第４番目の式は、制約条件生成手段により生成された第３制約条件式である。
目的関数は、選択したｎ枚の当該原材料にかかる費用の総和を示す。
第１制約条件式は、割付パターン行列Ａと使用枚数ベクトルｘと製品要求数量ベクトルｂの関係を示す。
第２制約条件式は、原材料使用行列Ｃと原材料の使用枚数ベクトルｘと原材料使用予定数量ベクトルｄの関係を示す。
第３制約条件式は、ｘiが０以上１以下であることを示す。既に説明したように、本発明の場合には、この第３制約条件式が不要になる。
【００４８】
初期設定手段２３は、任意の方法で取得した任意の初期実行可能解４４を受け付ける。そして、シンプレックス演算処理のためのパラメータを生成する。任意の方法とは、先に説明した予め定めた割付け方法である。初期実行可能解４４は、初期設定の段階で、上記の２次元モデル条件を満たすかどうかの判定がされる。初期設定手段２３は、上記の２次元モデル条件６３を満たすもののみを、初期実行可能解４４に設定する。初期実行可能解は、上記の割付パターン行列Ａから選択される割付パターンベクトルを指定する原材料の使用枚数ベクトルｘで表すことができる。これも、実施例３でより具体的に説明をする。最初のシンプレックス演算処理のために入力するパラメータは、目的関数Σｆi・ｘiと第１制約条件式Ａｘ≧ｂと第３制約条件式０≦ｘi≦１を構成するデータである。
【００４９】
探索制御手段３０は、シンプレックス演算処理手段２９に対して、Cｘ＝ｄの制約条件を除外したパラメータを入力して最初の演算処理を実行させる。シンプレックス演算処理手段２９は、目的関数の値を改善するようにシンプレックス表の基底変数を変更して解を出力する。第３制約条件式０≦ｘi≦１は、ｘi∈｛０，１｝という制約条件を緩和したものである。従って、解には、ｘi＝０．５といった整数以外のものが含まれる場合もある。また、目的関数の値が同一の解が複数存在することもある。
【００５０】
探索制御手段３０は、得られた解の中に、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解を検出する。検出されたときは、その解を最適解として、部材割付データ５３を生成して、処理を終了する。それ以外の場合には、探索制御手段は、次のシンプレックス演算処理のためのパラメータを再生成する。まず、初期設定をした実行可能解の目的関数の値Ｆ０を最大値に設定する。初期設定の解を改善するのが目的だからである。また、最初のシンプレックス演算処理で得られた解の目的関数の値Ｆ１を最小値に設定する。条件を緩和して得られた解であるから、そのときの目的関数値が限界値と判断する。
【００５１】
次に、探索制御手段３０は、目的関数の値がＦ１以上、Ｆ０未満となる、原材料の枚数の組合せを列挙して、組合せリストを生成する。これは、原材料使用予定数量ベクトルｄに該当する。この組合せリストの中から目的関数の値が最小のものを次候補に選定する。この具体例は実施例３で説明するが、制約条件生成手段２６は、第２制約条件式Cｘ＝ｄを生成する。目的関数や割付パターンベクトル等のパラメータに変更があれば第１制約条件式Ａｘ≧ｂも生成する。その後、探索制御手段３０は、シンプレックス演算処理手段２９に対して、生成したパラメータを入力して演算処理を実行させる。第３制約条件式０≦ｘi≦１は変更しない。
【００５２】
その結果、得られた解に、ｘiの値がいずれも０または１であって、それ以外の値を含まないものを検出する。検出されたときは、その解を最適解とする。この探索処理のための演算時間を短縮するために、後で説明するような評価式を用いた制御を実行する。最適解が得られないときには、原材料の枚数の組合せのリスト中で、目的関数の値が上記の次候補と同値のものがあれば、それを次候補に選定する。なければその次に小さいものを次候補に選定する。そして、前回と全く同様にして、第２制約条件式Cｘ＝ｄを生成し、パラメータを変更して、シンプレックス演算処理手段２９に対して、生成したパラメータを入力して演算処理を実行させる。
【００５３】
こうして、シンプレックス演算処理を繰り返して、最適解を探索する。なお、原材料の枚数の組合せのリストが多数生成されたときは、原材料の枚数の組合せの選択回数に上限を設けて、一定回数以上探索しても最適解がみつからなければ、初期実行可能解を最適解として、部材割付データ５３を出力するとよい。また、以上の演算処理では、割付パターン行列Ａと使用枚数ベクトルｘと製品要求数量ベクトルｂの関係を示す制約条件を使用したので、シンプレックス演算処理のパラメータに製品の寸法が含まれず、計算が煩雑にならない。また、各要素が０または１のみの値をとる原材料の使用枚数ベクトルｘが基底変数になるようにパラメータを設定し、０≦ｘi≦１という緩和した制約条件でシンプレックス演算処理を実行するので、最適解が得られない場合でも目的関数の最小値を得て、探索範囲を限定することができる。
【００５４】
図４は、初回のシンプレックス演算処理動作フローチャートである。
これらの図を用いて、上記のシステムを制御するコンピュータプログラムの実施例を説明する。
ステップＳ１１では、原材料設定手段２２が原材料データの受け付けをする。端末装置１６から、使用される全ての原材料データの入力を受け付けて、原材料ベクトル４３に対応するデータを生成し、記憶装置４０に記憶させる。即ち、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置４０に記憶させる。ステップＳ１２では、製品設定手段２１が、製品に関するデータの入力受け付けをする。端末装置１６から、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置４０に記憶させる。
【００５５】
ステップＳ１３では、初期設定手段２３が２次元モデル条件を満たすと判定された初期実行可能解４４の入力を受け付ける。その結果は  記憶装置４０に記憶される。ステップＳ１４では、割付パターンベクトル生成手段２４が、割付パターンベクトルの生成をする。割付パターンベクトルは、記憶装置４０に記憶される。続いて、ステップＳ１５で、割付パターン行列生成手段２５が割付パターン行列４６の生成をして、記憶装置４０に記憶させる。次に、ステップＳ１６で、制約条件生成手段２６が、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０を生成して、記憶装置４０に記憶させる。
【００５６】
ステップＳ１７では、費用係数ベクトル生成手段２７が費用係数ベクトルの生成をし、ステップＳ１８では、目的関数生成手段２８がその費用係数ベクトルを使用して目的関数５１の設定をする。その結果が記憶装置４０に記憶される。次に探索制御手段３０が、ステップＳ１９で、後で説明するように最初の演算用パラメータをシンプレックス演算処理手段２９に入力する。ステップＳ２０では、この演算用パラメータを使用したシンプレックス演算を実行する。解が得られたら探索制御手段３０は、ステップＳ２１で、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから、ステップＳ２３で部材割付データとカッティング手順データを出力して処理を終了する。ノーのときはステップＳ２２の処理に移行する。ステップＳ２２では、探索制御手段３０が、図５に示した手順で、シンプレックス法による演算を制御する。
【００５７】
図５は、１回目のシンプレックス演算終了後の演算処理のフローチャートである。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数値の範囲で、原材料の組合せリストの生成をする。その結果を目的関数値の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、後で説明するように制約条件の設定をする。
【００５８】
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ピボット演算処理を繰り返したかどうか判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。
【００５９】
（ファーストフィット）
特許文献３に記載された上記の方法により、原材料の縦長データと横長データと、この原材料から切り出す製品の縦長データと横長データとを指定して、最適な歩留の割付けが可能になる。即ち、原材料と製品とを、縦長と横長と面積の制約を考慮して組み合わせた多数のパターンの中から、歩留が最大となるパターンの組合せを求めることができる。さらに、原材料から製品を切り出した残りの原材料に、他の製品の割付が可能かどうかを判定する処理を含めると、原材料から製品を切り出すカッティング手順データを生成することができる。
【００６０】
一方向の長さだけに着目する１次元割り付けでは、原材料長が割付けた製品長の和以上ならば（刃物厚を無視して）、割付可能と判定できる。しかし、縦長と横長とを考慮する２次元割り付けでは、原材料面積が割付けた製品の面積の和以上でも、ただちに割付可能と判断することができない。そこで、例えば、実装プログラムでは、製品に適当な順序を付ける。例えば、縦長の降順、横長の降順、面積の降順等にデータを整列させる。この順番に製品データを取り出す。
【００６１】
図６は、原材料から製品を切り出す手順と新たな原材料の説明図である。
この処理は、カッティングデータ生成手段３４（図１）が実行する。図６に示すように、原材料の左下隅を原点として、原材料６０に、製品データ中から取り出した製品６２を配置できれば配置し、できなければ製品データ中の次の順番の製品を取り出す。配置できた場合には、縦ギロチンカットから始めるか横ギロチンカットから始めるかを決めて、一方を選択する。縦ギロチンカットから始める場合には、図６（ａ）に示すように、原材料６０を縦方向に切断して、切り離された新たな原材料７０と７１を得る。
【００６２】
原材料７０から製品６２を切り出して新たな原材料７２を得る。これら２枚の新たな原材料７１，７２に対して、製品データ中から次の順番の製品を取り出し、同様の割り付け処理を行い。全ての製品がなくなるまでこの処理を繰り返す。
【００６３】
このように、製品を取り出す順序を決めて取り出し、割り付けができた製品から割付けを決めていくことを、ファーストフィットと呼ぶ。そして、上記のように、元の原材料を切断して、切り離されたものを新たな原材料とみなして同じ割り付け処理を繰り返すことを再帰的割り付けと呼ぶ。再帰的割り付け処理にしておくと割り付けるべき製品が無くなるまで一定のループを繰り返し実行すればよくプログラムが簡単になる。
【００６４】
（ギロチンカット）
製品が全て長方形の場合の、ファーストフィット（再帰的）による割り付け処理は、上記のように、例えば、製品を縦に長い順に整列させてから、１番目の製品を取りだして母材に割付ける。図１に示したカッティングデータ生成手段３４は、縦ギロチン割付と横ギロチン割付のいずれかを自動的に選択する機能を持つ。縦ギロチン割付は、先ずＹ方向のカットを、次にＸ方向のカットを行うものである。そして、切り離された原材料を新たな原材料として、再帰的に割付を進める。横ギロチン割付は、図のように先ずＸ方向のカットを、次にＹ方向のカットを行うものである。
【００６５】
（非ギロチンカット制約）
上記の方法を利用して、長方形の製品だけでなく、図６（ｂ）や（ｃ）に示すような、Ｌ字形やＵ字形等の多角形の製品を含む割付計算も可能である。割付計算を開始する前に、これらの長方形でない多角形の製品については、その多角形を包含する最小の長方形の製品と見なす処理をしておく。この最小の長方形を「みなし長方形」と呼ぶことにする。図１に示したみなし長方形設定手段３５は、みなし長方形を設定して、その横長データと縦長データを、上記のｍ枚の製品に含めるように条件を設定する機能を持つ。
【００６６】
割付計算を進めながら、上記のように、原材料から製品を切り出した残りの原材料に、他の製品の割付が可能かどうかを判定する。このとき、図６（ｂ）に示すように、みなし長方形から多角形の製品６３を切り出して、残りの新たな原材料７３に、他の製品の割付が可能かどうかも併せて判定する。図６（ｃ）に示した製品６４を切り出した残りの新たな原材料７４や７５についても同様である。
【００６７】
原材料から製品を切り出す工程では、実行可能解により製品が割付された原材料を、縦ギロチンの場合は、始めに縦ギロチンカットにより製品または製品を含む原材料を切り出す。その後、製品を含む原材料を一つずつ選択して、今度は横ギロチンカットで製品または製品を含む材料を切り出す。なお、始めに横ギロチンカットを実行し、上記と逆の手順で割付計算をしてもよい。結果が異なる場合には、より歩留の大きい方を選択する。
【００６８】
原材料を縦ギロチンカットするときは、切断可能な全ての切断線を検出して同じ方向に切断する。このほうが作業性が良いからである。この方向の切断線が無くなったら、切断後の原材料をひとつずつ選択して、最初の原材料からみたとき横ギロチンカットに相当する方向の切断線を検出して切断する。最初の原材料からみたときは、縦ギロチンカットと横ギロチンカットを交互に実行することになる。カッティングデータ生成手段３４（図１）がこのようなカッティング手順データ５５（図１）を生成することにより、１枚の原材料の合計切断回数を最小化することができる。
【００６９】
また、縦ギロチンと横ギロチンを組み合わせることにより、割付パターンの、場合の数を増やすことができる。これで探索空間が広くなり、計算時間が増加するが、最適解を見つけやすいという効果がある。
【００７０】
（非ギロチンカット用の切断刃）
図７は、部材切断手段１２１（図２）の主要部と原材料の横断面図である。
上記の処理で、みなし長方形から多角形の製品を切り出すときは、ギロチンカットができない部分が生じることがある。このときは、図７に示すように制御を行う。即ち、プレカット装置１７（図１）は、切断開始時には、切断刃６５を図の左端にあるように傾斜させた状態で移動させる。そして、切断刃６５を停止させる直前で、その刃の向きを原材料６０の面に垂直な方向に向ける。これで、例えば、図６（ｂ）のＡ点からＢ点までと、Ｃ点からＢ点までの切断をして、製品６３と新たな原材料７３を切り出すことができる。他の部分についても、同様に制御するとよい。
【実施例２】
【００７１】
（演算処理時間の短縮）
図８〜図１０は、演算処理で得られるデータ例説明図である。
上記のように組み合わせパターンを生成した場合には、演算処理時間が長時間になるおそれがある。本発明により、この演算処理時間を短縮するシステム構成を説明する。図８は、原材料から縦にして切り出しても横にして切り出しても構わない１５本の製品について、それぞれ長さと必要数ｂをリストしたものである。上記の制約条件式Ax≧ｂ、Cx=dで、１５本の製品の種類のｂの要素は全て１であった。全く長さの等しい製品でも、ｂi（i＝1〜k）＝１としてこのように別々の製品のように列挙すると、以下のように、汎用性のある計算処理ができる。
【００７２】
図９は、図８の条件に基づいてファーストフィットで求められた初期実行可能解を示す。
原材料ａ１には製品の１番と２番が割り付けられる。同様にして、原材料ａ７まで、１５種類の製品がそれぞれ割り付けられる。ここで、Ａは１５×７の行列、ｂは１５×１のベクトル、Ｃは１×７の行列、ｄは１×１のベクトルとなっている。
【００７３】
初期実行可能解ではx1=1,x2=1,x3=1,x4=1,x5=1,x6=1,x7=1が全て整数だから、少なくともこのパターンでの割付が可能という結果がでている。即ち、７枚の原材料から１５種類の製品を切り出すことができるという結果が得られている。
【００７４】
次に、バックトラック法でパターンを生成し、シンプレックス乗数を使用する感度解析に基づき初期実行解を改善できる割付パターンを図９の割付パターンに追加する。実際には、約１４０種類の割付パターンを生成することができた。そして、特許文献３に記載されたように、整数解（0,1）が得られるまで、Σｘ2（ｘ要素の２乗和）が増加するほうにピボット操作を繰り返す。これにより、最も歩留の大きい実行可能な割付パターンを自動的に選択する。
【００７５】
図１０は、上記の演算処理の結果得られた最適割付パターンの例である。図１１は、上記の初期実行可能解の割付パターンを図解したもので、図１２は最適解の割付パターンを図解したものである。図１０のように、ａ５、ａ６、ａ７の割付パターンを、ａ８とａ９に置き換えることができる。その結果、x1=1,x2=1,x3=1,x4=1,x8=1,x9=1というように、６枚の原材料に割り付けできるという結果が得られた。
【００７６】
図１１の例には、４枚の同一寸法の原材料６０を示す。（ａ）の原材料６０には２枚の（１）の製品を割り付ける。（ｂ）の原材料６０には、２枚の（２）の製品及び（７）の製品を割り付ける。（ｃ）の原材料６０には、（５）と（６）の製品を割り付ける。（ｄ）の原材料には、（３）と（４）の製品を割り付ける。
【００７７】
これを縦横寸法の一致する製品を並べて最適化すると、図１２のように、（ａ）の原材料６０に（５）と（６）と（７）の製品を割り付けられる。また、（ｂ）の原材料６０に、２枚の（２）と（３）と（４）の製品を割り付けられる。この最適化処理の結果、３枚の原材料に割付が可能になり、１枚分の原材料を節約できる。
【００７８】
ここまでの処理は、上記特許文献３に紹介された方法による。この方法ではAの要素、ｂの要素、Cの要素は、すべて０または１である。したがって、ｘの要素は０以上１以下（整数または実数）となる。続いて、本発明による演算処理を説明する。
【００７９】
図１３〜図１６は、演算処理時間を短縮する計算例によるデータ例説明図である。
上記特許文献３との違いは、Aの要素、ｂの要素が０以上の整数になることである。割付パターンベクトルは０または１以上の整数を使い、図１３では、ｂを必要数８とした。図９に示した初期実行可能解を、図１４に示すように、同一長さの製品の分をひとまとめにして書き換える。１番の製品が原材料ａ１、ａ２、ａ３、ａ４にそれぞれ２枚ずつ割付けられている。
【００８０】
ここまでは、x1=1,x2=1,x3=1,x4=1,x5=1,x6=1,x7=1という初期実行可能解である。ここで、図１５に示すように、同じ割付パターンベクトルであるａ１、ａ２、ａ３、ａ４をａ１を残して削除する。即ち、これによりＡは７×４の行列、ｂは７×１のベクトル、Ｃは１×４の行列、ｄは１×１のベクトルと上記図９の例よりもサイズを小さくできる。得られる初期実行可能解は、x1=4,x5=1,x6=1,x7=1となる。次に、バックトラック法＋組合せ順列で割付パターンを生成し、シンプレックス乗数を使用する感度解析に基づき初期解を改善できる割付パターンをAに追加する。整数解（０〜Ｎ）が得られるまで、ピシンプレックス演算によるピボット操作を繰り返す。
【００８１】
このとき、上記の発明では、Σｘ2が増加するほうにピボット操作を繰り返した。本発明では、別の評価式を使用する。即ち、整数解の個数が増加する方向にピボット操作を繰り返す。これにより、図１６に示すような結果が得られる。この結果は、図１２に示した割付結果に該当する。
【００８２】
ここで、本発明の計算の過程を検証する。本発明の計算では、約３０パターンの割付パターンベクトルが生成されて、その中から最適値を選択して図１６に示す結果を得た。
【００８３】
図１７と１８に、本発明による具体的な演算処理方法のフローチャートを示す。
図１７により、主としてシンプレックス演算処理実行のための前処理について説明する。まず、ステップＳ４１で製品ベクトル４１の設定をする。即ち、製品設定手段２１は、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とするｍ次の製品要求数量ベクトルｂとを生成する。こうして得られた製品ベクトル４１を記憶装置４０に記憶させる。
【００８４】
次に、ステップＳ４２で原材料ベクトル４３の設定をする。即ち、原材料設定手段２２は、用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成する。こうして得られた原材料ベクトル４３を記憶装置に記憶させる。
【００８５】
ステップＳ４４では、初期設定手段２３が、予め定めた割付け方法で求められた初期実行可能解４４の入力を受け付けて、ｍ次の初期割付パターンベクトル４６ａと初期割付パターン行列４６を生成して、記憶装置４０に記憶させる。この結果は図９に示したとおりである。
【００８６】
ステップＳ４３では、２次元モデル条件生成手段３２が、第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件６３の生成をする。第１評価条件は割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする条件である。第２評価条件は、隣接する製品が重ならないとする条件である。第３評価条件は、割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする条件である。
【００８７】
ステップＳ４５では、横長データと縦長データが同一の製品を検出する。そして、ステップＳ４６では、製品再設定手段３６が、製品ベクトル４１の再設定をする。即ち、同一な製品をまとめて１つの要素とする。そして、同一な製品の横長を要素とするｍ次未満の製品横長ベクトルwp１と、同一な製品の縦長を要素とするｍ次未満の製品縦長ベクトルhp１と、同一な製品の面積を要素とするｍ次未満の製品面積ベクトルsp１と、ｍ次未満の製品要求数量ベクトルｂ１を生成する。
【００８８】
ステップＳ４７では、初期設定変換手段３７が、初期の割付パターン行列４６の再設定をする。即ち、初期割付パターンベクトルを前記同一な製品に対応するｍ次未満の割付パターンベクトルに変換し、初期割付パターン行列を前記m次未満の割付パターンベクトルに対応する割付パターン行列に変換して、記憶装置４０記憶する。こうして、図１５に示したデータが得られる。
【００８９】
ステップＳ４８では、割付パターンベクトル生成手段２４が、条件を満たす割付パターンベクトル４６ａの生成をする。即ち、求められているｍ次未満の製品横長ベクトルwp１に含まれる製品横長データと、ｍ次未満の製品縦長ベクトルｈp１に含まれる製品縦長データとを、用意されたｋ種類の原材料の原材料横長データと原材料縦長データと比較して、上記２次元モデル条件６３を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次未満の割付パターンベクトルａｊを列挙する。
【００９０】
ステップＳ４９では、割付パターン行列生成手段２４が、割付パターンベクトル４６ａを並べた割付パターン行列４６（Ａ）を生成して、記憶装置４０に記憶させる。ステップＳ５０では、目的関数生成手段が、目的関数Σｆｘを生成をする。即ち、製品を割り付けたｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置４０に記憶させる。
【００９１】
ステップＳ５１では、制約条件生成手段２６が、第１制約条件式Ａｘ≧ｂ１を生成する。即ち、割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式を生成して、記憶装置４０に記憶させる。
【００９２】
ステップＳ５２では、シンプレックス演算処理手段２９が、初期実行可能解４４と目的関数５１と制約条件式４８と４９の入力を受け付けて、シンプレックス演算処理を実行する。ステップＳ５３では、探索制御手段３０が、探索制御により最適解を探索して出力する演算処理を実行する。
【００９３】
探索制御手段３０は、図１８に示すような制御を実行する。まず、ステップＳ６１では、シンプレックス演算処理により、得られたｘｉは０以上の整数のみかどうかという判断をする。この判断の結果がイエスのときはステップＳ７２の処理に移行し、ノーのときはステップＳ６２の処理に移行する。ｘｉの値が０以上の整数であって、それ以外のものを含まない解のときは、その解を最適解としてステップＳ７２で部材割付データ５３を出力する。
【００９４】
ステップＳ６２では、探索制御手段３０が、初期実行可能解４４の目的関数５１の値を最大値に設定する。さらに、ステップＳ６３で、シンプレックス演算処理の結果得た目的関数５１の値を最小値に設定する。次に、ステップＳ６４で、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙する。ステップＳ６５では、目的関数５１が最小値に近いものを選択し、制約条件生成手段２６に対して第２制約条件式４９の生成を依頼する。
【００９５】
ステップＳ６６で、制約条件生成手段２６は、第２制約条件式Ｃｘ＝ｄの生成をする。第２制約条件式は、どの種類の原材料を何枚選択して割付けに使用するかを定めたものである。これは、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする式である。
【００９６】
探索制御手段３０はシンプレックス演算処理手段２９に演算処理を依頼する。ステップＳ６７でシンプレックス演算処理手段２９は、第１制約条件式４８と第２制約条件式４９の制約条件下で、演算処理を実行する。
【００９７】
探索制御手段３０は、ステップＳ６８で、非整数解を伴う実行可能解が得られたかどうかという判断をする。この判断の結果がイエスのときはステップＳ６９の処理に移行し、ノーのときはステップＳ６１の処理に戻る。非整数解を伴う実行可能解が得られたとき、ステップＳ６９では、評価式Σ（整数ｘｉの個数）を求める。
【００９８】
非整数解を伴う実行可能解が得られて、さらにその後のシンプレックス演算処理で、再び非整数解を伴う実行可能解が得られたときには、ステップＳ７０で、評価式の値が増加したかどうかという判断をする。この判断の結果がイエスのときはステップＳ６７の処理に移行し、ノーのときはステップＳ７１の処理に移行する。即ち、価式の値が増加している限りシンプレックス演算処理を繰り返して、ｘｉの値が０以上の整数であって、それ以外のものを含まない整数解を求める。
【００９９】
整数解が得られないまま評価式の値が減少したときは、ステップＳ７１で、制約条件生成手段２６に対して第２制約条件式４９の変更を依頼する。こうしてステップＳ６７に戻り、改めて整数解の探索を付ける。以上の処理により、図１４、図１５、図１６で説明した最適解を得ることができる。
【実施例３】
【０１００】
（一次元モデル）
上記の演算処理は、長さだけで幅を問題としない棒状の原材料に棒状の製品を割り付けする場合にも応用できる。この場合には、上記の「ｍ枚の製品」を「ｍ本の製品」と読み替え、「面材割付データ」は「割付データ」と読み替えるとよい。
【０１０１】
そして、１次元では、割り付けられる製品長の和が原材料長以下であれば（第１評価条件）、２次元における重ならない（第２評価条件）、どう配置するか（第３評価条件）は自動的に満たされるので、第１評価条件だけ考慮すればよい。従って、第１〜３評価条件を一次元モデル条件と読み替えるようにする。
【０１０２】
即ち、それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する。
【０１０３】
一次元モデルでは、下記のように演算処理のパラメータを設定する。その他の設定は、上記の実施例と同様である。シンプレックス演算処理も、評価式の設定も同様である。
（ａ）製品の長さを要素とするｍ次の製品長ベクトルwp
（ｂ）製品要求数量を要素とするｍ次の製品要求数量ベクトルｂ
（ｃ）原材料の長さを要素とするｋ次の原材料長ベクトルwm
（ｄ）原材料の種類番号を要素とするｋ次の原材料番号ベクトルnm
（ｅ）第１評価条件（wp，ａｊ）≦wm
（割付け製品の長さの和は原材料長ベクトルwmの要素のうちのいずれかの原材料の長さ以下である）
【０１０４】
棒状の原材料に棒状の製品を割り付ける場合には、演算処理の要素は単純になる。しかしながら、建築材料の場合には、原材料の種類も製品の長さの種類も面材に比較して格段に多くなることが多い。従って、場合の数も膨大になるから、本発明のような演算処理時間の短縮化はきわめて有効になる。
【０１０５】
なお、一次元モデルの場合には、製品を長いものから順に配列し、原材料を長いものから順に配列して、ファーストフィット法で割付けを実行するとよい。また、上記の実施例と同様に、原材料から製品を切り出した残りの部分も原材料に含めて、原材料に割り付ける製品の組合せを決定するとよい。
【０１０６】
上記のように、本発明では、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、ｘｉの値が０以上の整数としたことで、シンプレックス演算処理に使用する評価式を新たに設定した。この評価式は、より歩留の良い実行可能解を探索するために演算処理を繰り返す場合に、これ以上計算を繰り返しても良い結果が得られないという見通しをたてて、次の演算処理に移るタイミングを決めるために使用される。評価式は各種考えられるが、その設定のしかたにより、全体の演算処理時間が大きく影響する。
【０１０７】
本発明で使用する評価式は、ｎ次の使用枚数ベクトルｘの整数であるものの個数である。すべてのｘが０以上の整数になるときはｎ（個）になる。１つでも整数でないものがあるとｎ未満になる。この評価式は、山登り法、ランダムリスタート、焼き鈍し法で探索する場合に有効である。すなわち、ｘｉが整数である個数が増加していく限り探索を続け、増加しなければ探索を打ち切ることで、短時間で整数解を見つけることができる。実際に計算をさせてみると、次数が大きくなるとこの方法は成り立たなくなることがある。しかし、建材の割付け演算処理については、適度な次数の範囲におさまるので、この評価式で実用上問題ないことがわかった。
【０１０８】
本発明の方法と特許文献３の演算処理結果との演算処理時間を比較する。例えば、標準的な住宅の断熱材の製品の数量は６０〜２００枚である。その形状種類の数は１０〜５０である。本発明の方法と特許文献３の方法の演算処理を汎用のパーソナルコンピュータで実行する。二次元モデルで、製品数量が２００枚ほどあると、従来の方法と比較して、本発明の方法では、探索のために生成する割付パターン行列を１０分の１程度あるいはそれ以上に大きく絞り込める。これにより、演算処理時間を数十分の１にすることができる。住宅に使用する建材は同一寸法のものが多いため、本発明の方法はきわめて有効に機能する。
【０１０９】
上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組合せて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。
【符号の説明】
【０１１０】
１０  部材割付システム
１２  コンピュータ
１４  ネットワーク
１６  端末装置
２０  演算処理装置
２１  製品設定手段
２２  原材料設定手段
２３  初期設定手段
２４  割付パターンベクトル生成手段
２５  割付パターン行列生成手段
２６  制約条件生成手段
２７  費用計数係数ベクトル生成手段
２８  目的関数生成手段
２９  シンプレックス演算処理手段
３０  探索制御手段
３１  判定手段
３２  ２次元モデル条件生成手段
３４  カッティングデータ生成手段
３５  みなし長方形設定手段
３６  製品再設定手段
３７  初期設定変換手段
３８  原材料使用行列生成手段
４０  記憶装置
４１  製品ベクトルwp、hp、sp
４２  製品要求数量ベクトルｂ
４３  原材料ベクトルwm、hm、sm
４４  初期実行可能解
４５  原材料使用予定数量ベクトルｄ
４６  割付パターン行列
４６ａ  割付パターンベクトル
４７  原材料使用行列Ｃ
４８  第１制約条件式
４９  第２制約条件式
５０  第３制約条件式
５１  目的関数
５２  組合せリスト
５３  部材割付データ
５４  評価式
５５  カッティング手順データ
６０  原材料
６２  製品
６３  多角形
６４  多角形
６５  切断刃
７１  新たな原材料
７２  新たな原材料
７３  新たな原材料
７４  新たな原材料
７５  新たな原材料
【要約】
【課題】ｋ種類の長方形の原材料から、長方形のみならず多角形のｍ個の製品を切り出すための割付計算をして、その歩留を最大にする。その際同一形状の製品はまとめることにより、計算時間短縮を図る。
【解決手段】割付計算を開始する前に、長方形でない多角形の製品については、その多角形を包含する最小の長方形の製品と見なす処理をしておく。割付計算を開始後、原材料から製品を切り出した残りの原材料に、他の製品の割付が可能かどうかを判定する。このとき、多角形を包含する長方形から多角形の製品を切り出して、残りの原材料にも他の製品の割付が可能かどうか判定する。さらに同一形状の製品をまとめて割り付けパターンを行列の低次元化を図る。
【選択図】図１【図１】
0005983976.tif 000002
【図２】
0005983976.tif 000003
【図３】
0005983976.tif 000004
【図４】
0005983976.tif 000005
【図５】
0005983976.tif 000006
【図６】
0005983976.tif 000007
【図７】
0005983976.tif 000008
【図８】
0005983976.tif 000009
【図９】
0005983976.tif 000010
【図１０】
0005983976.tif 000011
【図１１】
0005983976.tif 000012
【図１２】
0005983976.tif 000013
【図１３】
0005983976.tif 000014
【図１４】
0005983976.tif 000015
【図１５】
0005983976.tif 000016
【図１６】
0005983976.tif 000017
【図１７】
0005983976.tif 000018
【図１８】
0005983976.tif 000019