部材割付システム
【課題】ｋ種類の長方形の原材料から、長方形のｍ個の製品を切り出し、その歩留を最大にする。既存の線材を対象にした探索法を面材に適用する。
【解決手段】予め求めた初期実行可能解の目的関数の値を最大値とし、原材料の使用枚数について緩和された制約条件式０≦ｘi≦１を設定してシンプレックス演算処理をする。その結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙する。その後、原材料の使用枚数の組合せを固定した制約条件でシンプレックス演算処理を実行し、得られた複数の非整数解を所定の評価式で評価する。初期実行可能解を面材固有のＦＦ法により求め、探索の結果をＦＦ法に当てはめて、板取りと切断順を出力する。
【解決手段】予め求めた初期実行可能解の目的関数の値を最大値とし、原材料の使用枚数について緩和された制約条件式０≦ｘi≦１を設定してシンプレックス演算処理をする。その結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙する。その後、原材料の使用枚数の組合せを固定した制約条件でシンプレックス演算処理を実行し、得られた複数の非整数解を所定の評価式で評価する。初期実行可能解を面材固有のＦＦ法により求め、探索の結果をＦＦ法に当てはめて、板取りと切断順を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、面材の板取りを最適化するための、部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置に関する。
【背景技術】
【０００２】
住宅構造材のプレカットには、断面形状や樹種，等級、レイヤといった仕様ごとに数種類の長さ３〜６メートルの原材料が用意される。そこから求められる寸法の部材(製品)を切り出す。製品の仕様と、製品の寸法と、切り出される原材料の組合せにより、原材料から切り落とされて無駄になる部分の量が異なる。実際に、１％の歩留向上により多量の廃棄物減量を図ることができる。柱や一定の幅の板といった線状材料については、シンプレックス演算処理を利用し、山登り法、ランダムリスタート法、焼き鈍し法等により、歩留あるいは費用を最小にするための最適値を探索する技術が開発された（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−９８９２４号
【特許文献２】特許３０７９１８９号公報
【特許文献３】特許３４４１４２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の特許文献１に記載された方法は、予め既存の方法で求めた初期実行可能解を起点にして、さらに何パーセントかの歩留向上を図るために、所定の演算処理を実行する。種々の縦横寸法を持つ製品（面材）を原材料（面材）から切り出す場合にも、特許文献１に記載の技術が利用できる。その場合に、初期実行可能解を求めるには、特許文献２、３等に記載された技術が利用できる。しかしながら、特許文献１の方法を面材の切り出しに適用するためには、１次元の計算を２次元に拡張するため、面材固有のパラメータを選択して、それらを有効に使用する手法の開発が必要になる。また、面材を縦横に切断するため、製品と原材料との最適な組み合わせを求めただけでは、具体的な板取りが分からない。具体的なプレカット作業のための指示書を作成するために、演算処理の最終段階で、板取りや切断順を明示しなければならない。
【０００５】
本発明は、以上の課題を解決するためになされたもので、面材を高い歩留で原材料から切り出すための部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件wpi+wpj≦wmlまたはhpi+hpj≦hmlと、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、
前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶する初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【０００７】
〈構成２〉
構成１に記載の部材割付システムにおいて、前記第１制約条件式と第３制約条件式の制約条件の下で、または前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の下で、前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、複数の解が存在するとき、予め定めた判定手段で、別の解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
【０００８】
〈構成３〉
構成２に記載の部材割付システムにおいて、前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【０００９】
〈構成４〉
構成２に記載の部材割付システムにおいて、前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【００１０】
〈構成５〉
構成３乃至４に記載の部材割付システムにおいて、順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
【００１１】
〈構成６〉
構成５に記載の部材割付システムにおいて、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
【００１２】
〈構成７〉
構成１乃至６のいずれかに記載の部材割付システムにおいて、前記探索制御手段は、前記シンプレックス演算手段に演算処理を依頼するという動作の繰り返し回数に上限を設けたことを特徴とする部材割付システム。
【００１３】
〈構成８〉
構成１乃至７のいずれかに記載の部材割付システムにおいて、前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする部材割付システム。
【００１４】
〈構成９〉
構成１乃至８に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【００１５】
〈構成１０〉
構成９に記載の部材加工装置において、前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶しておき、前記判定結果を使用して、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成して出力することを特徴とする部材加工装置。
【００１６】
〈構成１１〉
コンピュータを、構成１乃至８に記載の各手段として機能させる部材割付プログラム。
【００１７】
〈構成１２〉
コンピュータを、構成１乃至８に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【００１８】
〈構成１３〉
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品設定手段が、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料設定手段が、用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させるステップと、
２次元モデル条件生成手段が、割付け製品の面積は
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hmlと、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶するステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【発明の効果】
【００１９】
面材について、シンプレックス演算処理を利用して、歩留の改善を図り、具体的な板取りを含めたプレカット作業のための切断手順を含む指示書を作成する
ることができる。
【図面の簡単な説明】
【００２０】
【図１】実施例１の部材割付システム１０のブロック図である。
【図２】部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
【図３】演算処理のパラメータを説明するための説明図である。
【図４】初回のシンプレックス演算処理動作フローチャートである。
【図５】１回目のシンプレックス演算終了後の演算処理のフローチャートである。
【図６】割付パターンベクトルの説明図である。
【図７】予め定めた割付け方法の説明図である。
【図８】ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
【図９】ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
【図１０】評価式の意味の説明図である。
【図１１】本発明の主要動作のフローチャートである。
【図１２】割付対象製品と使用する材料の具体例説明図である。
【図１３】初期実行可能解を含む１〜１５の割付けパターンベクトルの説明図である。
【図１４】２２６９８種類の割付けパターンベクトルの説明図である。
【図１５】到達した実行可能解の説明図である。
【図１６】非整数解の説明図である。
【図１７】非整数解と整数解の比較例説明図である。
【図１８】歩留改善効果の説明図である。
【図１９】部材加工装置のブロック図である。
【図２０】ＦＦ法による割付け結果を示す。
【図２１】ＦＦ法による割付け結果を示す。
【図２２】ＦＦ法による割付け結果を示す。
【図２３】ＦＦ法による割付け結果を示す。
【図２４】ＦＦ法による割付け結果を示す。
【図２５】ＦＦ法による割付け結果を示す。
【図２６】ＦＦ法による割付け結果を示す。
【図２７】実施例２の処理による割付け結果を示す。
【図２８】実施例２の処理による割付け結果を示す。
【図２９】実施例２の処理による割付け結果を示す。
【図３０】実施例２の処理による割付け結果を示す。
【図３１】実施例２の処理による割付け結果を示す。
【図３２】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３３】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３４】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３５】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３６】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３７】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図３８】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図３９】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図４０】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【発明を実施するための形態】
【００２１】
本発明では、既存の任意の方法で得られた実用性のある解を基礎にして、それをシンプレックス法で評価し、さらに改善した解を求める。シンプレックス法は、線形計画問題の最適解を探索する方法として知られている。しかし、求められた製品の寸法の種類や原材料の種類が数十種類にも及ぶと、組合せの数は数十万組を越えることがある。ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付ける、といった条件に基づいてそのまま演算処理のためのパラメータを作ると、最適値探索のためのシンプレックス演算処理に時間がかかりすぎるおそれがある。そこで、本発明では、シンプレックス法による演算処理のための制約条件を付加して、比較対象範囲の絞り込みをしながら、効率よく計算をする。そして、シンプレックス法によるピボット演算処理の過程で実行可能解が得られたときに、所定の評価式を使用してその後の見通しをたてる。その結果に応じて探索条件を変更し、無駄な演算処理を回避する。従って、探索のための演算処理時間を大幅に短縮できる。以下、本発明の実施の形態を実施例ごとに詳細に説明する。
【実施例１】
【００２２】
図１は実施例１の部材割付システム１０のブロック図である。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、面材をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献３に記載されたとおりのものを使用することができる。
【００２３】
コンピュータ１２には、演算処理装置２０と記憶装置４０とが設けられている。演算処理装置２０には、図のように、製品設定手段２１、原材料設定手段２２、初期設定手段２３、割付パターンベクトル生成手段２４、割付パターン行列生成手段２５、制約条件生成手段２６、費用係数ベクトル生成手段２７、目的関数生成手段２８、シンプレックス演算処理手段２９、探索制御手段３０、及び判定手段３１等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。
【００２４】
記憶装置４０には、図のように、製品横長ベクトル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と、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置４０に記憶させる。
【００５８】
ステップＳ１３では、初期設定手段２３が
２次元モデル条件を満たすと判定された 初期実行可能解４４の入力を受け付ける。その結果は 記憶装置４０に記憶される。ステップＳ１４では、割付パターンベクトル生成手段２４が、割付パターンベクトルの生成をする。割付パターンベクトルは、記憶装置４０に記憶される。続いて、ステップＳ１５で、割付パターン行列生成手段２５が割付パターン行列４６の生成をして、記憶装置４０に記憶させる。次に、ステップＳ１６で、制約条件生成手段２６が、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０を生成して、記憶装置４０に記憶させる。
【００５９】
ステップＳ１７では、費用係数ベクトル生成手段２７が費用係数ベクトルの生成をし、ステップＳ１８では、目的関数生成手段２８がその費用係数ベクトルを使用して目的関数５１の設定をする。その結果が記憶装置４０に記憶される。次に探索制御手段３０が、ステップＳ１９で、後で説明するように最初の演算用パラメータをシンプレックス演算処理手段２９に入力する。ステップＳ２０では、この演算用パラメータを使用したシンプレックス演算を実行する。解が得られたら探索制御手段３０は、ステップＳ２１で、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから、ステップＳ２３で部材割付データとカッティング手順データを出力して処理を終了する。ノーのときはステップＳ２２の処理に移行する。ステップＳ２２では、探索制御手段３０が、図５に示した手順で、シンプレックス法による演算を制御する。
【００６０】
図５は、１回目のシンプレックス演算終了後の演算処理のフローチャートである。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数値の範囲で、原材料の組合せリストの生成をする。その結果を目的関数値の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、後で説明するように制約条件の設定をする。
【００６１】
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ピボット演算処理を繰り返したかどうか判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。本発明では、上記のステップＳ３７における探索動作に後で説明するような特殊な制御を行う。
【００６２】
図６から図１１までは、具体的な計算例の説明図である。
（原材料データ）
例えば、用意された原材料は５種類で、原材料名をＧＧ１〜ＧＧ５とする。
（製品データ）
求められている製品は７枚で、その製品名をＳＳ１〜ＳＳ７とする。
【００６３】
（割付パターンベクトル）
図６は、割付パターンベクトルの説明図である。
図の最も左側の上から下に向かう縦１列に、上記の７種類の製品名が列挙されている。また、最も上段の左から右に向かう横１列に、原材料名が列挙されている。各原材料名の下の縦一列が、それぞれ割付パターンベクトルである。例えば、原材料名ＧＧ１ものには、製品名がＳＳ２のものを１枚割り付けることができるとする。例えば、原材料名がＧＧ２のものには、製品名がＳＳ３とＳＳ６のものを各１枚割り付けることができるとする。この表には、この要領で、７枚の製品の寸法と５種類の原材料の寸法とを比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品との関係を示す７次の割付パターンベクトルを列挙する。ここで、ｘ１〜ｘ５は初期実行可能解から得られた割付パターンベクトルである。以下は、特許文献１に記載したとおりの手順で、この表を展開し、原材料の使用枚数ベクトルｘを求める。
【００６４】
（目的関数）
説明を簡略化するために、費用係数ベクトルｆの各要素を原材料面積と一致させる。
すなわち、面積の数値をそのまま円と読み替える。
図６の原材料名の部分を原材料の面積で表示すると、それらの数値は費用係数ベクトルｆの要素である。従って、最初のシンプレックス演算処理で、初期値として入力する実行可能解の目的関数Σ（ｆｉ・ｘｉ）の値は、ｘ１〜ｘ５の使用原材料の面積の総和である。以下の計算ではこれを改善する解を求めるのだから、目的関数値の上限値をこのとき求めた総和に定める。
【００６５】
本発明では、シンプレックス演算による解が得られたときの目的関数値を、最適値の下限値に設定する。即ち、初期実行可能解を改善することを目的とするから、目的関数値の初期値を最大値に設定し、最初のシンプレックス演算処理により得られた目的関数値を最小値に設定する。この範囲に最適値があるとし、再度探索をする。ここで、原材料を任意の枚数だけ組合せて、目的関数値がこの範囲にある場合を列挙する。例えば、組合せを選択しながら集計する演算処理結果を昇順にソートすればよい。
【００６６】
具体的なシンプレックス演算処理については、特許文献１に記載されたとおりであるから、その説明を省略する。こうして、原材料を節約できる割付パターンを見つけて、その結果を、部材割付データとして出力し、端末装置に送信する。
なお、２次元モデルについては、使用する原材料と各原材料から切り出す製品を特定したデータだけをプレカット装置に送っても、そのままではプレカット制御できない。初期実行可能解を求めるときにした、２次元モデル条件を満たすかどうかの判定処理において、予め定めた割付け方法で割付け可能かどうかの判定をした。この判定では、具体的に製品の割付け位置と原材料の切断位置と切断順とを確認する。その結果が記憶装置４０に記憶されている。
【００６７】
図７は、予め定めた割付け方法の説明図である。
予め定めた割付け方法は、例えば、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法（ＦＦ法）で割付けを実行する。その後、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、同様にファーストフィット法で割付けを実行し、さらに、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する。この全てを実行して、最適な割付け方法を見付ければよい。
【００６８】
その過程では、例えば、図７において、ある原材料５６の隅に製品５７を割付けたとする。このとき、製品５７のいずれかの辺を通る切断線５８で、原材料を切断する。切断後の原材料片を、製品５７の残りの辺を通る切断線５９で切断する。こうして残った原材料片６０と６１に、他の製品を割付けられるかどうか判断し、割付けられなかったら、廃材とする。この手順で割付けを行うと、製品の割付け位置と原材料の切断位置と切断順とが自動的に確定する。これを実行可能解の生成とともに、あるいは、２次元モデル条件を満たすかどうかの判定処理中に判定結果６４として、記憶装置４０に記憶させる。その判定結果６４を読み出して、カッティング手順データ５４を生成するとよい。このデータはそのままプレカット装置を制御できる。また、作業手順書を印刷して、作業者に手渡し、手動でのプレカットが可能になる。
【００６９】
（ＦＦ法）
図８と図９は、ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
ファーストフィット法（ＦＦ法）を用いて、面材の割付をする場合には、例えば、図に示すように、面積の広いものから順に割付をする。即ち、まず、最初のステップＳ１１で、原材料を面積降順に並べて読み出し順のリストを作成し記憶装置に格納する。ステップＳ１２では、製品を面積降順に並べて読み出し順のリストを作成し記憶装置に格納する。その後ステップＳ３からステップＳ１９の処理を繰り返す。
【００７０】
ステップＳ１３では、読み出し順のリストに従って、原材料を一枚選択する。ステップＳ１４で、この原材料に製品の割付試行処理をする。ステップＳ１４の処理の具体的な内容は後から図９を用いて説明する。ステップＳ１３で選択した一枚の原材料に対して、最も歩留の良い製品の割付けがステップＳ１４で見つかったら、ステップＳ１５で歩留の算出をする。
【００７１】
ステップＳ１６では、全ての原材料を選択し終わったかどうかという判断をする。この判断の結果がイエスのときはステップＳ１７の処理に移行し、ノーのときはステップＳ１３の処理に戻る。即ち、全ての種類の原材料について、ステップＳ１３からステップＳ１６の処理を繰り返す。全ての原材料についての処理が終了すると、ステップＳ１７でこれまでの計算結果を比較し、最大歩留の割付けを見付けて、一組の材料と製品の組み合わせを決め、これを採用する。
【００７２】
ステップＳ１８では、ステップＳ１７で組み合わせの決まった割付済の製品を、読み出し順のリストから削除する。ステップＳ１９では、全ての製品について、割付け処理が終了したかどうかという判断をする。この判断の結果がイエスのときはステップＳ２０の処理に移行し、ノーのときはステップＳ１３の処理に戻る。こうして、ステップＳ１３からステップＳ１９の
処理を繰り返して、全ての製品をいずれかの材料に割り付ける。これが終了するとステップＳ２０で総歩留の計算をする。こうして、ＦＦ法による割付処理が終了する。
【００７３】
図９は、原材料に製品の割付試行処理をするための動作フローチャートである。
まず、ステップ２１で製品の読み出し順リストに未割付の製品があるかを判断する。イエスのときはステップＳ２２の処理に移行し、ノーのときは処理を終了し、図８のステップＳ１５へ移行する。 ステップＳ２２では製品を読み出し順リストにしたがって一枚選択する。ステップＳ２３では選択した製品が原材料または残材に割付可能かどうかという判断をする。
【００７４】
最初は原材料が割付対象になり、２回目以降は残材が割付対象になる。ステップＳ２３の判断は選択した製品が原材料または残材の隅に割付可能かどうかである。イエスのときはステップＳ２４に移行し、ノーのときはステップＳ２１に移行する。ステップＳ２４では選択した製品を原材料または残材の隅に割付する。原材料も残材も長方形（正方形含む）だから四隅のいずれかに割付する。 ステップＳ２５ではギロチンカット（刃物を途中で止めない）で製品部と残材部に分割する。そしてステップＳ２１に移行する。これを一枚の原材料への割付が終了するまで繰返し、終了したら図８のステップＳ１５へ移行する。
【００７５】
（割付パターンベクトル生成）
最適解を得るために、総当り的に重複をせずすべての割付パターンを自動的に生成することは、例えばバックトラック法を利用すれば可能である。しかしそれでは、
図１２に示す２５枚の製品を２種類の原材料に割付ける場合を例にしても、その割付パターンの数は組合せ爆発を起こす。
【００７６】
これを避けるためシンプレックス乗数を用いた感度解析手法を前記２次元モデル条件に加えて割付パターンベクトル生成時に割付パターンベクトルの数を総当り相当を担保しながら合理的に絞り込むようにしてもよい。これは演算時間の大幅短縮に寄与する。
【００７７】
（評価式）
また、シンプレックス演算処理手段２９は、制約条件を満たす割付けパターンベクトルの組み合わせを、既知のシンプレックスタブローを使用したピボット演算により、探索する。使用する原材料の組み合わせが一定という制約条件を与えると、シンプレックス演算処理手段２９は、割付けパターンベクトルの組み合わせを少しずつ変更しながら、ｘの値が制約条件を満たす実行可能解を見付ける。このピボット演算の過程で得られる非整数解の出現順に規則性はない。ピボット演算開始時の初期条件が異なると、全く異なる過程でピボット演算が実行され、非整数解の出現順も変わる。最短時間で整数解に到達する最適な初期条件を見付ける方法は無い。運の悪いときには何万回ピボット演算を繰り返しても整数解が得られないことがある。
【００７８】
整数解が得られる前に、複数の非整数解が得られることもある。多数の非整数解が得られても、最後まで整数解が得られないこともある。最後まで整数解が得られなかったときは、条件設定をした原材料の組み合わせで最適解は無いということである。最後までピボット演算を繰り返すことは実用上の計算時間を考慮すれば不合理であるので、ピボット演算の繰り返し回数がＷ回に達したときに探索を打ち切って、別の原材料の組み合わせを選択するようにしてもよい。しかしながら、非整数解が出力されたときのシンプレックスタブローから得られる相対費用係数を監視すると、探索方針を決めることができる。相対費用係数が全部正の数になったときには、これ以上、実行可能解は無いと判断してよい。また、相対費用係数に一つでも０（ゼロ）が含まれていれば、実行可能解が他にもあると判断できる。従って、探索を続行するとよい。
【００７９】
しかしながら、前記割付パターンベクトル生成合理化を図っても、なお、割付けパターンベクトルの数が多い場合や、原材料の組み合わせの種類が多い場合には、シンプレックス演算処理手段２９による演算処理時間が膨大になるおそれがある。そこで、本発明では、複数の非整数解が得られたときに、以下に定義する評価式を用いて、その後の演算処理の結果を予測する。即ち、ピボット演算処理の結果、複数の非整数解が得られたとき、これらの非整数解を特定の評価式を適用して比較し、一定の判定基準を満たす場合にはピボット演算処理を続行する。判定基準を満たさない場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開する。また、あるいは、同一制約条件での演算処理を中止し、別の原材料の組み合わせを制約条件に設定する。
【００８０】
図１に示した評価式５４は、Σｆ（ｘｉ）と定義したデータである。Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最大値が一定値になる関数である。例えば、ｆ（ｘｉ）はｘｉのｎ乗（ｎ＞１）と定義することができる。また、あるいは、Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最小値が一定値になる関数である。例えば、ｆ（ｘｉ）はｓｉｎπｘｉとか、あるいは、ｆ（ｘｉ）はｘｉのｎ乗（０＜ｎ＜１）というように定義することができる。
【００８１】
図１０は、評価式の意味の説明図である。
ｆ（ｘｉ）をｘｉの２乗と定義して、評価式の意味を説明する。この評価式は、複数の非整数解が得られたときに、原材料の使用枚数ベクトルｘの要素ｘiの値の変化を観察するためのものである。即ち、それぞれの解に含まれる全てのｘiが整数に近づく方向にピボット演算が進んでいるかを判定することができる。概略的には、次のような理論になる。
【００８２】
例えば、使用枚数ｘ＝（ｘ１、ｘ２）とする。また、原材料の組み合わせＣを（１、１）とする。前者は列ベクトル、後者は行ベクトルである。（Cｘ＝ｄ）だから、ｘ１＋ｘ２＝１である。この場合、図１０（ａ）に示すように、ｘ１軸とｘ２軸の直交座標上で、ｘ１軸の切辺の座標が１でｘ２軸の切辺の座標が１の直線上に実行可能解があるということができる。直線の両端の白丸は整数解、中央の黒丸は非整数解になる。（ｂ）には、縦軸に評価式の値を示し、横軸にｘ１とｘ２の値を示した。
【００８３】
図１０の（ｂ）に示したのは使用枚数ベクトルｘの要素がｘ１とｘ２の場合の解空間である。評価式の最大値は１、最小値は０．５である。ベクトルｘの要素数が増えると解空間はこの図よりもさらに複雑になる。しかも、ピボット演算により求められる非整数解や整数解の出力順序も複雑である。従って、ある条件でピボット演算を開始して、順番に出力される実行可能解により得られる整数解あるいは非整数解の評価式の値は、図１０（ｃ）に示すように変遷する。黒丸が非整数解によるもので、白丸が整数解によるものである。
【００８４】
ここで、例えば、シンプレックス演算処理手段２９による演算処理が開始されて、所定のタイミングで、実行可能解Ｒ１が得られたとする。さらにその後、実行可能解Ｒ２が得られたとする。いずれも非整数解である。両者の評価式の値を比較すると、後から得られた非整数解の値が減少している。ここでさらにピボット演算を続行しても、評価式の値は減少していき、すぐに整数解には近づかないと判定する。そこで、このタイミングで初期条件を変更する。即ち、ピボット演算の開始点を変更する。
【００８５】
この演算処理では、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）とし、ｘiは０≦ｘi≦１とし、さらに、原材料の組み合わせが一定という制約条件（Cｘ＝ｄ）を追加して、シンプレックス演算処理手段２９を起動した。割付けパターンベクトルと制約条件は変えられない。一方、本発明の方法では、制約条件（Cｘ＝ｄ）に費用係数の値が含まれないようにし、かつ、基底変数も使用枚数ベクトルｘを使用したから、費用係数ｆiの値を変更しても解に直接影響がない。しかも、目的関数に含まれる費用係数ｆiの値を変更すると、ピボット演算の開始点や順序を変えることができる。例えば、仮に、費用係数ｆiの値を全て０にして演算処理を開始しても、費用係数ｆiの値を全て１にして、演算処理を開始しても、最終的には同じ結果が得られる。ところが、ピボット演算の過程は相異する。即ち、シンプレックス演算処理手段２９に対して、こうした変更可能な設定条件を変更することで、図１０（ｃ）の実行可能解Ｒ２が得られた時点でピボット演算を停止し、今度はタイミングｔ１からピボット演算を再開することができる場合がある。もちろん、他の任意の方法でピボット演算開始のための初期条件を変更できればよい。
【００８６】
タイミングｔ１からピボット演算を再開すると、その後、実行可能解Ｒ３が得られる。さらにその後、実行可能解Ｒ４が得られたとする。いずれも非整数解である。ここで、両者の評価式の値を比較すると、その値が増加している。このとき、さらにピボット演算を続行すれば、評価式の値は増加していき、整数解に近づく可能性が高いと判定する。こうした判断を、図１に示した判定手段３１が実行する。図１０（ｃ）の例では、その後無事に白丸で示した整数解に到達することができる。
【００８７】
しかしながら、実際には、同じ設定条件で演算処理を続行しても、必ず整数解が得られるとは限らない。従って、例えば、評価式の値が増加した後に整数解が得られないまま減少し始めたら、極大値を通過したものと判断して、別の上昇曲線を求めて設定条件を変更するとよい。例えば、費用係数ｆiの値を全て０の状態から全て１の状態まで順番に切り替えて、ピボット演算を繰り返せばよい。
【００８８】
以上の処理により、複数の非整数解が得られたときに、その後ピボット演算を続行しても良い結果が得られないと判断したら、その状態を回避し、別の条件からピボット演算を開始するようにして、演算処理時間を短縮することができる。また、例えば、初期条件を変更しても評価式の値が増加する傾向がみられない場合には、この制約条件での整数解は無いと判断して、原材料の組み合わせの制約条件（Cｘ＝ｄ）を変更して、演算処理を再開するとよい。
【００８９】
評価式の値が増加していく場合にのみピボット演算を続行するのは、既知の局所探索法でいう山登り法と呼ぶことができる。そして、ランダムに初期条件を変更するのをランダムリスタート法と呼ぶことができる。さらに、上記の評価式を利用して、既知の焼き鈍し法により、整数解を探索することができる。また、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときピボット演算を続行する方法も有効である。以上のように判定基準を定めて、図１に示した判定手段３１が、ピボット演算を続行するかどうかの判定をする。図１に示した探索制御手段３０は、この判定手段の判定に従って、探索を制御する。
【００９０】
（動作フロー）
図１１は、本発明の主要動作のフローチャートである。
この図を用いて、評価式を使用した演算処理の具体的な手順を説明する。まず、図のステップＳ５１では、原材料枚数の組み合わせを選択する。次に、ステップＳ５２で、上記の制約条件式を用いた制約条件の設定をする。ステップＳ５３では、初期条件の設定をする。この初期条件とは、ピボット演算の開始時の条件のことで、例えば、費用係数を全てゼロに設定する。ステップＳ５４でシンプレックス演算処理を起動する。ステップＳ５５では、ピボット演算を実行する。ピボット演算を繰り返してステップＳ５６で、実行可能解の出力をする。ステップＳ５７では、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから処理を終了する。ノーのときはステップＳ５８の処理に移行する。
【００９１】
ステップＳ５８では、ピボット演算の終了かどうかという判断をする。これは、既に説明したように、実行可能解が無いと判断された場合である。この判断の結果がイエスのときは最初のステップＳ５１の処理に移行し、制約条件の再設定を行う。ノーのときはステップＳ５９の処理に移行する。ステップＳ５９では、非整数解を評価式に当てはめる演算処理をする。ステップＳ５９〜６１の演算は判定手段３１（図１）が実行する。ステップＳ６０では、評価式の値の履歴を比較して判定をする。即ち、例えば、前回の非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。また、数回連続して得られた非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。ステップＳ６１では、既に説明したような判定基準を使用して、ピボット演算を続行するかどうかという判断をする。この判断の結果がイエスのときはステップＳ５６の処理に移行して、ステップＳ５６〜６１を繰り返す。一方、ノーのときはステップＳ６２の処理に移行して、費用係数の変更をする。そして、ステップＳ５４に戻る。即ち、新たな初期条件で、ピボット演算を再開する。
【００９２】
図１２は、割付対象製品と使用する材料の具体例説明図である。
以下の具体例では、この図に示すように、２５枚の製品を割付対象製品とする。
ベクトル表示を簡単にするため、縦長と横長が同一の製品にも、それぞれ別々の製品番号を付した。原材料は、横長は同一で縦長が異なる２種類を用意した。長さは、０．１ｍｍ単位で表示した。従って、「８２２０」は８２２ｍｍのことである。歩留計算では、原材料の価格は面積に比例するものとした。即ち、歩留が高いほど製品のコストが安価になる。面積値を「円」と読み替えるものとする。
【００９３】
なお、面材については、板取りをしたときに、木目の方向が問題になる場合がある。即ち、製品の木目の方向が特定されている場合と、木目の方向は自由で、９０度回転させても良い場合がある。この例では、製品の90度回転はできないものとした。即ち、原材料と製品の、横長、縦長は、それぞれ要求される向きにしたときのものである。原材料を切断するときの刃物厚は０ｍｍとする。また、原材料は全面にわたり全く傷みが無くて、寸法どおり使用できるものとする。
【００９４】
図１３と図１４は、製品と割付けパターンベクトルの説明図である。図１３は初期実行可能解を含む１〜１５の割付けパターンベクトルを示し、図１４は、２２６９８種類の割付けパターンベクトルである。最上部の数字は各割付けパターンベクトルを区別するためのものである。この表には、スペースの関係で、各製品の製品番号のみを表示した。各製品の横長と縦長は図１２に示したとおりである。図１２の１〜７の部分がＦＦ法により得た初期実行可能解である。
【００９５】
図１５は、到達した実行可能解の説明図である。
図１３と図１４のデータを使用して、シンプレックス演算処理手段２９によるピボット操作を繰り返す。最初から数えて６１４９回繰り返して、図１５に示すような実行可能解が得られた。即ち、図１３と図１４に示した割付けパターンベクトルのうちの、「１４」「２５８６」「５３９２」「７５１６」「８０１８」のものを組み合わせると、５枚の材料から２５種類の製品をそれぞれ一枚ずつ切り出すことができるという解が得られた。
【００９６】
ＦＦ法による初期実行可能解は、図１３に示すように、「１」〜「７」の７枚の材料から２５種類の製品をそれぞれ一枚ずつ切り出すことができるというものであった。従って、図１５と比較したとき、歩留が大幅に改善された解が得られたことが分かる。
【００９７】
図１６は、非整数解の説明図である。
ピボット操作を最初から数えて２５６回目に、図１６に示すような非整数解が得られた。左側の枠に囲まれたものは、割付けパターンベクトルである。この枠の最上部が、使用枚数ベクトルｘの要素である。即ち、０．５とあるのは、該当する原材料を０．５枚使用するということである。これが非整数解である。
【００９８】
右側の枠に囲まれたものは、Ａｘの要素である。非整数解でも製品枚数としては１枚以上得ることを表すが（Ａｘ≧ｂが成立）、非整数解の意味は製品を分断して切り出し、合わせれば元の製品と同形状になることである。
【００９９】
このような演算処理の過程で、Σｆ（ｘｉ）を計算する。そして、評価式による値が増加し続けた場合には、ピボット演算を繰り返す。その結果、上記の６１４９回目で整数解を得ることができた。
【０１００】
図１７は、非整数解と整数解の比較例説明図である。
図１７に示すように、図１６の非整数解について目的関数値の計算をすると、その値が「３１０００００」という結果が得られた。このレベルの値が得られるであろうと予測して、ピボット演算を繰り返し、図１７の整数解を得た。その目的関数値の計算結果は、上記と同様の「３１０００００」であった。演算処理時間の関係で、ピボット演算の繰り返し回数に上限を設けて、この結果を最適値とし、演算処理を終了するとよい。
【実施例２】
【０１０１】
図１８は、歩留改善効果の説明図である。図１９は部材加工装置のブロック図である。
面材では、部材割付データ５３に、切断手順を含めなければならない。この具体例では、始めに、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行した。また、常にまず原材料の左下隅に製品を割付け、図７で説明したとおり、製品の辺に平行な線で原材料を切断し、残材に残りの製品を割付けるという方法を採用した。従って、上記の最適値を得た割付け結果についても、同様の手順を実行して、全ての製品の切断が可能なとき、カッティング手順データを生成する。カッティング手順データは、ＮＣデータのような形式のものでよい。また、作業手順書は、後で説明する図２０以下の板取図を印刷したものが適する。
【０１０２】
以上の処理により、カッティング手順データが得られた。これは、プレカット工場でプレカット装置１７に供給される。原材料は図１４に示した順に選択されて、対応する割付パターンで切り分けられ、製品が得られる。この実施例では、図１８に示すように、製品の回転が不可な場合に、初期実行可能解の場合の歩留５９．５％を、改善により７８．６％にすることができた。また、回転が可能な場合には、初期実行可能解の場合の歩留７８．６％を、改善により８７．１％にすることができた。
【０１０３】
図２０〜図２６は、ＦＦ法による割付け結果を示す。図２７〜図３１は実施例の処理による割付け結果を示す。図３２〜図３６は、製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。図３７〜図４０は製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【０１０４】
図２０〜２６に示すように、ＦＦ法により割付けたときには、原材料番号が１番のものを５枚、２番のものを２枚使用し、合計７枚の原材料を使用した。図２７〜３１に示すように、実施例の方法では、原材料番号が１番のものを４枚、２番のものを１枚使用し、合計５枚の原材料を使用した。一方、製品の縦横が９０度回転可能な場合には、図３２〜図３６に示すように、ＦＦ法で原材料番号が１番のものの使用が１枚減った。実施例では、図３７〜図４０に示すように、原材料番号が２番のものの使用が１枚減った。いずれの場合も、上記の手順でプレカットが可能なことが確認できた。
【０１０５】
大量の原材料に大量の製品を割り付けて切り出すプレカット工場では、このような歩留改善ができたことにより額のコストダウンが可能になる。また、廃棄物量を減少させることができれば、廃棄物処理のための設備や費用も節約することができる。上記の例では、原材料の種類や要求される製品の種類や量を単純化したが、多種多様の原材料と製品とを取り扱えばさらに従来法では到達できなかったレベルまで大幅な歩留の改善を見込むことができる。
【実施例３】
【０１０６】
なお、使用原材料面積の総和の最小値を求めるために、最初に、第１制約条件式と第３制約条件式の制約条件の下でシンプレックス演算処理を実行した。このとき、非整数解を伴う実行可能解が得られたら、そのときの目的関数値を使用原材料面積の総和の最小値に設定した。しかしながら、上記のように、同一制約条件の下で、非整数解が複数回得られることがある。そこで、別の新たな非整数解が得られる可能性があり、原材料の枚数を組み合わせて、その目的関数値と等しくなる組合せがある限り、その制約条件下で、シンプレックス演算処理を繰り返すことが好ましい。
【０１０７】
上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組合せて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。
【符号の説明】
【０１０８】
１０ 部材割付システム
１２ コンピュータ
１４ ネットワーク
１６ 端末装置
２０ 演算処理装置
２１ 製品設定手段
２２ 原材料設定手段
２３ 初期設定手段
２４ 割付パターンベクトル生成手段
２５ 割付パターン行列生成手段
２６ 制約条件生成手段
２７ 費用計数係数ベクトル生成手段
２８ 目的関数生成手段
２９ シンプレックス演算処理手段
３０ 探索制御手段
３１ 判定手段
３２ ２次元モデル条件生成手段
４０ 記憶装置
４１ 製品ベクトルwp、hp、sp
４２ 製品要求数量ベクトルｂ
４３ 原材料ベクトルwm、hm、sm
４４ 初期実行可能解
４５ 原材料使用予定数量ベクトルｄ
４６ 割付パターン行列
４６ａ 割付パターンベクトル
４７ 原材料使用行列Ｃ
４８ 第１制約条件式
４９ 第２制約条件式
５０ 第３制約条件式
５１ 目的関数
５２ 組合せリスト
５３ 部材割付データ
５４ 評価式
５５ カッティング手順データ
【技術分野】
【０００１】
本発明は、面材の板取りを最適化するための、部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置に関する。
【背景技術】
【０００２】
住宅構造材のプレカットには、断面形状や樹種，等級、レイヤといった仕様ごとに数種類の長さ３〜６メートルの原材料が用意される。そこから求められる寸法の部材(製品)を切り出す。製品の仕様と、製品の寸法と、切り出される原材料の組合せにより、原材料から切り落とされて無駄になる部分の量が異なる。実際に、１％の歩留向上により多量の廃棄物減量を図ることができる。柱や一定の幅の板といった線状材料については、シンプレックス演算処理を利用し、山登り法、ランダムリスタート法、焼き鈍し法等により、歩留あるいは費用を最小にするための最適値を探索する技術が開発された（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−９８９２４号
【特許文献２】特許３０７９１８９号公報
【特許文献３】特許３４４１４２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の特許文献１に記載された方法は、予め既存の方法で求めた初期実行可能解を起点にして、さらに何パーセントかの歩留向上を図るために、所定の演算処理を実行する。種々の縦横寸法を持つ製品（面材）を原材料（面材）から切り出す場合にも、特許文献１に記載の技術が利用できる。その場合に、初期実行可能解を求めるには、特許文献２、３等に記載された技術が利用できる。しかしながら、特許文献１の方法を面材の切り出しに適用するためには、１次元の計算を２次元に拡張するため、面材固有のパラメータを選択して、それらを有効に使用する手法の開発が必要になる。また、面材を縦横に切断するため、製品と原材料との最適な組み合わせを求めただけでは、具体的な板取りが分からない。具体的なプレカット作業のための指示書を作成するために、演算処理の最終段階で、板取りや切断順を明示しなければならない。
【０００５】
本発明は、以上の課題を解決するためになされたもので、面材を高い歩留で原材料から切り出すための部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件wpi+wpj≦wmlまたはhpi+hpj≦hmlと、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、
前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶する初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【０００７】
〈構成２〉
構成１に記載の部材割付システムにおいて、前記第１制約条件式と第３制約条件式の制約条件の下で、または前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の下で、前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、複数の解が存在するとき、予め定めた判定手段で、別の解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
【０００８】
〈構成３〉
構成２に記載の部材割付システムにおいて、前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【０００９】
〈構成４〉
構成２に記載の部材割付システムにおいて、前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【００１０】
〈構成５〉
構成３乃至４に記載の部材割付システムにおいて、順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
【００１１】
〈構成６〉
構成５に記載の部材割付システムにおいて、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
【００１２】
〈構成７〉
構成１乃至６のいずれかに記載の部材割付システムにおいて、前記探索制御手段は、前記シンプレックス演算手段に演算処理を依頼するという動作の繰り返し回数に上限を設けたことを特徴とする部材割付システム。
【００１３】
〈構成８〉
構成１乃至７のいずれかに記載の部材割付システムにおいて、前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする部材割付システム。
【００１４】
〈構成９〉
構成１乃至８に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【００１５】
〈構成１０〉
構成９に記載の部材加工装置において、前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶しておき、前記判定結果を使用して、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成して出力することを特徴とする部材加工装置。
【００１６】
〈構成１１〉
コンピュータを、構成１乃至８に記載の各手段として機能させる部材割付プログラム。
【００１７】
〈構成１２〉
コンピュータを、構成１乃至８に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【００１８】
〈構成１３〉
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品設定手段が、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料設定手段が、用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させるステップと、
２次元モデル条件生成手段が、割付け製品の面積は
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hmlと、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶するステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【発明の効果】
【００１９】
面材について、シンプレックス演算処理を利用して、歩留の改善を図り、具体的な板取りを含めたプレカット作業のための切断手順を含む指示書を作成する
ることができる。
【図面の簡単な説明】
【００２０】
【図１】実施例１の部材割付システム１０のブロック図である。
【図２】部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
【図３】演算処理のパラメータを説明するための説明図である。
【図４】初回のシンプレックス演算処理動作フローチャートである。
【図５】１回目のシンプレックス演算終了後の演算処理のフローチャートである。
【図６】割付パターンベクトルの説明図である。
【図７】予め定めた割付け方法の説明図である。
【図８】ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
【図９】ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
【図１０】評価式の意味の説明図である。
【図１１】本発明の主要動作のフローチャートである。
【図１２】割付対象製品と使用する材料の具体例説明図である。
【図１３】初期実行可能解を含む１〜１５の割付けパターンベクトルの説明図である。
【図１４】２２６９８種類の割付けパターンベクトルの説明図である。
【図１５】到達した実行可能解の説明図である。
【図１６】非整数解の説明図である。
【図１７】非整数解と整数解の比較例説明図である。
【図１８】歩留改善効果の説明図である。
【図１９】部材加工装置のブロック図である。
【図２０】ＦＦ法による割付け結果を示す。
【図２１】ＦＦ法による割付け結果を示す。
【図２２】ＦＦ法による割付け結果を示す。
【図２３】ＦＦ法による割付け結果を示す。
【図２４】ＦＦ法による割付け結果を示す。
【図２５】ＦＦ法による割付け結果を示す。
【図２６】ＦＦ法による割付け結果を示す。
【図２７】実施例２の処理による割付け結果を示す。
【図２８】実施例２の処理による割付け結果を示す。
【図２９】実施例２の処理による割付け結果を示す。
【図３０】実施例２の処理による割付け結果を示す。
【図３１】実施例２の処理による割付け結果を示す。
【図３２】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３３】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３４】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３５】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３６】製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。
【図３７】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図３８】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図３９】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【図４０】製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【発明を実施するための形態】
【００２１】
本発明では、既存の任意の方法で得られた実用性のある解を基礎にして、それをシンプレックス法で評価し、さらに改善した解を求める。シンプレックス法は、線形計画問題の最適解を探索する方法として知られている。しかし、求められた製品の寸法の種類や原材料の種類が数十種類にも及ぶと、組合せの数は数十万組を越えることがある。ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付ける、といった条件に基づいてそのまま演算処理のためのパラメータを作ると、最適値探索のためのシンプレックス演算処理に時間がかかりすぎるおそれがある。そこで、本発明では、シンプレックス法による演算処理のための制約条件を付加して、比較対象範囲の絞り込みをしながら、効率よく計算をする。そして、シンプレックス法によるピボット演算処理の過程で実行可能解が得られたときに、所定の評価式を使用してその後の見通しをたてる。その結果に応じて探索条件を変更し、無駄な演算処理を回避する。従って、探索のための演算処理時間を大幅に短縮できる。以下、本発明の実施の形態を実施例ごとに詳細に説明する。
【実施例１】
【００２２】
図１は実施例１の部材割付システム１０のブロック図である。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、面材をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献３に記載されたとおりのものを使用することができる。
【００２３】
コンピュータ１２には、演算処理装置２０と記憶装置４０とが設けられている。演算処理装置２０には、図のように、製品設定手段２１、原材料設定手段２２、初期設定手段２３、割付パターンベクトル生成手段２４、割付パターン行列生成手段２５、制約条件生成手段２６、費用係数ベクトル生成手段２７、目的関数生成手段２８、シンプレックス演算処理手段２９、探索制御手段３０、及び判定手段３１等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。
【００２４】
記憶装置４０には、図のように、製品横長ベクトル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と、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置４０に記憶させる。
【００５８】
ステップＳ１３では、初期設定手段２３が
２次元モデル条件を満たすと判定された 初期実行可能解４４の入力を受け付ける。その結果は 記憶装置４０に記憶される。ステップＳ１４では、割付パターンベクトル生成手段２４が、割付パターンベクトルの生成をする。割付パターンベクトルは、記憶装置４０に記憶される。続いて、ステップＳ１５で、割付パターン行列生成手段２５が割付パターン行列４６の生成をして、記憶装置４０に記憶させる。次に、ステップＳ１６で、制約条件生成手段２６が、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０を生成して、記憶装置４０に記憶させる。
【００５９】
ステップＳ１７では、費用係数ベクトル生成手段２７が費用係数ベクトルの生成をし、ステップＳ１８では、目的関数生成手段２８がその費用係数ベクトルを使用して目的関数５１の設定をする。その結果が記憶装置４０に記憶される。次に探索制御手段３０が、ステップＳ１９で、後で説明するように最初の演算用パラメータをシンプレックス演算処理手段２９に入力する。ステップＳ２０では、この演算用パラメータを使用したシンプレックス演算を実行する。解が得られたら探索制御手段３０は、ステップＳ２１で、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから、ステップＳ２３で部材割付データとカッティング手順データを出力して処理を終了する。ノーのときはステップＳ２２の処理に移行する。ステップＳ２２では、探索制御手段３０が、図５に示した手順で、シンプレックス法による演算を制御する。
【００６０】
図５は、１回目のシンプレックス演算終了後の演算処理のフローチャートである。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数値の範囲で、原材料の組合せリストの生成をする。その結果を目的関数値の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、後で説明するように制約条件の設定をする。
【００６１】
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ピボット演算処理を繰り返したかどうか判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。本発明では、上記のステップＳ３７における探索動作に後で説明するような特殊な制御を行う。
【００６２】
図６から図１１までは、具体的な計算例の説明図である。
（原材料データ）
例えば、用意された原材料は５種類で、原材料名をＧＧ１〜ＧＧ５とする。
（製品データ）
求められている製品は７枚で、その製品名をＳＳ１〜ＳＳ７とする。
【００６３】
（割付パターンベクトル）
図６は、割付パターンベクトルの説明図である。
図の最も左側の上から下に向かう縦１列に、上記の７種類の製品名が列挙されている。また、最も上段の左から右に向かう横１列に、原材料名が列挙されている。各原材料名の下の縦一列が、それぞれ割付パターンベクトルである。例えば、原材料名ＧＧ１ものには、製品名がＳＳ２のものを１枚割り付けることができるとする。例えば、原材料名がＧＧ２のものには、製品名がＳＳ３とＳＳ６のものを各１枚割り付けることができるとする。この表には、この要領で、７枚の製品の寸法と５種類の原材料の寸法とを比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品との関係を示す７次の割付パターンベクトルを列挙する。ここで、ｘ１〜ｘ５は初期実行可能解から得られた割付パターンベクトルである。以下は、特許文献１に記載したとおりの手順で、この表を展開し、原材料の使用枚数ベクトルｘを求める。
【００６４】
（目的関数）
説明を簡略化するために、費用係数ベクトルｆの各要素を原材料面積と一致させる。
すなわち、面積の数値をそのまま円と読み替える。
図６の原材料名の部分を原材料の面積で表示すると、それらの数値は費用係数ベクトルｆの要素である。従って、最初のシンプレックス演算処理で、初期値として入力する実行可能解の目的関数Σ（ｆｉ・ｘｉ）の値は、ｘ１〜ｘ５の使用原材料の面積の総和である。以下の計算ではこれを改善する解を求めるのだから、目的関数値の上限値をこのとき求めた総和に定める。
【００６５】
本発明では、シンプレックス演算による解が得られたときの目的関数値を、最適値の下限値に設定する。即ち、初期実行可能解を改善することを目的とするから、目的関数値の初期値を最大値に設定し、最初のシンプレックス演算処理により得られた目的関数値を最小値に設定する。この範囲に最適値があるとし、再度探索をする。ここで、原材料を任意の枚数だけ組合せて、目的関数値がこの範囲にある場合を列挙する。例えば、組合せを選択しながら集計する演算処理結果を昇順にソートすればよい。
【００６６】
具体的なシンプレックス演算処理については、特許文献１に記載されたとおりであるから、その説明を省略する。こうして、原材料を節約できる割付パターンを見つけて、その結果を、部材割付データとして出力し、端末装置に送信する。
なお、２次元モデルについては、使用する原材料と各原材料から切り出す製品を特定したデータだけをプレカット装置に送っても、そのままではプレカット制御できない。初期実行可能解を求めるときにした、２次元モデル条件を満たすかどうかの判定処理において、予め定めた割付け方法で割付け可能かどうかの判定をした。この判定では、具体的に製品の割付け位置と原材料の切断位置と切断順とを確認する。その結果が記憶装置４０に記憶されている。
【００６７】
図７は、予め定めた割付け方法の説明図である。
予め定めた割付け方法は、例えば、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法（ＦＦ法）で割付けを実行する。その後、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、同様にファーストフィット法で割付けを実行し、さらに、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する。この全てを実行して、最適な割付け方法を見付ければよい。
【００６８】
その過程では、例えば、図７において、ある原材料５６の隅に製品５７を割付けたとする。このとき、製品５７のいずれかの辺を通る切断線５８で、原材料を切断する。切断後の原材料片を、製品５７の残りの辺を通る切断線５９で切断する。こうして残った原材料片６０と６１に、他の製品を割付けられるかどうか判断し、割付けられなかったら、廃材とする。この手順で割付けを行うと、製品の割付け位置と原材料の切断位置と切断順とが自動的に確定する。これを実行可能解の生成とともに、あるいは、２次元モデル条件を満たすかどうかの判定処理中に判定結果６４として、記憶装置４０に記憶させる。その判定結果６４を読み出して、カッティング手順データ５４を生成するとよい。このデータはそのままプレカット装置を制御できる。また、作業手順書を印刷して、作業者に手渡し、手動でのプレカットが可能になる。
【００６９】
（ＦＦ法）
図８と図９は、ＦＦ法による原材料種類が複数の面材の割付処理動作フローチャートである。
ファーストフィット法（ＦＦ法）を用いて、面材の割付をする場合には、例えば、図に示すように、面積の広いものから順に割付をする。即ち、まず、最初のステップＳ１１で、原材料を面積降順に並べて読み出し順のリストを作成し記憶装置に格納する。ステップＳ１２では、製品を面積降順に並べて読み出し順のリストを作成し記憶装置に格納する。その後ステップＳ３からステップＳ１９の処理を繰り返す。
【００７０】
ステップＳ１３では、読み出し順のリストに従って、原材料を一枚選択する。ステップＳ１４で、この原材料に製品の割付試行処理をする。ステップＳ１４の処理の具体的な内容は後から図９を用いて説明する。ステップＳ１３で選択した一枚の原材料に対して、最も歩留の良い製品の割付けがステップＳ１４で見つかったら、ステップＳ１５で歩留の算出をする。
【００７１】
ステップＳ１６では、全ての原材料を選択し終わったかどうかという判断をする。この判断の結果がイエスのときはステップＳ１７の処理に移行し、ノーのときはステップＳ１３の処理に戻る。即ち、全ての種類の原材料について、ステップＳ１３からステップＳ１６の処理を繰り返す。全ての原材料についての処理が終了すると、ステップＳ１７でこれまでの計算結果を比較し、最大歩留の割付けを見付けて、一組の材料と製品の組み合わせを決め、これを採用する。
【００７２】
ステップＳ１８では、ステップＳ１７で組み合わせの決まった割付済の製品を、読み出し順のリストから削除する。ステップＳ１９では、全ての製品について、割付け処理が終了したかどうかという判断をする。この判断の結果がイエスのときはステップＳ２０の処理に移行し、ノーのときはステップＳ１３の処理に戻る。こうして、ステップＳ１３からステップＳ１９の
処理を繰り返して、全ての製品をいずれかの材料に割り付ける。これが終了するとステップＳ２０で総歩留の計算をする。こうして、ＦＦ法による割付処理が終了する。
【００７３】
図９は、原材料に製品の割付試行処理をするための動作フローチャートである。
まず、ステップ２１で製品の読み出し順リストに未割付の製品があるかを判断する。イエスのときはステップＳ２２の処理に移行し、ノーのときは処理を終了し、図８のステップＳ１５へ移行する。 ステップＳ２２では製品を読み出し順リストにしたがって一枚選択する。ステップＳ２３では選択した製品が原材料または残材に割付可能かどうかという判断をする。
【００７４】
最初は原材料が割付対象になり、２回目以降は残材が割付対象になる。ステップＳ２３の判断は選択した製品が原材料または残材の隅に割付可能かどうかである。イエスのときはステップＳ２４に移行し、ノーのときはステップＳ２１に移行する。ステップＳ２４では選択した製品を原材料または残材の隅に割付する。原材料も残材も長方形（正方形含む）だから四隅のいずれかに割付する。 ステップＳ２５ではギロチンカット（刃物を途中で止めない）で製品部と残材部に分割する。そしてステップＳ２１に移行する。これを一枚の原材料への割付が終了するまで繰返し、終了したら図８のステップＳ１５へ移行する。
【００７５】
（割付パターンベクトル生成）
最適解を得るために、総当り的に重複をせずすべての割付パターンを自動的に生成することは、例えばバックトラック法を利用すれば可能である。しかしそれでは、
図１２に示す２５枚の製品を２種類の原材料に割付ける場合を例にしても、その割付パターンの数は組合せ爆発を起こす。
【００７６】
これを避けるためシンプレックス乗数を用いた感度解析手法を前記２次元モデル条件に加えて割付パターンベクトル生成時に割付パターンベクトルの数を総当り相当を担保しながら合理的に絞り込むようにしてもよい。これは演算時間の大幅短縮に寄与する。
【００７７】
（評価式）
また、シンプレックス演算処理手段２９は、制約条件を満たす割付けパターンベクトルの組み合わせを、既知のシンプレックスタブローを使用したピボット演算により、探索する。使用する原材料の組み合わせが一定という制約条件を与えると、シンプレックス演算処理手段２９は、割付けパターンベクトルの組み合わせを少しずつ変更しながら、ｘの値が制約条件を満たす実行可能解を見付ける。このピボット演算の過程で得られる非整数解の出現順に規則性はない。ピボット演算開始時の初期条件が異なると、全く異なる過程でピボット演算が実行され、非整数解の出現順も変わる。最短時間で整数解に到達する最適な初期条件を見付ける方法は無い。運の悪いときには何万回ピボット演算を繰り返しても整数解が得られないことがある。
【００７８】
整数解が得られる前に、複数の非整数解が得られることもある。多数の非整数解が得られても、最後まで整数解が得られないこともある。最後まで整数解が得られなかったときは、条件設定をした原材料の組み合わせで最適解は無いということである。最後までピボット演算を繰り返すことは実用上の計算時間を考慮すれば不合理であるので、ピボット演算の繰り返し回数がＷ回に達したときに探索を打ち切って、別の原材料の組み合わせを選択するようにしてもよい。しかしながら、非整数解が出力されたときのシンプレックスタブローから得られる相対費用係数を監視すると、探索方針を決めることができる。相対費用係数が全部正の数になったときには、これ以上、実行可能解は無いと判断してよい。また、相対費用係数に一つでも０（ゼロ）が含まれていれば、実行可能解が他にもあると判断できる。従って、探索を続行するとよい。
【００７９】
しかしながら、前記割付パターンベクトル生成合理化を図っても、なお、割付けパターンベクトルの数が多い場合や、原材料の組み合わせの種類が多い場合には、シンプレックス演算処理手段２９による演算処理時間が膨大になるおそれがある。そこで、本発明では、複数の非整数解が得られたときに、以下に定義する評価式を用いて、その後の演算処理の結果を予測する。即ち、ピボット演算処理の結果、複数の非整数解が得られたとき、これらの非整数解を特定の評価式を適用して比較し、一定の判定基準を満たす場合にはピボット演算処理を続行する。判定基準を満たさない場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開する。また、あるいは、同一制約条件での演算処理を中止し、別の原材料の組み合わせを制約条件に設定する。
【００８０】
図１に示した評価式５４は、Σｆ（ｘｉ）と定義したデータである。Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最大値が一定値になる関数である。例えば、ｆ（ｘｉ）はｘｉのｎ乗（ｎ＞１）と定義することができる。また、あるいは、Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最小値が一定値になる関数である。例えば、ｆ（ｘｉ）はｓｉｎπｘｉとか、あるいは、ｆ（ｘｉ）はｘｉのｎ乗（０＜ｎ＜１）というように定義することができる。
【００８１】
図１０は、評価式の意味の説明図である。
ｆ（ｘｉ）をｘｉの２乗と定義して、評価式の意味を説明する。この評価式は、複数の非整数解が得られたときに、原材料の使用枚数ベクトルｘの要素ｘiの値の変化を観察するためのものである。即ち、それぞれの解に含まれる全てのｘiが整数に近づく方向にピボット演算が進んでいるかを判定することができる。概略的には、次のような理論になる。
【００８２】
例えば、使用枚数ｘ＝（ｘ１、ｘ２）とする。また、原材料の組み合わせＣを（１、１）とする。前者は列ベクトル、後者は行ベクトルである。（Cｘ＝ｄ）だから、ｘ１＋ｘ２＝１である。この場合、図１０（ａ）に示すように、ｘ１軸とｘ２軸の直交座標上で、ｘ１軸の切辺の座標が１でｘ２軸の切辺の座標が１の直線上に実行可能解があるということができる。直線の両端の白丸は整数解、中央の黒丸は非整数解になる。（ｂ）には、縦軸に評価式の値を示し、横軸にｘ１とｘ２の値を示した。
【００８３】
図１０の（ｂ）に示したのは使用枚数ベクトルｘの要素がｘ１とｘ２の場合の解空間である。評価式の最大値は１、最小値は０．５である。ベクトルｘの要素数が増えると解空間はこの図よりもさらに複雑になる。しかも、ピボット演算により求められる非整数解や整数解の出力順序も複雑である。従って、ある条件でピボット演算を開始して、順番に出力される実行可能解により得られる整数解あるいは非整数解の評価式の値は、図１０（ｃ）に示すように変遷する。黒丸が非整数解によるもので、白丸が整数解によるものである。
【００８４】
ここで、例えば、シンプレックス演算処理手段２９による演算処理が開始されて、所定のタイミングで、実行可能解Ｒ１が得られたとする。さらにその後、実行可能解Ｒ２が得られたとする。いずれも非整数解である。両者の評価式の値を比較すると、後から得られた非整数解の値が減少している。ここでさらにピボット演算を続行しても、評価式の値は減少していき、すぐに整数解には近づかないと判定する。そこで、このタイミングで初期条件を変更する。即ち、ピボット演算の開始点を変更する。
【００８５】
この演算処理では、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）とし、ｘiは０≦ｘi≦１とし、さらに、原材料の組み合わせが一定という制約条件（Cｘ＝ｄ）を追加して、シンプレックス演算処理手段２９を起動した。割付けパターンベクトルと制約条件は変えられない。一方、本発明の方法では、制約条件（Cｘ＝ｄ）に費用係数の値が含まれないようにし、かつ、基底変数も使用枚数ベクトルｘを使用したから、費用係数ｆiの値を変更しても解に直接影響がない。しかも、目的関数に含まれる費用係数ｆiの値を変更すると、ピボット演算の開始点や順序を変えることができる。例えば、仮に、費用係数ｆiの値を全て０にして演算処理を開始しても、費用係数ｆiの値を全て１にして、演算処理を開始しても、最終的には同じ結果が得られる。ところが、ピボット演算の過程は相異する。即ち、シンプレックス演算処理手段２９に対して、こうした変更可能な設定条件を変更することで、図１０（ｃ）の実行可能解Ｒ２が得られた時点でピボット演算を停止し、今度はタイミングｔ１からピボット演算を再開することができる場合がある。もちろん、他の任意の方法でピボット演算開始のための初期条件を変更できればよい。
【００８６】
タイミングｔ１からピボット演算を再開すると、その後、実行可能解Ｒ３が得られる。さらにその後、実行可能解Ｒ４が得られたとする。いずれも非整数解である。ここで、両者の評価式の値を比較すると、その値が増加している。このとき、さらにピボット演算を続行すれば、評価式の値は増加していき、整数解に近づく可能性が高いと判定する。こうした判断を、図１に示した判定手段３１が実行する。図１０（ｃ）の例では、その後無事に白丸で示した整数解に到達することができる。
【００８７】
しかしながら、実際には、同じ設定条件で演算処理を続行しても、必ず整数解が得られるとは限らない。従って、例えば、評価式の値が増加した後に整数解が得られないまま減少し始めたら、極大値を通過したものと判断して、別の上昇曲線を求めて設定条件を変更するとよい。例えば、費用係数ｆiの値を全て０の状態から全て１の状態まで順番に切り替えて、ピボット演算を繰り返せばよい。
【００８８】
以上の処理により、複数の非整数解が得られたときに、その後ピボット演算を続行しても良い結果が得られないと判断したら、その状態を回避し、別の条件からピボット演算を開始するようにして、演算処理時間を短縮することができる。また、例えば、初期条件を変更しても評価式の値が増加する傾向がみられない場合には、この制約条件での整数解は無いと判断して、原材料の組み合わせの制約条件（Cｘ＝ｄ）を変更して、演算処理を再開するとよい。
【００８９】
評価式の値が増加していく場合にのみピボット演算を続行するのは、既知の局所探索法でいう山登り法と呼ぶことができる。そして、ランダムに初期条件を変更するのをランダムリスタート法と呼ぶことができる。さらに、上記の評価式を利用して、既知の焼き鈍し法により、整数解を探索することができる。また、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときピボット演算を続行する方法も有効である。以上のように判定基準を定めて、図１に示した判定手段３１が、ピボット演算を続行するかどうかの判定をする。図１に示した探索制御手段３０は、この判定手段の判定に従って、探索を制御する。
【００９０】
（動作フロー）
図１１は、本発明の主要動作のフローチャートである。
この図を用いて、評価式を使用した演算処理の具体的な手順を説明する。まず、図のステップＳ５１では、原材料枚数の組み合わせを選択する。次に、ステップＳ５２で、上記の制約条件式を用いた制約条件の設定をする。ステップＳ５３では、初期条件の設定をする。この初期条件とは、ピボット演算の開始時の条件のことで、例えば、費用係数を全てゼロに設定する。ステップＳ５４でシンプレックス演算処理を起動する。ステップＳ５５では、ピボット演算を実行する。ピボット演算を繰り返してステップＳ５６で、実行可能解の出力をする。ステップＳ５７では、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから処理を終了する。ノーのときはステップＳ５８の処理に移行する。
【００９１】
ステップＳ５８では、ピボット演算の終了かどうかという判断をする。これは、既に説明したように、実行可能解が無いと判断された場合である。この判断の結果がイエスのときは最初のステップＳ５１の処理に移行し、制約条件の再設定を行う。ノーのときはステップＳ５９の処理に移行する。ステップＳ５９では、非整数解を評価式に当てはめる演算処理をする。ステップＳ５９〜６１の演算は判定手段３１（図１）が実行する。ステップＳ６０では、評価式の値の履歴を比較して判定をする。即ち、例えば、前回の非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。また、数回連続して得られた非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。ステップＳ６１では、既に説明したような判定基準を使用して、ピボット演算を続行するかどうかという判断をする。この判断の結果がイエスのときはステップＳ５６の処理に移行して、ステップＳ５６〜６１を繰り返す。一方、ノーのときはステップＳ６２の処理に移行して、費用係数の変更をする。そして、ステップＳ５４に戻る。即ち、新たな初期条件で、ピボット演算を再開する。
【００９２】
図１２は、割付対象製品と使用する材料の具体例説明図である。
以下の具体例では、この図に示すように、２５枚の製品を割付対象製品とする。
ベクトル表示を簡単にするため、縦長と横長が同一の製品にも、それぞれ別々の製品番号を付した。原材料は、横長は同一で縦長が異なる２種類を用意した。長さは、０．１ｍｍ単位で表示した。従って、「８２２０」は８２２ｍｍのことである。歩留計算では、原材料の価格は面積に比例するものとした。即ち、歩留が高いほど製品のコストが安価になる。面積値を「円」と読み替えるものとする。
【００９３】
なお、面材については、板取りをしたときに、木目の方向が問題になる場合がある。即ち、製品の木目の方向が特定されている場合と、木目の方向は自由で、９０度回転させても良い場合がある。この例では、製品の90度回転はできないものとした。即ち、原材料と製品の、横長、縦長は、それぞれ要求される向きにしたときのものである。原材料を切断するときの刃物厚は０ｍｍとする。また、原材料は全面にわたり全く傷みが無くて、寸法どおり使用できるものとする。
【００９４】
図１３と図１４は、製品と割付けパターンベクトルの説明図である。図１３は初期実行可能解を含む１〜１５の割付けパターンベクトルを示し、図１４は、２２６９８種類の割付けパターンベクトルである。最上部の数字は各割付けパターンベクトルを区別するためのものである。この表には、スペースの関係で、各製品の製品番号のみを表示した。各製品の横長と縦長は図１２に示したとおりである。図１２の１〜７の部分がＦＦ法により得た初期実行可能解である。
【００９５】
図１５は、到達した実行可能解の説明図である。
図１３と図１４のデータを使用して、シンプレックス演算処理手段２９によるピボット操作を繰り返す。最初から数えて６１４９回繰り返して、図１５に示すような実行可能解が得られた。即ち、図１３と図１４に示した割付けパターンベクトルのうちの、「１４」「２５８６」「５３９２」「７５１６」「８０１８」のものを組み合わせると、５枚の材料から２５種類の製品をそれぞれ一枚ずつ切り出すことができるという解が得られた。
【００９６】
ＦＦ法による初期実行可能解は、図１３に示すように、「１」〜「７」の７枚の材料から２５種類の製品をそれぞれ一枚ずつ切り出すことができるというものであった。従って、図１５と比較したとき、歩留が大幅に改善された解が得られたことが分かる。
【００９７】
図１６は、非整数解の説明図である。
ピボット操作を最初から数えて２５６回目に、図１６に示すような非整数解が得られた。左側の枠に囲まれたものは、割付けパターンベクトルである。この枠の最上部が、使用枚数ベクトルｘの要素である。即ち、０．５とあるのは、該当する原材料を０．５枚使用するということである。これが非整数解である。
【００９８】
右側の枠に囲まれたものは、Ａｘの要素である。非整数解でも製品枚数としては１枚以上得ることを表すが（Ａｘ≧ｂが成立）、非整数解の意味は製品を分断して切り出し、合わせれば元の製品と同形状になることである。
【００９９】
このような演算処理の過程で、Σｆ（ｘｉ）を計算する。そして、評価式による値が増加し続けた場合には、ピボット演算を繰り返す。その結果、上記の６１４９回目で整数解を得ることができた。
【０１００】
図１７は、非整数解と整数解の比較例説明図である。
図１７に示すように、図１６の非整数解について目的関数値の計算をすると、その値が「３１０００００」という結果が得られた。このレベルの値が得られるであろうと予測して、ピボット演算を繰り返し、図１７の整数解を得た。その目的関数値の計算結果は、上記と同様の「３１０００００」であった。演算処理時間の関係で、ピボット演算の繰り返し回数に上限を設けて、この結果を最適値とし、演算処理を終了するとよい。
【実施例２】
【０１０１】
図１８は、歩留改善効果の説明図である。図１９は部材加工装置のブロック図である。
面材では、部材割付データ５３に、切断手順を含めなければならない。この具体例では、始めに、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行した。また、常にまず原材料の左下隅に製品を割付け、図７で説明したとおり、製品の辺に平行な線で原材料を切断し、残材に残りの製品を割付けるという方法を採用した。従って、上記の最適値を得た割付け結果についても、同様の手順を実行して、全ての製品の切断が可能なとき、カッティング手順データを生成する。カッティング手順データは、ＮＣデータのような形式のものでよい。また、作業手順書は、後で説明する図２０以下の板取図を印刷したものが適する。
【０１０２】
以上の処理により、カッティング手順データが得られた。これは、プレカット工場でプレカット装置１７に供給される。原材料は図１４に示した順に選択されて、対応する割付パターンで切り分けられ、製品が得られる。この実施例では、図１８に示すように、製品の回転が不可な場合に、初期実行可能解の場合の歩留５９．５％を、改善により７８．６％にすることができた。また、回転が可能な場合には、初期実行可能解の場合の歩留７８．６％を、改善により８７．１％にすることができた。
【０１０３】
図２０〜図２６は、ＦＦ法による割付け結果を示す。図２７〜図３１は実施例の処理による割付け結果を示す。図３２〜図３６は、製品の縦横が９０度回転可能な場合のＦＦ法による割付け結果を示す。図３７〜図４０は製品の縦横が９０度回転可能な場合の実施例の処理による割付け結果を示す。
【０１０４】
図２０〜２６に示すように、ＦＦ法により割付けたときには、原材料番号が１番のものを５枚、２番のものを２枚使用し、合計７枚の原材料を使用した。図２７〜３１に示すように、実施例の方法では、原材料番号が１番のものを４枚、２番のものを１枚使用し、合計５枚の原材料を使用した。一方、製品の縦横が９０度回転可能な場合には、図３２〜図３６に示すように、ＦＦ法で原材料番号が１番のものの使用が１枚減った。実施例では、図３７〜図４０に示すように、原材料番号が２番のものの使用が１枚減った。いずれの場合も、上記の手順でプレカットが可能なことが確認できた。
【０１０５】
大量の原材料に大量の製品を割り付けて切り出すプレカット工場では、このような歩留改善ができたことにより額のコストダウンが可能になる。また、廃棄物量を減少させることができれば、廃棄物処理のための設備や費用も節約することができる。上記の例では、原材料の種類や要求される製品の種類や量を単純化したが、多種多様の原材料と製品とを取り扱えばさらに従来法では到達できなかったレベルまで大幅な歩留の改善を見込むことができる。
【実施例３】
【０１０６】
なお、使用原材料面積の総和の最小値を求めるために、最初に、第１制約条件式と第３制約条件式の制約条件の下でシンプレックス演算処理を実行した。このとき、非整数解を伴う実行可能解が得られたら、そのときの目的関数値を使用原材料面積の総和の最小値に設定した。しかしながら、上記のように、同一制約条件の下で、非整数解が複数回得られることがある。そこで、別の新たな非整数解が得られる可能性があり、原材料の枚数を組み合わせて、その目的関数値と等しくなる組合せがある限り、その制約条件下で、シンプレックス演算処理を繰り返すことが好ましい。
【０１０７】
上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組合せて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。
【符号の説明】
【０１０８】
１０ 部材割付システム
１２ コンピュータ
１４ ネットワーク
１６ 端末装置
２０ 演算処理装置
２１ 製品設定手段
２２ 原材料設定手段
２３ 初期設定手段
２４ 割付パターンベクトル生成手段
２５ 割付パターン行列生成手段
２６ 制約条件生成手段
２７ 費用計数係数ベクトル生成手段
２８ 目的関数生成手段
２９ シンプレックス演算処理手段
３０ 探索制御手段
３１ 判定手段
３２ ２次元モデル条件生成手段
４０ 記憶装置
４１ 製品ベクトルwp、hp、sp
４２ 製品要求数量ベクトルｂ
４３ 原材料ベクトルwm、hm、sm
４４ 初期実行可能解
４５ 原材料使用予定数量ベクトルｄ
４６ 割付パターン行列
４６ａ 割付パターンベクトル
４７ 原材料使用行列Ｃ
４８ 第１制約条件式
４９ 第２制約条件式
５０ 第３制約条件式
５１ 目的関数
５２ 組合せリスト
５３ 部材割付データ
５４ 評価式
５５ カッティング手順データ
【特許請求の範囲】
【請求項１】
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、
前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製
品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶する初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【請求項２】
請求項１に記載の部材割付システムにおいて、
前記第１制約条件式と第３制約条件式の制約条件の下で、
または前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の下で、
前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、複数の解が存在するとき、予め定めた判定手段で、
別の解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
【請求項３】
請求項２に記載の部材割付システムにおいて、
前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【請求項４】
請求項２に記載の部材割付システムにおいて、
前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【請求項５】
請求項３乃至４に記載の部材割付システムにおいて、
順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
【請求項６】
請求項５に記載の部材割付システムにおいて、
非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
【請求項７】
請求項１乃至６のいずれかに記載の部材割付システムにおいて、
前記探索制御手段は、前記シンプレックス演算手段に演算処理を依頼するという動作の繰り返し回数に上限を設けたことを特徴とする部材割付システム。
【請求項８】
請求項１乃至７のいずれかに記載の部材割付システムにおいて、
前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする部材割付システム。
【請求項９】
請求項１乃至８に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【請求項１０】
請求項９に記載の部材加工装置において、
前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶しておき、前記判定結果を使用して、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成して出力することを特徴とする部材加工装置。
【請求項１１】
コンピュータを、請求項１乃至８に記載の各手段として機能させる部材割付プログラム。
【請求項１２】
コンピュータを、請求項１乃至８に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項１３】
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品設定手段が、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料設定手段が、用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させるステップと、
２次元モデル条件生成手段が、割付け製品の面積は
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶するステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【請求項１】
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品設定手段と、
用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させる原材料設定手段と、
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させる２次元モデル条件生成手段と、
求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、
前記第１評価条件と第２評価条件と第３評価条件とを含む２次元モデル条件を満たす、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製
品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させる制約条件生成手段と、
前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶する初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備えたことを特徴とする部材割付システム。
【請求項２】
請求項１に記載の部材割付システムにおいて、
前記第１制約条件式と第３制約条件式の制約条件の下で、
または前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の下で、
前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、複数の解が存在するとき、予め定めた判定手段で、
別の解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
【請求項３】
請求項２に記載の部材割付システムにおいて、
前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【請求項４】
請求項２に記載の部材割付システムにおいて、
前記予め定めた判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、判定基準を満たすと判定する手段であることを特徴とする部材割付システム。
【請求項５】
請求項３乃至４に記載の部材割付システムにおいて、
順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
【請求項６】
請求項５に記載の部材割付システムにおいて、
非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
【請求項７】
請求項１乃至６のいずれかに記載の部材割付システムにおいて、
前記探索制御手段は、前記シンプレックス演算手段に演算処理を依頼するという動作の繰り返し回数に上限を設けたことを特徴とする部材割付システム。
【請求項８】
請求項１乃至７のいずれかに記載の部材割付システムにおいて、
前記予め定めた割付け方法は、製品を横長の大きいものから順に配列し、原材料を横長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、製品を縦長の大きいものから順に配列し、原材料を縦長の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理か、もしくは、製品を面積の大きいものから順に配列し、原材料を面積の大きいものから順に配列して、ファーストフィット法で割付けを実行する処理のいずれかであることを特徴とする部材割付システム。
【請求項９】
請求項１乃至８に記載の部材割付システムから出力される部材割り付けデータを受け入れて、前記ｍ枚の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置を備えたことを特徴とする部材加工装置。
【請求項１０】
請求項９に記載の部材加工装置において、
前記２次元モデル条件を満たすかどうかの判定処理において、前記予め定めた割付け方法で割付け可能かどうかの判定結果を記憶装置に記憶しておき、前記判定結果を使用して、全ての原材料について、製品の割付け位置と原材料の切断位置と切断順とを含む、カッティング手順データを生成して出力することを特徴とする部材加工装置。
【請求項１１】
コンピュータを、請求項１乃至８に記載の各手段として機能させる部材割付プログラム。
【請求項１２】
コンピュータを、請求項１乃至８に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項１３】
それぞれ所定の長方形のｍ枚の製品を、それぞれ所定の長方形のｋ種類の原材料から切り出すときに必要な各種類の原材料の枚数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品設定手段が、求められているｍ枚の製品の横長データと縦長データの入力を受け付けて、製品の横長を要素とするｍ次の製品横長ベクトルwpと、製品の縦長を要素とするｍ次の製品縦長ベクトルhpと、製品の面積を要素とするｍ次の製品面積ベクトルspと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料設定手段が、用意されたｋ種類の長方形の原材料データの入力を受け付けて、原材料の横長を要素とするｋ次の原材料横長ベクトルwmと、原材料の縦長を要素とするｋ次の原材料縦長ベクトルhmと、原材料の面積を要素とするｋ次の原材料面積ベクトルsmと、原材料の種類番号を要素とするｋ次の原材料番号ベクトルnmとを生成し、記憶装置に記憶させるステップと、
２次元モデル条件生成手段が、割付け製品の面積は
割付け製品の面積は原材料面積ベクトルsmの要素のうちのいずれかの原材料の面積Ｓ以下であるとする第１評価条件（sp，aj）（内積）≦Sと、隣接する製品が重ならないとする第２評価条件
wpi+wpj≦wml または
hpi+hpj≦hml と、
割付パターンベクトルａｊが予め定めた割付け方法で割付け可能であるとする第３評価条件とを含む、２次元モデル条件を生成して、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ枚の製品の製品横長データと製品縦長データとを用意された前記ｋ種類の原材料の原材料横長データと原材料縦長データと比較して、１枚または複数枚の製品を経済的に割り付けることができる原材料と製品の関係を示す、ｍ次の割付パターンベクトルａｊを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、ｋ種類の原材料から任意に選択したｎ枚の原材料に対して、それぞれｍ枚の製品のうちのいずれかの製品を割り付けたとき、選択したｎ枚の原材料の使用枚数を表すために、要素がｘｉのｎ次の使用枚数ベクトルｘを定義し、
前記ｎ枚の原材料それぞれに対応するｎ次の費用係数ベクトルｆと前記使用枚数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと緩和された第３制約条件式０≦ｘｉ≦１を生成して、記憶装置に記憶させるステップと、
初期設定手段が、前記予め定めた割付け方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶するステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算手段処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前期シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用枚数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの種類の原材料を何枚選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用枚数ベクトルの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘｉの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として面材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用枚数の組合せの中から、目的関数の値が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップを含むことを特徴とする部材割付方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【公開番号】特開２０１３−３６１７（Ｐ２０１３−３６１７Ａ）
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１１−１３０７９７（Ｐ２０１１−１３０７９７）
【出願日】平成２３年６月１３日（２０１１．６．１３）
【出願人】（０００１８３４２８）住友林業株式会社 (540)
【出願人】（５０１１９５６２５）住友林業クレスト株式会社 (43)
【Ｆターム（参考）】
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２３年６月１３日（２０１１．６．１３）
【出願人】（０００１８３４２８）住友林業株式会社 (540)
【出願人】（５０１１９５６２５）住友林業クレスト株式会社 (43)
【Ｆターム（参考）】
[ Back to top ]