JP5000735B2 - 部材割付システム - Google Patents
部材割付システム Download PDFInfo
- Publication number
- JP5000735B2 JP5000735B2 JP2010030975A JP2010030975A JP5000735B2 JP 5000735 B2 JP5000735 B2 JP 5000735B2 JP 2010030975 A JP2010030975 A JP 2010030975A JP 2010030975 A JP2010030975 A JP 2010030975A JP 5000735 B2 JP5000735 B2 JP 5000735B2
- Authority
- JP
- Japan
- Prior art keywords
- raw material
- vector
- value
- solution
- constraint condition
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/02—Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- General Factory Administration (AREA)
Description
本発明は、部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置に関する。
住宅構造材のプレカットには、断面形状や樹種，等級、レイヤといった仕様ごとに数種類の長さ (主に3m〜6m)の原材料が用意される。そこから決められた長さの部材(製品)を切り出す。一般的な大きさの住宅の場合、梁、桁、土台など横架材とよばれる構造材には約20種類の仕様がある。製品の仕様ごとに用意された数種類の長さの原材料から、これらの構造材がそれぞれ平均10本、１棟分を合計すると約200本の製品が切り出される。製品の仕様と、製品のサイズと、切り出される原材料の組合せにより、原材料から切り落とされて無駄になる部分の量が異なる。そこで、部材割付方法を改善する技術が開発された（特許文献１参照）。
上記のような部材割付方法の計算の目的は、製品の仕様ごとに用意された数種類の長さの原材料群から要求製品をいかに少ない原材料（歩留最高）で切り出すかということにある。他にも、各種の技術が開発されているが、これらの技術を利用したプレカット工場での割付方法では概ね90%程度といわれている。一定の規格で設計生産される建物の場合には、原材料のサイズに適合する構造材のサイズを決めておくと、さらに歩留を向上させることができる。しかしながら、注文生産により多種多様の設計に基づき、構造材を原材料から切り出す場合には、さらに歩留を向上させる計算方法の開発が求められている。実際に、１％の歩留を向上させるだけでも、多量の廃棄物減量を図ることができる。
上記の特許文献２では、既存の部材割付方法の計算結果を利用して、製品の仕様ごとに用意された数種類の長さの原材料群から要求製品を切り出す組合せの最適化をする。特に、多数の組み合わせについて最適解を探索する場合に、その探索範囲を絞り込む技術を紹介している。本発明はさらに、探索を効率的に進めることにより、演算処理時間をより一層短縮する部材割付システムと部材割付プログラムと記録媒体と部材割付方法と部材加工装置を提供することを目的とする。
以下の構成はそれぞれ上記の課題を解決するための手段である。
〈構成１〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材割付システム。
〈構成１〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材割付システム。
〈構成２〉
構成１に記載の部材割付システムにおいて、前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。
構成１に記載の部材割付システムにおいて、前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。
〈構成３〉
構成１に記載の部材割付システムにおいて、前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。
構成１に記載の部材割付システムにおいて、前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。
〈構成４〉
構成１に記載の部材割付システムにおいて、順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
構成１に記載の部材割付システムにおいて、順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。
〈構成５〉
構成１に記載の部材割付システムにおいて、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
構成１に記載の部材割付システムにおいて、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。
〈構成６〉
構成１乃至５のいずれかに記載の部材割付システムにおいて、前記第１制約条件式と第３制約条件式の制約条件の下で、前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、別の新たな非整数解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
構成１乃至５のいずれかに記載の部材割付システムにおいて、前記第１制約条件式と第３制約条件式の制約条件の下で、前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、別の新たな非整数解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。
〈構成７〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材加工装置。
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材加工装置。
〈構成８〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラム。
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラム。
〈構成９〉
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
コンピュータを、構成１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
〈構成１０〉
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させるステップと、初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、前記探索制御手段が、前記制約条件で、シンプレックス演算手段に演算処理を依頼するステップと、前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップと、判定手段が、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較するステップと、前記探索制御手段が、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開するステップを含むことを特徴とする部材割付方法。
それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させるステップと、初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、前記探索制御手段が、前記制約条件で、シンプレックス演算手段に演算処理を依頼するステップと、前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップと、判定手段が、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較するステップと、前記探索制御手段が、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開するステップを含むことを特徴とする部材割付方法。
制約条件を緩和して得られた複数の非整数解を、特定の評価式で評価するので、山登り法、ランダムリスタート法、焼き鈍し法等により、無駄な繰り返し演算を回避して、探索時間を短縮することができる。
本発明では、既存の任意の方法で得られた実用性のある解を基礎にして、それをシンプレックス法で評価し、さらに改善した解を求める。シンプレックス法は、線形計画問題の最適解を探索する方法として知られている。しかし、求められた製品長の種類や原材料の種類が数十種類にも及ぶと、組合せの数は数十万組を越えることがある。ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける、といった条件に基づいてそのまま演算処理のためのパラメータを作ると、最適値探索のためのシンプレックス演算処理に時間がかかりすぎるおそれがある。そこで、本発明では、シンプレックス法による演算処理のための制約条件を付加して、比較対象範囲の絞り込みをしながら、効率よく計算をする。そして、シンプレックス法によるピボット演算処理の過程で実行可能解が得られたときに、所定の評価式を使用してその後の見通しをたてる。その結果に応じて探索条件を変更し、無駄な演算処理を回避する。従って、探索のための演算処理時間を大幅に短縮できる。以下、本発明の実施の形態を実施例ごとに詳細に説明する。
図１は実施例１の部材割付システム１０のブロック図である。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、建物の構造材をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献１に記載されたとおりのものを使用することができる。
図の部材割付システム１０は、コンピュータ１２にインストールされたコンピュータプログラムにより動作する。このシステムは、例えば、コンピュータ１２に対してネットワーク１４を介して接続された端末装置１６により利用される。端末装置１６は、例えば、建物の構造材をプレカットするプレカット工場に設けられている。部材割付システム１０は、この端末装置１６からプレカットのための条件データを受け付けて、計算処理を実行してその結果を返す。端末装置１６は、返された部材割付データを使用して、プレカット装置１７を制御する。プレカット装置１７には、例えば、特許文献１に記載されたとおりのものを使用することができる。
コンピュータ１２には、演算処理装置２０と記憶装置４０とが設けられている。演算処理装置２０には、図のように、製品長設定手段２１、原材料長設定手段２２、初期設定手段２３、割付パターンベクトル生成手段２４、割付パターン行列生成手段２５、制約条件生成手段２６、費用係数ベクトル生成手段２７、目的関数生成手段２８、シンプレックス演算処理手段２９、探索制御手段３０、及び判定手段３１等のコンピュータプログラムがインストールされている。これらのコンピュータプログラムが連携して演算処理を実行する。
記憶装置４０には、図のように、製品長ベクトルLp４１、製品要求数量ベクトルｂ４２、原材料長ベクトルLm４３（または費用係数ベクトル）、初期実行可能解４４、原材料使用予定数量ベクトルｄ４５、割付パターン行列４６、原材料使用行列Ｃ４７、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０、目的関数５１、組合せリスト５２、部材割付データ５３、及び評価式５４等のデータが記憶されている。これらのデータは、予め外部から入力されるか、あるいは、上記のコンピュータプログラムの動作により生成されて、記憶装置４０に記憶されるものである。続いて、これらのコンピュータプログラムと記憶装置４０に記憶されるデータの具体的な説明をする。
図２は、部材割付システム１０を構成するコンピュータのハードウエアブロック図である。
部材割付システム１０の具体的な機能を説明する前に、部材割付システム１０のハードウエアを説明する。図のように、コンピュータ１２の本体ケース３中に収められた内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５と、ネットワークインタフェース１１６とが接続されている。入出力インタフェース１１５には、ディスプレイ３とキーボード４とマウス５とが接続されている。ネットワークインタフェース１１６には、ネットワーク１４を介して、端末装置１６が接続されている。以上のハードウェアは一般的によく知られたパーソナルコンピュータに備えられているものと変わらない。端末装置１６は、プレカット装置１７の部材選択供給装置１２０に、部材割付データを５３（図１）を供給する。これにより、指定された原材料が部材切断装置１２１に供給され、指定された割付パターンで切断される。切断された製品は製品搬送装置１２２により搬送され排出される。
部材割付システム１０の具体的な機能を説明する前に、部材割付システム１０のハードウエアを説明する。図のように、コンピュータ１２の本体ケース３中に収められた内部バス１１０には、ＣＰＵ（中央処理装置）１１１と、ＲＯＭ（リードオンリメモリ）１１２と、ＲＡＭ（ランダムアクセスメモリ）１１３と、ＨＤＤ（ハードディスク）１１４と、入出力インタフェース１１５と、ネットワークインタフェース１１６とが接続されている。入出力インタフェース１１５には、ディスプレイ３とキーボード４とマウス５とが接続されている。ネットワークインタフェース１１６には、ネットワーク１４を介して、端末装置１６が接続されている。以上のハードウェアは一般的によく知られたパーソナルコンピュータに備えられているものと変わらない。端末装置１６は、プレカット装置１７の部材選択供給装置１２０に、部材割付データを５３（図１）を供給する。これにより、指定された原材料が部材切断装置１２１に供給され、指定された割付パターンで切断される。切断された製品は製品搬送装置１２２により搬送され排出される。
図１に示した記憶装置４０は、図２のＲＯＭ１１２やＲＡＭ１１３やＨＤＤ１１４により構成される。図１に示した演算処理装置２０は、図２のＣＰＵ１１１、ＲＯＭ１１２、ＲＡＭ１１３等により構成される。各種のデータは主としてＨＤＤ１１４に記憶されて保存される。ＣＰＵ１１１が実行するコンピュータプログラムは、ＲＯＭ１１２に記憶され、あるいはＲＡＭ１１３に適時ロードされる。端末装置１６も同様の構成で構わない。ネットワーク１４はインターネットでもイントラネットでも構わない。
図３は、演算処理のパラメータを説明するための説明図である。
この図を参照しながら、演算処理に使用するパラメータの定義と、上記の各コンピュータプログラムの機能を説明する。
［製品長ベクトルLp］
生産されるべき製品の数量をｍとする。図の例では、ｍ＝７である。
製品長をLp1,Lp2,…,Lpmと表現する。単位は例えば、ｍ（メートル）である。
ｍ次の製品長ベクトルLp（行ベクトル）を下記のように定義する。
Lp＝（Lp1,Lp2,…,Lpm）
但し、（Lp1≧Lp2≧…≧Lpm）
図の例では、Lp＝（Lp1,Lp2,Lp3,Lp4,Lp5,Lp6,Lp7）である。
この図を参照しながら、演算処理に使用するパラメータの定義と、上記の各コンピュータプログラムの機能を説明する。
［製品長ベクトルLp］
生産されるべき製品の数量をｍとする。図の例では、ｍ＝７である。
製品長をLp1,Lp2,…,Lpmと表現する。単位は例えば、ｍ（メートル）である。
ｍ次の製品長ベクトルLp（行ベクトル）を下記のように定義する。
Lp＝（Lp1,Lp2,…,Lpm）
但し、（Lp1≧Lp2≧…≧Lpm）
図の例では、Lp＝（Lp1,Lp2,Lp3,Lp4,Lp5,Lp6,Lp7）である。
［製品要求数量ベクトルｂ］
数量ｍの製品の生産が要求されているとき、製品要求数量ベクトルｂを、下記のように定義する。なお、この実施例では、計算を単純化するために、全てｂi＝１として説明をする。実際には、ｂiは任意の正の整数でよい。
ｂ＝（ｂ1,ｂ2,…,ｂm）T
（上付きＴは転置を表す。即ち、ｂは列ベクトルである。以下も同様）
図３（ａ）の例では、ｂ＝（１，１，１，１，１，１，１）Tである。
製品長設定手段２１は、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLp４１と、製品要求数量を要素とする製品要求数量ベクトルｂ４２を生成して、記憶装置４０に記憶させる。
数量ｍの製品の生産が要求されているとき、製品要求数量ベクトルｂを、下記のように定義する。なお、この実施例では、計算を単純化するために、全てｂi＝１として説明をする。実際には、ｂiは任意の正の整数でよい。
ｂ＝（ｂ1,ｂ2,…,ｂm）T
（上付きＴは転置を表す。即ち、ｂは列ベクトルである。以下も同様）
図３（ａ）の例では、ｂ＝（１，１，１，１，１，１，１）Tである。
製品長設定手段２１は、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLp４１と、製品要求数量を要素とする製品要求数量ベクトルｂ４２を生成して、記憶装置４０に記憶させる。
［原材料データ］
原材料にはｋ種類の長さのものが含まれている。図の例では、ｋ＝３である。
原材料長をLm1,Lm2,…,Lmkと表現する。単位は例えば、ｍ（メートル）である。
ｋ次の原材料長ベクトルLm（行ベクトル）を下記のように定義する。
Lm＝（Lm1,Lm2,…,Lmk）
但し、（Lm1＞Lm2＞…＞Lmk）
図３（ｂ）の例では、Lm＝（Lm1,Lm2,Lm3）である。
原材料長設定手段２２は、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLm４３を生成し、記憶装置４０に記憶させる。
原材料にはｋ種類の長さのものが含まれている。図の例では、ｋ＝３である。
原材料長をLm1,Lm2,…,Lmkと表現する。単位は例えば、ｍ（メートル）である。
ｋ次の原材料長ベクトルLm（行ベクトル）を下記のように定義する。
Lm＝（Lm1,Lm2,…,Lmk）
但し、（Lm1＞Lm2＞…＞Lmk）
図３（ｂ）の例では、Lm＝（Lm1,Lm2,Lm3）である。
原材料長設定手段２２は、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLm４３を生成し、記憶装置４０に記憶させる。
［原材料使用予定数量ベクトルｄ］
原材料使用予定数量ベクトルｄ４５（列ベクトル）は、実行可能なある解に対して、ｋ種類の長さの材料がそれぞれ何本ずつ使用されるかを示す。これを下記のように定義する。
ｄ＝（ｄ1,ｄ2,…,ｄk）T
図３の例では、ｄ＝（ｄ1,ｄ2,ｄ3）T＝（１，２、１）Tである。原材料使用予定数量ベクトルｄ４５は、後で説明する第３制約条件式で使用される。
原材料使用予定数量ベクトルｄ４５（列ベクトル）は、実行可能なある解に対して、ｋ種類の長さの材料がそれぞれ何本ずつ使用されるかを示す。これを下記のように定義する。
ｄ＝（ｄ1,ｄ2,…,ｄk）T
図３の例では、ｄ＝（ｄ1,ｄ2,ｄ3）T＝（１，２、１）Tである。原材料使用予定数量ベクトルｄ４５は、後で説明する第３制約条件式で使用される。
［使用本数ベクトルｘ］
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、選択したｎ本の原材料の使用本数を表すｎ次の使用本数ベクトルｘを、下記のように定義する。なお、ｋ種類の原材料からｎ本の原材料を選択するとき、同一の原材料を２度以上重複して選択して構わない。
ｘ＝（ｘ1,ｘ2,…,ｘn）T
なお、計算を単純化するために、製品要求数量ベクトルｂの要素を全てｂｉ＝１としたので、ｍ次の使用本数ベクトルｘの各要素ｘｉは０≦ｘｉ≦１となり、部材割付の結果として、意味を持つのは、ｘｉが０または１の場合である。
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、選択したｎ本の原材料の使用本数を表すｎ次の使用本数ベクトルｘを、下記のように定義する。なお、ｋ種類の原材料からｎ本の原材料を選択するとき、同一の原材料を２度以上重複して選択して構わない。
ｘ＝（ｘ1,ｘ2,…,ｘn）T
なお、計算を単純化するために、製品要求数量ベクトルｂの要素を全てｂｉ＝１としたので、ｍ次の使用本数ベクトルｘの各要素ｘｉは０≦ｘｉ≦１となり、部材割付の結果として、意味を持つのは、ｘｉが０または１の場合である。
従って、同一の原材料を複数本使用するときは、必要数だけ、同一製品長を列挙した原材料長ベクトルLmを使用する。例えば、上記の具体例では、Lm1,Lm2,Lm2,Lm3と列挙された４本の原材料に対して、それぞれ求められている製品を割り付けた。このとき、最初のLm1に対してｘ1、２番目のLm2に対してｘ2、３番目のLm2に対してｘ3、４番目のLm3に対してｘ4を設定する。図の例では、ｘ1＝ｘ2＝ｘ3＝ｘ4＝１である。選択される原材料と選択されない原材料とを列挙したとき、選択される原材料に設定されるｘｉの値は１である。選択されない原材料に設定されるｘｉの値は０である。使用本数ベクトルｘは制約条件式で使用される。この取り扱いは実施例３でより具体的に説明する。
［割付パターンベクトルａj］
いずれか１本の原材料から、数量ｍの製品のうちのいずれかを切り出すように割り付けたデータを、ｍ次の割付パターンベクトルａj（列ベクトル）で表す。これを下記のように定義する。
ａj＝（a1,a2,…,am）T
下記に、図３（ｃ）の例における割付パターンベクトルを示す。
Lm1にLp2とLp6をそれぞれ１本割付ける （０，１，０，０，０，１，０）T
Lm2にLp1を１本割付ける （１，０，０，０，０，０，０）T
Lm2にLp3とLp5をそれぞれ１本割付ける （０，０，１，０，１，０，０）T
Lm3にLp4とLp7をそれぞれ１本割付ける （０，０，０，１，０，０，１）T
いずれか１本の原材料から、数量ｍの製品のうちのいずれかを切り出すように割り付けたデータを、ｍ次の割付パターンベクトルａj（列ベクトル）で表す。これを下記のように定義する。
ａj＝（a1,a2,…,am）T
下記に、図３（ｃ）の例における割付パターンベクトルを示す。
Lm1にLp2とLp6をそれぞれ１本割付ける （０，１，０，０，０，１，０）T
Lm2にLp1を１本割付ける （１，０，０，０，０，０，０）T
Lm2にLp3とLp5をそれぞれ１本割付ける （０，０，１，０，１，０，０）T
Lm3にLp4とLp7をそれぞれ１本割付ける （０，０，０，１，０，０，１）T
上記の割付パターンベクトルａjは、下式を満足するように生成される。
Ｌp・ａj≦Ｌ （ｊ＝1,2,…,n）
この式の左辺の積（Ｌp・ａj）は、選択された原材料に割り付けられた、１本の製品長もしくは複数本の製品長の総和である。割付パターンベクトルａjを生成するときには、この長さを割り付けることができる最小長さLmiの原材料が選択される。Ｌは、その選択された原材料の長さLmiを示す。なお、実加工では、矩を出すためのハナ切り長、刃物厚が考慮されるが、ここでは無視する。
Ｌp・ａj≦Ｌ （ｊ＝1,2,…,n）
この式の左辺の積（Ｌp・ａj）は、選択された原材料に割り付けられた、１本の製品長もしくは複数本の製品長の総和である。割付パターンベクトルａjを生成するときには、この長さを割り付けることができる最小長さLmiの原材料が選択される。Ｌは、その選択された原材料の長さLmiを示す。なお、実加工では、矩を出すためのハナ切り長、刃物厚が考慮されるが、ここでは無視する。
例えば、図の例でいえば、Lp3とLp5をそれぞれ１本割付けるとすると、原材料Lm1またはLm2のいずれにも割付ができる。しかし、Lm1＞Lm2だから、割付対象をLm2というように原材料を選択する。こうして、経済的に割り付けできる関係を見つける。
図の例は、実行可能解に相当する一組の割付パターンベクトルを列挙した。シンプレックス法で最適解を求めるための準備として、必要に応じてシンプレックス演算処理の結果に基づき、割付パターンベクトルを列挙する。
図の例は、実行可能解に相当する一組の割付パターンベクトルを列挙した。シンプレックス法で最適解を求めるための準備として、必要に応じてシンプレックス演算処理の結果に基づき、割付パターンベクトルを列挙する。
割付パターンベクトル生成手段２４は、求められているｍ本の製品の製品長データと用意されたｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトル４６ａを生成し、記憶装置４０に記憶させる。
［割付パターン行列］
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付けるときには、上記の割付パターンベクトルをｎ個並べる。ａjをｎ個並べたｍ×ｎ次の割付パターン行列を下記に定義する。これを図３（ｄ）に示す。
Ａ＝（ａij） （ｉ＝1,2,…,ｍ、ｊ＝1,2,…,ｎ）
割付パターン行列生成手段２５は、割付パターンベクトル生成手段２４の生成した割付パターンベクトル４６ａをｎ個並べたｍ×ｎ次の割付パターン行列を生成し、記憶装置４０に記憶させる。
ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付けるときには、上記の割付パターンベクトルをｎ個並べる。ａjをｎ個並べたｍ×ｎ次の割付パターン行列を下記に定義する。これを図３（ｄ）に示す。
Ａ＝（ａij） （ｉ＝1,2,…,ｍ、ｊ＝1,2,…,ｎ）
割付パターン行列生成手段２５は、割付パターンベクトル生成手段２４の生成した割付パターンベクトル４６ａをｎ個並べたｍ×ｎ次の割付パターン行列を生成し、記憶装置４０に記憶させる。
［第１制約条件］
割付パターン行列Ａと使用本数ベクトルｘとの積は、選択された各原材料から、それぞれ該当する割り付けパターンで切り出した製品数になる。従って、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならない。求められている各製品の数量は、製品要求数量ベクトルｂに相当する。従って、少なくとも、下式を満足しないと、必要な数の製品が得られない。
Σａij・ｘj≧ｂi
割付パターン行列Ａと使用本数ベクトルｘとの積は、選択された各原材料から、それぞれ該当する割り付けパターンで切り出した製品数になる。従って、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならない。求められている各製品の数量は、製品要求数量ベクトルｂに相当する。従って、少なくとも、下式を満足しないと、必要な数の製品が得られない。
Σａij・ｘj≧ｂi
なお、不等号が成立するときは作りすぎである。計算の便宜上、上記の不等式を制約条件とする。この制約条件式は、Ａｘ≧ｂと表す。
図３の例では、生産された製品数も必要な製品数も７であって、等号が成立する。
制約条件生成手段２６は、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上であるとする第１制約条件式を生成して、記憶装置４０に記憶させる。
図３の例では、生産された製品数も必要な製品数も７であって、等号が成立する。
制約条件生成手段２６は、割付パターン行列Ａから選択された原材料から該当する割り付けパターンで切り出した各製品数は、それぞれ求められている各製品の数量以上であるとする第１制約条件式を生成して、記憶装置４０に記憶させる。
［原材料使用行列Ｃ］
ｋ種類の原材料のうちのどの原材料を使用するかを示す、ｋ次の原材料使用ベクトルｃjを次のように定義する。これを図３（ｅ）に示す。
ｃj＝（ｃ1j,ｃ2j,…,ｃkj）T
但し、ｃ1j,ｃ2j,…,ｃkjはいずれも、０または１である。
上記のように、ｋ種類の原材料から選択したｎ本の原材料を表すのに、原材料使用行列Ｃを用いる。これをｃjをｎ個並べたｋ×ｎ次の行列で定義する。
Ｃ＝（ｃij）（ｉ＝1,2,…,ｋ、ｊ＝1,2,…,n）
ｋ種類の原材料のうちのどの原材料を使用するかを示す、ｋ次の原材料使用ベクトルｃjを次のように定義する。これを図３（ｅ）に示す。
ｃj＝（ｃ1j,ｃ2j,…,ｃkj）T
但し、ｃ1j,ｃ2j,…,ｃkjはいずれも、０または１である。
上記のように、ｋ種類の原材料から選択したｎ本の原材料を表すのに、原材料使用行列Ｃを用いる。これをｃjをｎ個並べたｋ×ｎ次の行列で定義する。
Ｃ＝（ｃij）（ｉ＝1,2,…,ｋ、ｊ＝1,2,…,n）
図の例でｃijは、下記のとおりである。
ｃ1＝（１、０、０）T
ｃ2＝（０，１，０）T
ｃ3＝（０，１，０）T
ｃ4＝（０，０，１）T
割付パターン行列生成手段２５は、各割付パターンで、ｋ種類の原材料のうちのどの原材料を使用するかを示す原材料使用ベクトルｃjを列挙した、ｋ×ｎ次の原材料使用行列Ｃを生成して、記憶装置に記憶させる。
ｃ1＝（１、０、０）T
ｃ2＝（０，１，０）T
ｃ3＝（０，１，０）T
ｃ4＝（０，０，１）T
割付パターン行列生成手段２５は、各割付パターンで、ｋ種類の原材料のうちのどの原材料を使用するかを示す原材料使用ベクトルｃjを列挙した、ｋ×ｎ次の原材料使用行列Ｃを生成して、記憶装置に記憶させる。
［第２制約条件］
なお、ｃjはｋ種類の原材料のうちの一つを指定するベクトルだから、下式を満足する。
Σｃij＝１
ｋ個の数字のうち１個だけが１で他は全て０ということである。
また、各原材料の長さは、割付けできる最小長さのものが選択される。
ΣＬmi・ｃij＝Ｌ
このLは、割付パターンベクトルの生成条件Ｌp・ａj≦Ｌで示した値である。
なお、ｃjはｋ種類の原材料のうちの一つを指定するベクトルだから、下式を満足する。
Σｃij＝１
ｋ個の数字のうち１個だけが１で他は全て０ということである。
また、各原材料の長さは、割付けできる最小長さのものが選択される。
ΣＬmi・ｃij＝Ｌ
このLは、割付パターンベクトルの生成条件Ｌp・ａj≦Ｌで示した値である。
また、既に定義したとおり、ｎ本の原材料の使用本数ベクトルｘは、ｘ＝（ｘ1,ｘ2,…,ｘn）であった。また、原材料使用予定数量ベクトルｄは、原材料長さごとの使用数を示すものであった。
従って、下式の条件が満足されなければならない。
Σｃij・ｘj＝ｄi（ｉ＝1,2,…,ｋ）
この制約条件式は、Ｃｘ＝ｄと表す。
これは、どの長さの原材料を何本選択して実際の割付に使用するかを定める。なお、Ａｘ≧ｂとＣｘ＝ｄの制約条件の具体的な関係は、実施例３でより明確に説明をする。
制約条件生成手段２６は、割付パターン行列生成手段２５が生成した原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が、原材料使用予定数量ベクトルｄと等しいとする第２制約条件式を生成して、記憶装置に記憶させる。
従って、下式の条件が満足されなければならない。
Σｃij・ｘj＝ｄi（ｉ＝1,2,…,ｋ）
この制約条件式は、Ｃｘ＝ｄと表す。
これは、どの長さの原材料を何本選択して実際の割付に使用するかを定める。なお、Ａｘ≧ｂとＣｘ＝ｄの制約条件の具体的な関係は、実施例３でより明確に説明をする。
制約条件生成手段２６は、割付パターン行列生成手段２５が生成した原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が、原材料使用予定数量ベクトルｄと等しいとする第２制約条件式を生成して、記憶装置に記憶させる。
［第３制約条件］
上記の使用本数ベクトルｘの各要素ｘiは０または１である。列挙された多数の割付パターンベクトルの中のいずれを選択するかどうかを決める意味をもつからである。従って、下式のような制約条件式が成立する。
ｘi∈｛０，１｝
なお、この実施例では、この制約条件を緩和する。即ち、０≦ｘi≦１という制約条件式を設定する。
制約条件生成手段は、使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１である旨を示す第３制約条件式を生成して、記憶装置に記憶させる。
上記の使用本数ベクトルｘの各要素ｘiは０または１である。列挙された多数の割付パターンベクトルの中のいずれを選択するかどうかを決める意味をもつからである。従って、下式のような制約条件式が成立する。
ｘi∈｛０，１｝
なお、この実施例では、この制約条件を緩和する。即ち、０≦ｘi≦１という制約条件式を設定する。
制約条件生成手段は、使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１である旨を示す第３制約条件式を生成して、記憶装置に記憶させる。
［費用係数ベクトル］
長さの違う原材料ごとに、価格だけでなく、運搬費、保管費、加工賃等が異なる。計算に含めるべき全ての費用要素をｎ次の費用係数ベクトルｆに含め、下記のように定義する。
ｆ＝（ｆ1,ｆ2,…,ｆn）
費用係数ベクトルｆは選択されたｎ種類の原材料にのみ適用されるから、ｎ次のベクトルになっている。なお、計算の便宜上、ｆ1,ｆ2,…,ｆnは、費用換算してしまい、単位を円とする。従って、目的関数値が小さいほど、少ないコストで製品を得ることができる。
長さの違う原材料ごとに、価格だけでなく、運搬費、保管費、加工賃等が異なる。計算に含めるべき全ての費用要素をｎ次の費用係数ベクトルｆに含め、下記のように定義する。
ｆ＝（ｆ1,ｆ2,…,ｆn）
費用係数ベクトルｆは選択されたｎ種類の原材料にのみ適用されるから、ｎ次のベクトルになっている。なお、計算の便宜上、ｆ1,ｆ2,…,ｆnは、費用換算してしまい、単位を円とする。従って、目的関数値が小さいほど、少ないコストで製品を得ることができる。
原材料の価格が長さに比例する場合は、歩留が最高になる場合と総費用が最小になる場合とは同意である。しかし、単位長さ当たりの価格が原材料長により異なる場合には、費用係数を調整する。費用係数ベクトル生成手段２７は、原材料長ベクトルLmの各要素に価格成分を含めてｎ次の費用係数ベクトルｆを生成する。費用係数ベクトルｆの要素ｆiは、単位が円のデータである。費用計数係数ベクトル生成手段２７は原材料長ベクトルLmを費用係数ベクトルｆで置き換えるようにすれば、以下は、費用係数ベクトルｆを意識することなく演算処理ができる。
［目的関数］
この計算では、ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、目的関数値が小さいほど少ないコストで製品を得ることができる。そこで、選択したｎ本の原材料にかかる費用の総和を示す目的関数を下記のように定義する。
Ｍｉｎ Σｆi・ｘi
目的関数生成手段２８は、選択したｎ本の当該原材料にかかる費用の総和を示す目的関数を生成して、記憶装置に記憶させる。
この計算では、ｋ種類の原材料から任意に選択したｎ本の原材料に対して、それぞれｍ種類の製品のうちのいずれかの製品を割り付ける。このとき、目的関数値が小さいほど少ないコストで製品を得ることができる。そこで、選択したｎ本の原材料にかかる費用の総和を示す目的関数を下記のように定義する。
Ｍｉｎ Σｆi・ｘi
目的関数生成手段２８は、選択したｎ本の当該原材料にかかる費用の総和を示す目的関数を生成して、記憶装置に記憶させる。
［整数計画を連続緩和問題とする］
シンプレックス法による演算処理を実行するために、目的関数と制約条件を次のように定義する。
Ｍｉｎ Σｆi・ｘi
subject to. Ａｘ≧ｂ
Cｘ＝ｄ
０≦ｘi≦１
シンプレックス法による演算処理を実行するために、目的関数と制約条件を次のように定義する。
Ｍｉｎ Σｆi・ｘi
subject to. Ａｘ≧ｂ
Cｘ＝ｄ
０≦ｘi≦１
第１番目の式は、目的関数生成手段により生成された目的関数である。
第２番目の式は、制約条件生成手段により生成された第１制約条件式である。
第３番目の式は、制約条件生成手段により生成された第２制約条件式である。
第４番目の式は、制約条件生成手段により生成された第３制約条件式である。
目的関数は、選択したｎ本の当該原材料にかかる費用の総和を示す。
第１制約条件式は、割付パターン行列Ａと使用本数ベクトルｘと製品要求数量ベクトルｂの関係を示す。
第２制約条件式は、原材料使用行列Ｃと原材料の使用本数ベクトルｘと原材料使用予定数量ベクトルｄの関係を示す。
第３制約条件式は、ｘiが０以上１以下であることを示す。
第２番目の式は、制約条件生成手段により生成された第１制約条件式である。
第３番目の式は、制約条件生成手段により生成された第２制約条件式である。
第４番目の式は、制約条件生成手段により生成された第３制約条件式である。
目的関数は、選択したｎ本の当該原材料にかかる費用の総和を示す。
第１制約条件式は、割付パターン行列Ａと使用本数ベクトルｘと製品要求数量ベクトルｂの関係を示す。
第２制約条件式は、原材料使用行列Ｃと原材料の使用本数ベクトルｘと原材料使用予定数量ベクトルｄの関係を示す。
第３制約条件式は、ｘiが０以上１以下であることを示す。
初期設定手段２３は、任意の方法で取得した任意の初期実行可能解４４を受け付ける。そして、シンプレックス演算処理のためのパラメータを生成する。任意の方法とは、例えばFirst Fit法、特許文献１に記載された方法等である。初期実行可能解は、上記の割付パターン行列Ａ４６から選択される割付パターンベクトルを指定する原材料の使用本数ベクトルｘで表すことができる。これも、実施例３でより具体的に説明をする。最初のシンプレックス演算処理のために入力するパラメータは、目的関数Σｆi・ｘiと第１制約条件式Ａｘ≧ｂと第３制約条件式０≦ｘi≦１を構成するデータである。
探索制御手段３０は、シンプレックス演算処理手段に対して、Cｘ＝ｄの制約条件を除外したパラメータを入力して最初の演算処理を実行させる。シンプレックス演算処理手段は、目的関数の値を改善するようにシンプレックス表の基底変数を変更して解を出力する。第３制約条件式０≦ｘi≦１は、ｘi∈｛０，１｝という制約条件を緩和したものである。従って、解には、ｘi＝０．５といった整数以外のものが含まれる場合もある。また、目的関数の値が同一の解が複数存在することもある。
探索制御手段３０は、得られた解の中に、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解を検出する。検出されたときは、その解を最適解として、部材割付データ５３を生成して、処理を終了する。それ以外の場合には、探索制御手段は、次のシンプレックス演算処理のためのパラメータを再生成する。まず、初期設定をした実行可能解の目的関数の値Ｆ０を最大値に設定する。初期設定の解を改善するのが目的だからである。また、最初のシンプレックス演算処理で得られた解の目的関数の値Ｆ１を最小値に設定する。条件を緩和して得られた解であるから、そのときの目的関数値が限界値と判断する。
次に、探索制御手段３０は、目的関数の値がＦ１以上、Ｆ０未満となる、原材料の本数の組合せを列挙して、組合せリストを生成する。これは、原材料使用予定数量ベクトルｄに該当する。この組合せリストの中から目的関数の値が最小のものを次候補に選定する。この具体例は実施例３で説明するが、制約条件生成手段２６は、第２制約条件式Cｘ＝ｄを生成する。目的関数や割付パターンベクトル等のパラメータに変更があれば第１制約条件式Ａｘ≧ｂも生成する。その後、探索制御手段３０は、シンプレックス演算処理手段２９に対して、生成したパラメータを入力して演算処理を実行させる。第３制約条件式０≦ｘi≦１は変更しない。
その結果、得られた解に、ｘiの値がいずれも０または１であって、それ以外の値を含まないものを検出する。検出されたときは、その解を最適解とする。この探索処理のための演算時間を短縮するために、後で説明するような評価式を用いた制御を実行する。最適解が得られないときには、原材料の本数の組合せのリスト中で、目的関数の値が上記の次候補と同値のものがあれば、それを次候補に選定する。なければその次に小さいものを次候補に選定する。そして、前回と全く同様にして、第２制約条件式Cｘ＝ｄを生成し、パラメータを変更して、シンプレックス演算処理手段に対して、生成したパラメータを入力して演算処理を実行させる。
こうして、シンプレックス演算処理を繰り返して、最適解を探索する。なお、原材料の本数の組合せのリストが多数生成されたときは、原材料の本数の組合せの選択回数に上限を設けて、一定回数以上探索しても最適解がみつからなければ、初期実行可能解を最適解として、部材割付データ５３を出力するとよい。また、以上の演算処理では、割付パターン行列Ａと使用本数ベクトルｘと製品要求数量ベクトルｂの関係を示す制約条件を使用したので、シンプレックス演算処理のパラメータに製品長が含まれず、計算が煩雑にならない。また、各要素が０または１のみの値をとる原材料の使用本数ベクトルｘが基底変数になるようにパラメータを設定し、０≦ｘi≦１という緩和した制約条件でシンプレックス演算処理を実行するので、最適解が得られない場合でも目的関数の最小値を得て、探索範囲を限定することができる。
図４は、初回のシンプレックス演算処理動作フローチャートである。
これらの図を用いて、上記のシステムを制御するコンピュータプログラムの実施例を説明する。
ステップＳ１１では、原材料長設定手段２２が原材料データの受け付けをする。端末装置１６から、使用される全ての原材料長データの入力を受け付けて、原材料長ベクトルLm４３に対応するデータを生成し、記憶装置４０に記憶させる。ステップＳ１２では、製品長設定手段２１が、製品長と数量の入力受け付けをする。端末装置１６から、求められている製品長データの入力を受け付けて、製品長ベクトルLp４１と製品要求数量ベクトルｂ４２に対応するデータを生成し、記憶装置４０に記憶させる。
これらの図を用いて、上記のシステムを制御するコンピュータプログラムの実施例を説明する。
ステップＳ１１では、原材料長設定手段２２が原材料データの受け付けをする。端末装置１６から、使用される全ての原材料長データの入力を受け付けて、原材料長ベクトルLm４３に対応するデータを生成し、記憶装置４０に記憶させる。ステップＳ１２では、製品長設定手段２１が、製品長と数量の入力受け付けをする。端末装置１６から、求められている製品長データの入力を受け付けて、製品長ベクトルLp４１と製品要求数量ベクトルｂ４２に対応するデータを生成し、記憶装置４０に記憶させる。
ステップＳ１３では、初期設定手段２３が初期実行可能解４４の入力を受け付ける。その結果は 記憶装置４０に記憶される。ステップＳ１４では、割付パターンベクトル生成手段２４が、製品長ベクトルLp４１や原材料長ベクトルLm４３等を比較して、割付パターンベクトルの生成をする。割付パターンベクトルは、記憶装置４０に記憶される。続いて、ステップＳ１５で、割付パターン行列生成手段２５が割付パターン行列４６の生成をして、記憶装置４０に記憶させる。次に、ステップＳ１６で、制約条件生成手段２６が、第１制約条件式４８、第２制約条件式４９、第３制約条件式５０を生成して、記憶装置４０に記憶させる。
ステップＳ１７では、費用係数ベクトル生成手段２７が費用係数ベクトルの生成をし、ステップＳ１８では、目的関数生成手段２８がその費用係数ベクトルを使用して目的関数５１の設定をする。その結果が記憶装置４０に記憶される。次に探索制御手段３０が、ステップＳ１９で、後で説明するように最初の演算用パラメータをシンプレックス演算処理手段２９に入力する。ステップＳ２０では、この演算用パラメータを使用したシンプレックス演算を実行する。解が得られたら探索制御手段３０は、ステップＳ２１で、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから、ステップＳ２３で部材割付データを出力して処理を終了する。ノーのときはステップＳ２２の処理に移行する。ステップＳ２２では、探索制御手段３０が、図５に示した手順で、シンプレックス法による演算を制御する。
図５は、１回目のシンプレックス演算終了後の演算処理のフローチャートである。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数の範囲で、原材料の組合せリストの生成をする。その結果を目的関数の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、後で説明するように制約条件の設定をする。
このフローチャートの動作は、探索制御手段３０が制御し、シンプレックス演算処理手段２９が実行する。まず、ステップＳ３１で、初期実行可能解から、目的関数の最大値の設定をする。次に、ステップＳ３２では、図４のステップＳ２０の演算処理結果から、目的関数の最小値を設定する。次にステップＳ３３で、設定された目的関数の範囲で、原材料の組合せリストの生成をする。その結果を目的関数の小さいものから並べて記憶装置４０に記憶させる。ステップＳ３４では、組合せリストの中から、目的関数値が最小のものを選択する。さらに、ステップＳ３５では、制約条件生成手段２６に依頼をして、後で説明するように制約条件の設定をする。
また、ステップＳ３６では、目的関数生成手段２８に依頼をして、目的関数の設定をする。ステップＳ３７でシンプレックス演算を実行する。ステップＳ３８では、探索制御手段３０が、整数解が得られたかどうかという判断をする。この判断の結果がイエスのときはこの処理を終了して、図４のステップＳ２３に進む。一方、ノーのときはステップＳ３９の処理に移行する。ステップＳ３９では、予め設定されたＷ回だけ、ピボット演算処理を繰り返したかどうか判断する。Ｗ回は上限値である。これにより、長時間探索をしても、解が得られない場合に、処理を中止する。即ち、ステップＳ４０で、初期実行可能解を演算処理結果として出力する。繰り返し回数がＷ回に満たないときは、ステップＳ３４に戻り、次に大きい目的関数値となる組合せリストを選択して、再度シンプレックス演算処理を実行する。以上の処理により、コンピュータプログラムは自動的に最適解を探索する。本発明では、上記のステップＳ３７における探索動作に後で説明するような特殊な制御を行う。
図６から図１１までは、特許文献２に記載の具体的な計算例の説明図である。
（原材料データ）
例えば、用意された原材料は５種類である。その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lm1＝６００００
Lm2＝４９０００
Lm3＝４５０００
Lm4＝４００００
Lm5＝３００００
（製品長データ）
求められている製品は７本で、その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lp1＝５３０５０
Lp2＝４４３５０
Lp3＝３０７００
Lp4＝２６２５０
Lp5＝２１０５０
Lp6＝１７８４０
Lp7＝１７１５０
（原材料データ）
例えば、用意された原材料は５種類である。その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lm1＝６００００
Lm2＝４９０００
Lm3＝４５０００
Lm4＝４００００
Lm5＝３００００
（製品長データ）
求められている製品は７本で、その長さは下記のとおりとする。長さの単位は０．１ｍｍ（ミリメートル）である。
Lp1＝５３０５０
Lp2＝４４３５０
Lp3＝３０７００
Lp4＝２６２５０
Lp5＝２１０５０
Lp6＝１７８４０
Lp7＝１７１５０
（割付パターンベクトル）
図６の（ａ）は、割付パターンベクトルの説明図である。
図の最も左側の上から下に向かう縦１列に、上記の７種類の製品長が列挙されている。また、最も上段の左から右に向かう横１列に、原材料長が列挙されている。各原材料長の下の縦一列が、それぞれ割付パターンベクトルである。例えば、原材料長が４５０００のものには、製品長が４４３５０のものを１本割り付けることができる。例えば、原材料長が４９０００のものには、製品長が３０７００と１７８４０のものを各１本割り付けることができる。この表には、この要領で、７本の製品の製品長データと５種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す７次の割付パターンベクトルを列挙した。ここで、ｘ１〜ｘ５は初期実行可能解から得られた割付パターンベクトルで、ｘ６〜ｘ１８は、最初のシンプレックス演算処理の結果に基づき追加生成した割付パターンベクトルである。
図６の（ａ）は、割付パターンベクトルの説明図である。
図の最も左側の上から下に向かう縦１列に、上記の７種類の製品長が列挙されている。また、最も上段の左から右に向かう横１列に、原材料長が列挙されている。各原材料長の下の縦一列が、それぞれ割付パターンベクトルである。例えば、原材料長が４５０００のものには、製品長が４４３５０のものを１本割り付けることができる。例えば、原材料長が４９０００のものには、製品長が３０７００と１７８４０のものを各１本割り付けることができる。この表には、この要領で、７本の製品の製品長データと５種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す７次の割付パターンベクトルを列挙した。ここで、ｘ１〜ｘ５は初期実行可能解から得られた割付パターンベクトルで、ｘ６〜ｘ１８は、最初のシンプレックス演算処理の結果に基づき追加生成した割付パターンベクトルである。
ｘ１〜ｘ１８は、原材料の使用本数ベクトルｘの各要素である。それぞれその下側に表示した長さの原材料を該当する割付パターンで使用するかどうかを、０または１の数値で表示する。ｘ１〜ｘ１８の値が０のときはその原材料を使用しない、１のときは使用することを示す。この原材料の使用本数ベクトルｘにより、列挙された割付パターンベクトルのうちのいずれを選択するかを表示する。
（目的関数）
説明を簡略化するために、費用係数ベクトルｆの各要素を原材料長と一致させる。すなわち、長さの数値をそのまま円と読み替える。
図６（ａ）の原材料長の右側の１８個の数値が、費用係数ベクトルｆの要素である。従って、最初のシンプレックス演算処理で、初期値として入力する実行可能解の目的関数Σ（ｆｉ・ｘｉ）の値は、ｘ１〜ｘ５の使用原材料長の総和で、２３３０００となる。以下の計算ではこれを改善する解を求めるのだから、目的関数の上限値を２３３０００に定める。
説明を簡略化するために、費用係数ベクトルｆの各要素を原材料長と一致させる。すなわち、長さの数値をそのまま円と読み替える。
図６（ａ）の原材料長の右側の１８個の数値が、費用係数ベクトルｆの要素である。従って、最初のシンプレックス演算処理で、初期値として入力する実行可能解の目的関数Σ（ｆｉ・ｘｉ）の値は、ｘ１〜ｘ５の使用原材料長の総和で、２３３０００となる。以下の計算ではこれを改善する解を求めるのだから、目的関数の上限値を２３３０００に定める。
（原材料使用行列Ｃ）
図６の（ｂ）は、同図（ａ）の各割付パターンベクトル対応する原材料使用ベクトルｃjを示す。ｘ１〜ｘ１８の割付パターンベクトルが選択されたときに使用される原材料を示している。従って、原材料使用ベクトルｃjと原材料の使用本数ベクトルｘの積は、各原材料長の原材料の使用本数の内訳を示す。
図６の（ｂ）は、同図（ａ）の各割付パターンベクトル対応する原材料使用ベクトルｃjを示す。ｘ１〜ｘ１８の割付パターンベクトルが選択されたときに使用される原材料を示している。従って、原材料使用ベクトルｃjと原材料の使用本数ベクトルｘの積は、各原材料長の原材料の使用本数の内訳を示す。
図７と図８は、後で具体的に説明するシンプレックス法演算処理により得られた非整数解の説明図である。
図７と図８の表では、解の値が０の割付パターンベクトルの表示を除外した。即ち、図７は、ｘ４＝ｘ１＝ｘ１６＝１、ｘ１２＝ｘ９＝ｘ３＝０．５で、他は０という解である。図８は、ｘ４＝ｘ１＝１、ｘ２＝ｘ９＝ｘ１０＝ｘ１６＝ｘ３＝０．５で、他は０という解である。例えば、図７の例では、原材料長が６００００，４５０００，４９０００のものを各１本、原材料長が４００００，４９０００，４５０００のものを各０．５本使用すると、目的関数値が２２１０００になるという結果が得られた。たしかに、目的関数値は初期値よりも小さい。しかしながら、ｘi∈｛０，１｝という制約条件を０≦ｘｉ≦１というように緩和したので、ｘｉ＝０．５という、実行不可能な解が得られた。
図７と図８の表では、解の値が０の割付パターンベクトルの表示を除外した。即ち、図７は、ｘ４＝ｘ１＝ｘ１６＝１、ｘ１２＝ｘ９＝ｘ３＝０．５で、他は０という解である。図８は、ｘ４＝ｘ１＝１、ｘ２＝ｘ９＝ｘ１０＝ｘ１６＝ｘ３＝０．５で、他は０という解である。例えば、図７の例では、原材料長が６００００，４５０００，４９０００のものを各１本、原材料長が４００００，４９０００，４５０００のものを各０．５本使用すると、目的関数値が２２１０００になるという結果が得られた。たしかに、目的関数値は初期値よりも小さい。しかしながら、ｘi∈｛０，１｝という制約条件を０≦ｘｉ≦１というように緩和したので、ｘｉ＝０．５という、実行不可能な解が得られた。
本発明では、上記の解が得られたときの目的関数値を、最適値の下限値に設定する。即ち、初期実行可能解を改善することを目的とするから、目的関数値の初期値を最大値２３３０００に設定し、最初のシンプレックス演算処理により得られた目的関数値２２１０００を最小値に設定する。この範囲に最適値があるとし、再度探索をする。ここで、原材料を任意の本数だけ組合せて、目的関数値が２２１０００以上、２３３０００より小さい値になる場合を列挙する。例えば、組合せを選択しながら集計する演算処理結果を昇順にソートすればよい。
全ての組合せを列挙する必要はない、原材料長の和、即ち、目的関数値が小さいものから順に列挙しながら、第２回目以降のシンプレックス演算処理を実行し、実行可能解、即ち、最適解が得られたら処理を終了すればよい。従って、例えば、Ｎｏ．１〜Ｎｏ．１０位までの組み合わせを列挙し、探索範囲を十分に狭めてシンプレックス演算処理を実行することにより、演算処理時間を短縮することができる。図９でそれを例示する。
図９は、最終的に得られた整数解の例を示す説明図である。
図９（ａ）は、Ｎｏ．１〜Ｎｏ．１０の組み合わせと目的関数値の例を示す。図９（ｂ）は得られた整数解の例を示す。
Ｎｏ．１では、原材料長４９０００が３本、４５０００が１本、３００００が１本、という組合せにする。Ｎｏ．２では、原材料長４９０００が２本、４５０００が１本、４００００が２本、という組合せにする。Ｎｏ．３では、原材料長４９０００が１本、４５０００が１本、４００００が１本、３００００が３本という組合せにする。Ｎｏ．４では、原材料長６００００〜３００００の全てが１本という組合せにする。最大値までは３０とおり以上の組み合わせがあるが、まず、ここまで列挙して探索演算処理を開始する。
図９（ａ）は、Ｎｏ．１〜Ｎｏ．１０の組み合わせと目的関数値の例を示す。図９（ｂ）は得られた整数解の例を示す。
Ｎｏ．１では、原材料長４９０００が３本、４５０００が１本、３００００が１本、という組合せにする。Ｎｏ．２では、原材料長４９０００が２本、４５０００が１本、４００００が２本、という組合せにする。Ｎｏ．３では、原材料長４９０００が１本、４５０００が１本、４００００が１本、３００００が３本という組合せにする。Ｎｏ．４では、原材料長６００００〜３００００の全てが１本という組合せにする。最大値までは３０とおり以上の組み合わせがあるが、まず、ここまで列挙して探索演算処理を開始する。
Ｎｏ．１〜３やＮｏ．５の組み合わせでは、使用する原材料長の最大値が４９０００だから、製品長５３０５０の製品は明らかに得られない。これらは演算対象から除外する。その他の組み合わせについて、上記の演算処理を繰り返す。これにより、原材料の本数の組合せのＮｏ．４で、シンプレックス表の基底変数ｘｉが全て０または１の整数解が得られた。原材料長が、６００００．４００００．４５０００．３００００．４９０００のものを各一本選択すれば、それぞれに切り出す製品全てを割り付けることができる。これにより、原材料長の総和が２２４０００になる。初期実行可能解の原材料長の総和は２３３０００であったから、９０００だけ、原材料を節約できる割付パターンを見つけることができた。この列挙した組み合わせを示すデータを、部材割付データとして出力し、端末装置に送信する。
（シンプレックス演算処理）
以下、さらに具体的に、シンプレックス演算処理の過程を説明する。
まず、初期実行可能解の目的関数の値の最大値と最小値とを定める方法から説明する。
始めに、既知の任意の方法で求めた初期実行可能解をシンプレックス演算処理手段２９にセットする。これを、例えば、以下のような取り合わせとする。単位は０．１ｍｍ（ミリメートル）である。これは、図６で説明したものと変わらない。
以下、さらに具体的に、シンプレックス演算処理の過程を説明する。
まず、初期実行可能解の目的関数の値の最大値と最小値とを定める方法から説明する。
始めに、既知の任意の方法で求めた初期実行可能解をシンプレックス演算処理手段２９にセットする。これを、例えば、以下のような取り合わせとする。単位は０．１ｍｍ（ミリメートル）である。これは、図６で説明したものと変わらない。
原材料長４５０００から製品４４３５０をとる。
原材料長４９０００から製品３０７００と１７８４０をとる。
原材料長４９０００から製品２６２５０と２１０５０をとる。
原材料長６００００から製品５３０５０をとる。
原材料長３００００から製品１７１５０をとる。
原材料長４９０００から製品３０７００と１７８４０をとる。
原材料長４９０００から製品２６２５０と２１０５０をとる。
原材料長６００００から製品５３０５０をとる。
原材料長３００００から製品１７１５０をとる。
シンプレックス演算処理手段２９には、図６に示したとおりの、初期値を設定する。
ｆｉ（ｆ１〜ｆ５）は、最上段の横方向に５個配列した原材料長である。
ｘ１〜ｘ５は全て「１」である。
左側の列には、製品長が７種類、長い物から順に並べてある。
その右側の７行５列（全て１または０）の数値が、割付けパターン行列Ａである。
ｆｉ（ｆ１〜ｆ５）は、最上段の横方向に５個配列した原材料長である。
ｘ１〜ｘ５は全て「１」である。
左側の列には、製品長が７種類、長い物から順に並べてある。
その右側の７行５列（全て１または０）の数値が、割付けパターン行列Ａである。
ここで、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）および、０≦ｘｉ≦１と設定して、シンプレックス演算処理手段２９を起動する。
シンプレックス演算処理手段２９は条件を満たす実行可能解を求めるように動作する。初期設定が実行可能解であるから、必ず初期設定どおりの初期解を出力する。
この演算処理の解は、ｘ＝（１，１，１，１，１）T
である。
即ち、（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）T
＝（１，１，１，１，１）T
である。
また、目的関数値は２３３０００である。上記の初期値のｆｉを集計した値である。
これは、目的関数の値の最大値である。他に実行可能解がみつからない場合には、初期設定値が最適値となる。
この演算処理は、シンプレックス乗数πを求めるために行われる。これは予備処理である。
シンプレックス演算処理手段２９は条件を満たす実行可能解を求めるように動作する。初期設定が実行可能解であるから、必ず初期設定どおりの初期解を出力する。
この演算処理の解は、ｘ＝（１，１，１，１，１）T
である。
即ち、（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）T
＝（１，１，１，１，１）T
である。
また、目的関数値は２３３０００である。上記の初期値のｆｉを集計した値である。
これは、目的関数の値の最大値である。他に実行可能解がみつからない場合には、初期設定値が最適値となる。
この演算処理は、シンプレックス乗数πを求めるために行われる。これは予備処理である。
このシンプレックス乗数に基づき、初期解を改善できる割付けパターンベクトル群を選択することができる。即ち、考えられる割付けパターンベクトルは多数あるが、この処理で、そのうち、初期解を改善する可能性のある割付けパターンベクトルだけを追加することができる。初期解を改善するというのは、目的関数Σｆi・ｘiの値をより小さくできるということである。
その結果、１３種類の割付けパターンベクトルを追加することができる。例えば、１０番目の割付けパターンベクトルは、図６では、ｘ１０および原材料長４０００という表示の下側の縦方向の列（００００１０１）T
である。これにより、新たな７行１８列の割付けパターン行列Ａがシンプレックス演算処理手段２９に設定される。
である。これにより、新たな７行１８列の割付けパターン行列Ａがシンプレックス演算処理手段２９に設定される。
今度は、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）とし、ｘiは０≦ｘi≦１というように条件を緩和して、シンプレックス演算処理手段２９を起動する。
シンプレックス演算処理手段２９は、ピボット演算処理により、割付けパターン行列Ａの中からいずれかの割付けパターンを選択して、上記の条件を満たす解、即ち、実行可能解を求める。ｘiの条件を緩和したから、ｘiが０．５という値を含む実行可能解が得られる。ｘiが全て０または１の整数である解を整数解と呼び、いずれかのｘiが０でも１でもない解のことを非整数解と呼ぶことにする。
シンプレックス演算処理手段２９は、ピボット演算処理により、割付けパターン行列Ａの中からいずれかの割付けパターンを選択して、上記の条件を満たす解、即ち、実行可能解を求める。ｘiの条件を緩和したから、ｘiが０．５という値を含む実行可能解が得られる。ｘiが全て０または１の整数である解を整数解と呼び、いずれかのｘiが０でも１でもない解のことを非整数解と呼ぶことにする。
シンプレックス演算処理手段２９は、目的関数Σｆi・ｘiの値を小さくするようにピボット演算処理を実行する。そして、実行可能解を求めてその結果を出力する。出力された実行可能解で整数解が得られていれば、それは最適値である。従って、その後の処理にはすすまずに、演算処理を終了する。
一方、出力された実行可能解で非整数解が得られたときは、そのときの目的関数Σｆi・ｘiの値を次の演算処理に使用する。即ち、図７の例では、このときの解は、原材料長４００００と４９０００と４５０００とをそれぞれ０．５本使用するというもので、目的関数Σｆi・ｘiの値は２２１０００である。これを下限値とする。その結果は図７に示したとおりである。以上で、目的関数の値の最大値と最小値とを求めることができた。
一方、出力された実行可能解で非整数解が得られたときは、そのときの目的関数Σｆi・ｘiの値を次の演算処理に使用する。即ち、図７の例では、このときの解は、原材料長４００００と４９０００と４５０００とをそれぞれ０．５本使用するというもので、目的関数Σｆi・ｘiの値は２２１０００である。これを下限値とする。その結果は図７に示したとおりである。以上で、目的関数の値の最大値と最小値とを求めることができた。
上記の演算処理で、目的関数の値の最大値２３３０００と最小値２２１０００との間を探索して、最適値を求めればよいという方針ができた。そこで、この範囲に含まれる原材料の組み合わせを求める。下式の条件を満たせばよい。
２２１０００≦Σｆi・ｘi＜２３３０００
Σｆi・ｘiが小さいほどよいから、組み合わせた原材料の長さの総和が少ないものから順位を付ける。そして、この順番に次の演算処理を実行する。特許文献２は、このようにして探索範囲を狭めて、演算処理時間を短縮する技術を示した。
２２１０００≦Σｆi・ｘi＜２３３０００
Σｆi・ｘiが小さいほどよいから、組み合わせた原材料の長さの総和が少ないものから順位を付ける。そして、この順番に次の演算処理を実行する。特許文献２は、このようにして探索範囲を狭めて、演算処理時間を短縮する技術を示した。
次に、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）とし、ｘiは０≦ｘi≦１とし、さらに、原材料の組み合わせが一定という制約条件（Cｘ＝ｄ）を追加して、シンプレックス演算処理手段２９を起動する。割付パターン行列Cは前回と同様の７行１８列である。例えば、最初は原材料の長さの総和が２２２０００から演算処理を開始する。このときの原材料の組み合わせは、６００００が０本、４９０００が３本、４５０００が１本、４００００が０本、３００００が１本である。
ｄは５行１列で（０，３，１，０，１）T
という内容になる。
ｄは５行１列で（０，３，１，０，１）T
という内容になる。
なお、この例では、目的関数の最小値２２１０００と等しくなる原材料の組み合わせが存在しないので、原材料の長さの総和が２２２０００から演算処理を開始する。シンプレックス演算処理手段２９は、１８種類の割付パターンベクトルの中から、制約条件を満たす実行可能解を求める。
（評価式）
ところで、実際には、例えば、製品の種類が３８種類で各１本、原材料長の種類は３種類といった場合に、割付けパターンベクトルの数は５２６個になる。また、原材料長の種類が１種類であっても、製品の種類が２００種類になると、割付けパターンベクトルの数は４２４７個になる。このような場合に、上記の条件でシンプレックス演算処理手段２９による演算処理を実行させると、数千回とか数十万回のピボット演算を繰り返して実行可能解を求める処理をすることになる。
ところで、実際には、例えば、製品の種類が３８種類で各１本、原材料長の種類は３種類といった場合に、割付けパターンベクトルの数は５２６個になる。また、原材料長の種類が１種類であっても、製品の種類が２００種類になると、割付けパターンベクトルの数は４２４７個になる。このような場合に、上記の条件でシンプレックス演算処理手段２９による演算処理を実行させると、数千回とか数十万回のピボット演算を繰り返して実行可能解を求める処理をすることになる。
ある製品を１個切り出すために最も経済的な原材料長は一意的に求められる。複数の製品を組み合わせて切り出すために最も経済的な原材料長も一意的に求められる。既に説明したＬp・ａj≦Ｌの式を満たす最も経済的な原材料長を求めればよい。即ち、原材料長と製品長とが決まれば、全ての場合の割付けパターンベクトルを自動的に生成することができる。原材料長と割付けパターンベクトルの組み合わせに重複はない。シンプレックス演算処理手段２９は、制約条件を満たす割付けパターンベクトルの組み合わせを、重複を避けながら総当たり的に探索する。従って、割付けパターンベクトルの数を最小限に絞り込むことができれば、演算処理時間を短縮できる。一方、例えば、後で説明するように、シンプレックス乗数に基づいて、割付けパターンベクトルの数を絞り込むことができる場合もある。
また、シンプレックス演算処理手段２９は、制約条件を満たす割付けパターンベクトルの組み合わせを、既知のシンプレックスタブローを使用したピボット演算により、探索する。使用する原材料の組み合わせが一定という制約条件を与えると、シンプレックス演算処理手段２９は、割付けパターンベクトルの組み合わせを少しずつ変更しながら、ｘの値が制約条件を満たす実行可能解を見付ける。このピボット演算の過程で得られる非整数解の出現順に規則性はない。ピボット演算開始時の初期条件が異なると、全く異なる過程でピボット演算が実行され、非整数解の出現順も変わる。最短時間で整数解に到達する最適な初期条件を見付ける方法は無い。運の悪いときには何万回ピボット演算を繰り返しても整数解が得られないことがある。
整数解が得られる前に、複数の非整数解が得られることもある。多数の非整数解が得られても、最後まで整数解が得られないこともある。最後まで整数解が得られなかったときは、条件設定をした原材料の組み合わせで最適解は無いということである。実施例２では、ピボット演算の繰り返し回数がＷ回に達したときに探索を打ち切って、別の原材料の組み合わせを選択するようにした。しかしながら、非整数解が出力されたときのシンプレックスタブローから得られる相対費用係数を監視すると、探索方針を決めることができる。相対費用係数が全部正の数になったときには、これ以上、実行可能解は無いと判断してよい。また、相対費用係数に一つでも０（ゼロ）が含まれていれば、実行可能解が他にもあると判断できる。従って、探索を続行するとよい。既出の実行可能解が出力されたときには全ての場合について演算処理を終了したと判断してよい。
しかしながら、割付けパターンベクトルの数が多い場合や、原材料の組み合わせの種類が多い場合には、シンプレックス演算処理手段２９による演算処理時間が膨大になるおそれがある。そこで、本発明では、複数の非整数解が得られたときに、以下に定義する評価式を用いて、その後の演算処理の結果を予測する。即ち、ピボット演算処理の結果、複数の非整数解が得られたとき、これらの非整数解を特定の評価式を適用して比較し、一定の判定基準を満たす場合にはピボット演算処理を続行する。判定基準を満たさない場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開する。また、あるいは、同一制約条件での演算処理を中止し、別の原材料の組み合わせを制約条件に設定する。
図１に示した評価式５４は、Σｆ（ｘｉ）と定義したデータである。Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最大値が一定値になる関数である。例えば、ｆ（ｘｉ）はｘｉのｎ乗（ｎ＞１）と定義することができる。また、あるいは、Σｆ（ｘｉ）は、ｘｉが前記制約条件を満たしながら０から１までの間の数値をとるとき、その最小値が一定値になる関数である。例えば、ｆ（ｘｉ）はｓｉｎπｘｉとか、あるいは、ｆ（ｘｉ）はｘｉのｎ乗（０＜ｎ＜１）というように定義することができる。
図１０は、評価式の意味の説明図である。
ｆ（ｘｉ）をｘｉの２乗と定義して、評価式の意味を説明する。この評価式は、複数の非整数解が得られたときに、原材料の使用本数ベクトルｘの要素ｘiの値の変化を観察するためのものである。即ち、それぞれの解に含まれる全てのｘiが整数に近づく方向にピボット演算が進んでいるかを判定することができる。概略的には、次のような理論になる。
ｆ（ｘｉ）をｘｉの２乗と定義して、評価式の意味を説明する。この評価式は、複数の非整数解が得られたときに、原材料の使用本数ベクトルｘの要素ｘiの値の変化を観察するためのものである。即ち、それぞれの解に含まれる全てのｘiが整数に近づく方向にピボット演算が進んでいるかを判定することができる。概略的には、次のような理論になる。
例えば、使用本数ｘ＝（ｘ１、ｘ２）とする。また、原材料の組み合わせＣを（１、１）とする。前者は列ベクトル、後者は行ベクトルである。（Cｘ＝ｄ）だから、ｘ１＋ｘ２＝１である。この場合、図１０（ａ）に示すように、ｘ１軸とｘ２軸の直交座標上で、ｘ１軸の切辺の座標が１でｘ２軸の切辺の座標が１の直線上に実行可能解があるということができる。直線の両端の白丸は整数解、中央の黒丸は非整数解になる。（ｂ）には、縦軸に評価式の値を示し、横軸にｘ１とｘ２の値を示した。
図１０の（ｂ）に示したのは使用本数ベクトルｘの要素がｘ１とｘ２の場合の解空間である。評価式の最大値は１、最小値は０．５である。ベクトルｘの要素数が増えると解空間はこの図よりもさらに複雑になる。しかも、ピボット演算により求められる非整数解や整数解の出力順序も複雑である。従って、ある条件でピボット演算を開始して、順番に出力される実行可能解により得られる整数解あるいは非整数解の評価式の値は、図１０（ｃ）に示すように変遷する。黒丸が非整数解によるもので、白丸が整数解によるものである。
ここで、例えば、シンプレックス演算処理手段２９による演算処理が開始されて、所定のタイミングで、実行可能解Ｒ１が得られたとする。さらにその後、実行可能解Ｒ２が得られたとする。いずれも非整数解である。両者の評価式の値を比較すると、後から得られた非整数解の値が減少している。ここでさらにピボット演算を続行しても、評価式の値は減少していき、すぐに整数解には近づかないと判定する。そこで、このタイミングで初期条件を変更する。即ち、ピボット演算の開始点を変更する。
この演算処理では、目的関数をΣｆi・ｘiとし、制約条件を（Ａｘ≧ｂ）とし、ｘiは０≦ｘi≦１とし、さらに、原材料の組み合わせが一定という制約条件（Cｘ＝ｄ）を追加して、シンプレックス演算処理手段２９を起動した。割付けパターンベクトルと制約条件は変えられない。一方、本発明の方法では、制約条件（Cｘ＝ｄ）に費用係数の値が含まれないようにし、かつ、基底変数も使用本数ベクトルｘを使用したから、費用係数ｆiの値を変更しても解に直接影響がない。しかも、目的関数に含まれる費用係数ｆiの値を変更すると、ピボット演算の開始点や順序を変えることができる。例えば、仮に、費用係数ｆiの値を全て０にして演算処理を開始しても、費用係数ｆiの値を全て１にして、演算処理を開始しても、最終的には同じ結果が得られる。ところが、ピボット演算の過程は相異する。即ち、シンプレックス演算処理手段２９に対して、こうした変更可能な設定条件を変更することで、図１０（ｃ）の実行可能解Ｒ２が得られた時点でピボット演算を停止し、今度はタイミングｔ１からピボット演算を再開することができる場合がある。もちろん、他の任意の方法でピボット演算開始のための初期条件を変更できればよい。
タイミングｔ１からピボット演算を再開すると、その後、実行可能解Ｒ３が得られる。さらにその後、実行可能解Ｒ４が得られたとする。いずれも非整数解である。ここで、両者の評価式の値を比較すると、その値が増加している。このとき、さらにピボット演算を続行すれば、評価式の値は増加していき、整数解に近づく可能性が高いと判定する。こうした判断を、図１に示した判定手段３１が実行する。図１０（ｃ）の例では、その後無事に白丸で示した整数解に到達することができる。
しかしながら、実際には、同じ設定条件で演算処理を続行しても、必ず整数解が得られるとは限らない。従って、例えば、評価式の値が増加した後に整数解が得られないまま減少し始めたら、極大値を通過したものと判断して、別の上昇曲線を求めて設定条件を変更するとよい。例えば、費用係数ｆiの値を全て０の状態から全て１の状態まで順番に切り替えて、ピボット演算を繰り返せばよい。
以上の処理により、複数の非整数解が得られたときに、その後ピボット演算を続行しても良い結果が得られないと判断したら、その状態を回避し、別の条件からピボット演算を開始するようにして、演算処理時間を短縮することができる。また、例えば、初期条件を変更しても評価式の値が増加する傾向がみられない場合には、この制約条件での整数解は無いと判断して、原材料の組み合わせの制約条件（Cｘ＝ｄ）を変更して、演算処理を再開するとよい。
評価式の値が増加していく場合にのみピボット演算を続行するのは、既知の局所探索法でいう山登り法と呼ぶことができる。そして、ランダムに初期条件を変更するのをランダムリスタート法と呼ぶことができる。さらに、上記の評価式を利用して、既知の焼き鈍し法により、整数解を探索することができる。また、非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときピボット演算を続行する方法も有効である。以上のように判定基準を定めて、図１に示した判定手段３１が、ピボット演算を続行するかどうかの判定をする。図１に示した探索制御手段３０は、この判定手段の判定に従って、探索を制御する。
（動作フロー）
図１１は、本発明の主要動作のフローチャートである。
この図を用いて、評価式を使用した演算処理の具体的な手順を説明する。まず、図のステップＳ５１では、原材料本数の組み合わせを選択する。次に、ステップＳ５２で、上記の制約条件式を用いた制約条件の設定をする。ステップＳ５３では、初期条件の設定をする。この初期条件とは、ピボット演算の開始時の条件のことで、例えば、費用係数を全てゼロに設定する。ステップＳ５４でシンプレックス演算処理を起動する。ステップＳ５５では、ピボット演算を実行する。ピボット演算を繰り返してステップＳ５６で、実行可能解の出力をする。ステップＳ５７では、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから処理を終了する。ノーのときはステップＳ５８の処理に移行する。
図１１は、本発明の主要動作のフローチャートである。
この図を用いて、評価式を使用した演算処理の具体的な手順を説明する。まず、図のステップＳ５１では、原材料本数の組み合わせを選択する。次に、ステップＳ５２で、上記の制約条件式を用いた制約条件の設定をする。ステップＳ５３では、初期条件の設定をする。この初期条件とは、ピボット演算の開始時の条件のことで、例えば、費用係数を全てゼロに設定する。ステップＳ５４でシンプレックス演算処理を起動する。ステップＳ５５では、ピボット演算を実行する。ピボット演算を繰り返してステップＳ５６で、実行可能解の出力をする。ステップＳ５７では、整数解かどうかという判断をする。この判断の結果がイエスのときは最適解であるから処理を終了する。ノーのときはステップＳ５８の処理に移行する。
ステップＳ５８では、ピボット演算の終了かどうかという判断をする。これは、既に説明したように、実行可能解が無いと判断された場合である。この判断の結果がイエスのときは最初のステップＳ５１の処理に移行し、制約条件の再設定を行う。ノーのときはステップＳ５９の処理に移行する。ステップＳ５９では、非整数解を評価式に当てはめる演算処理をする。ステップＳ５９〜６１の演算は判定手段３１（図１）が実行する。ステップＳ６０では、評価式の値の履歴を比較して判定をする。即ち、例えば、前回の非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。また、数回連続して得られた非整数解について、演算をした評価式の値を記憶装置に記憶させておき、今回のものと比較する。ステップＳ６１では、既に説明したような判定基準を使用して、ピボット演算を続行するかどうかという判断をする。この判断の結果がイエスのときはステップＳ５６の処理に移行して、ステップＳ５６〜６１を繰り返す。一方、ノーのときはステップＳ６２の処理に移行して、費用係数の変更をする。そして、ステップＳ５４に戻る。即ち、新たな初期条件で、ピボット演算を再開する。
図１２は、ピボット演算を１５５回繰り返したときの、割付パターンベクトルと使用本数ベクトルの関係を示す説明図である。図１３は、その過程での非整数解と整数解の具体例説明図である。
シンプレックス演算処理手段２９によるピボット操作を最初から数えて１５５回繰り返して、図の第１の実行可能解を得た。
その非整数解は、ｘ２７の割り付けパターンの材料が１本、ｘ１７の割り付けパターンの材料が０．５本、ｘ８８の割り付けパターンの材料が０．５本・・・というような内容である。
ここで、Σｆ（ｘｉ）を計算する。使用本数ベクトルに、１が１６個，０．５が１２個含まれている。従って、Σｆ（ｘｉ）は１９である。
さらに、シンプレックス演算処理手段２９によるピボット操作を繰り返すと、最初から数えて１５７回目に新たな実行可能解を得た。上記の１５５回目も１５６回目も非整数解が得られたが、その評価式による値は増加し続けた。従って、上記の判定手段の判定により、ピボット演算を続行した。
シンプレックス演算処理手段２９によるピボット操作を最初から数えて１５５回繰り返して、図の第１の実行可能解を得た。
その非整数解は、ｘ２７の割り付けパターンの材料が１本、ｘ１７の割り付けパターンの材料が０．５本、ｘ８８の割り付けパターンの材料が０．５本・・・というような内容である。
ここで、Σｆ（ｘｉ）を計算する。使用本数ベクトルに、１が１６個，０．５が１２個含まれている。従って、Σｆ（ｘｉ）は１９である。
さらに、シンプレックス演算処理手段２９によるピボット操作を繰り返すと、最初から数えて１５７回目に新たな実行可能解を得た。上記の１５５回目も１５６回目も非整数解が得られたが、その評価式による値は増加し続けた。従って、上記の判定手段の判定により、ピボット演算を続行した。
一方、原材料の種類を一種とし、製品の種類を２００種としたとき、割付パターンベクトルは４２４７種類生成された。同様にしてシンプレックス演算処理を実行させたところ、最初の実行可能解を得るまでに１７８３回のピボット演算が行われた。評価式を使用しないで、そのままピボット演算を続行したところ、４４３１８３回までピボット演算をしても、整数解は得られなかった。一方、上記の評価式を使用して探索を実行したところ、９４８０８回までピボット演算をして、整数解を得ることができた。即ち、本発明の方法により、十分に演算処理時間を短縮できることがわかった。
図１４は、部材加工装置のブロック図である。
以上の処理により、部材割付データ５３が得られた。これは、プレカット工場でプレカット装置１７に供給される。原材料は図１４に示した順に選択されて、対応する割付パターンで切り分けられ、製品が得られる。この実施例では、初期実行可能解の場合の歩留まりが０．９０３であったものが、改善後に０．９３９になった。大量の原材料に大量の製品を割り付けて切り出すプレカット工場では、このように、約１％の歩留まり改善ができただけで多額のコストダウンが可能になる。また、廃棄物量を１％減少させることができれば、廃棄物処理のための設備や費用も節約することができる。上記の例では、原材料の種類や要求される製品の種類や量を単純化したが、多種多様の原材料と製品とを取り扱えばさらに従来法では到達できなかったレベルまで大幅な歩留まりの改善を見込むことができる。
以上の処理により、部材割付データ５３が得られた。これは、プレカット工場でプレカット装置１７に供給される。原材料は図１４に示した順に選択されて、対応する割付パターンで切り分けられ、製品が得られる。この実施例では、初期実行可能解の場合の歩留まりが０．９０３であったものが、改善後に０．９３９になった。大量の原材料に大量の製品を割り付けて切り出すプレカット工場では、このように、約１％の歩留まり改善ができただけで多額のコストダウンが可能になる。また、廃棄物量を１％減少させることができれば、廃棄物処理のための設備や費用も節約することができる。上記の例では、原材料の種類や要求される製品の種類や量を単純化したが、多種多様の原材料と製品とを取り扱えばさらに従来法では到達できなかったレベルまで大幅な歩留まりの改善を見込むことができる。
なお、使用原材料長の総和の最小値を求めるために、最初に、第１制約条件式と第３制約条件式の制約条件の下でシンプレックス演算処理を実行した。このとき、非整数解を伴う実行可能解が得られたら、そのときの目的関数値を使用原材料長の総和の最小値に設定した。しかしながら、上記のように、同一制約条件の下で、非整数解が複数回得られることがある。そこで、別の新たな非整数解が得られる可能性があり、原材料の本数を組み合わせて、その目的関数値と等しくなる組合せがある限り、その制約条件下で、シンプレックス演算処理を繰り返すことが好ましい。
上記の演算処理装置で実行されるコンピュータプログラムは、機能ブロックで図示した単位でモジュール化されてもよいし、複数の機能ブロックを組合せて一体化されてもよい。また、上記のコンピュータプログラムは、既存のアプリケーションプログラムに組み込んで使用してもよい。本発明を実現するためのコンピュータプログラムは、例えばＣＤ−ＲＯＭのようなコンピュータで読み取り可能な記録媒体に記録して、任意の情報処理装置にインストールして利用することができる。
１０ 部材割付システム
１２ コンピュータ
１４ ネットワーク
１６ 端末装置
２０ 演算処理装置
２１ 製品長設定手段
２２ 原材料長設定手段
２３ 初期設定手段
２４ 割付パターンベクトル生成手段
２５ 割付パターン行列生成手段
２６ 制約条件生成手段
２７ 費用計数係数ベクトル生成手段
２８ 目的関数生成手段
２９ シンプレックス演算処理手段
３０ 探索制御手段
３１ 判定手段
４０ 記憶装置
４１ 製品長ベクトルLp
４２ 製品要求数量ベクトルｂ
４３ 原材料長ベクトルLm
４４ 初期実行可能解
４５ 原材料使用予定数量ベクトルｄ
４６ 割付パターン行列
４６ａ 割付パターンベクトル
４７ 原材料使用行列Ｃ
４８ 第１制約条件式
４９ 第２制約条件式
５０ 第３制約条件式
５１ 目的関数
５２ 組合せリスト
５３ 部材割付データ
５４ 評価式
１２ コンピュータ
１４ ネットワーク
１６ 端末装置
２０ 演算処理装置
２１ 製品長設定手段
２２ 原材料長設定手段
２３ 初期設定手段
２４ 割付パターンベクトル生成手段
２５ 割付パターン行列生成手段
２６ 制約条件生成手段
２７ 費用計数係数ベクトル生成手段
２８ 目的関数生成手段
２９ シンプレックス演算処理手段
３０ 探索制御手段
３１ 判定手段
４０ 記憶装置
４１ 製品長ベクトルLp
４２ 製品要求数量ベクトルｂ
４３ 原材料長ベクトルLm
４４ 初期実行可能解
４５ 原材料使用予定数量ベクトルｄ
４６ 割付パターン行列
４６ａ 割付パターンベクトル
４７ 原材料使用行列Ｃ
４８ 第１制約条件式
４９ 第２制約条件式
５０ 第３制約条件式
５１ 目的関数
５２ 組合せリスト
５３ 部材割付データ
５４ 評価式
Claims (10)
- それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化するものであって、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、
前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、
前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材割付システム。 - 請求項１に記載の部材割付システムにおいて、
前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最大値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて増加していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。 - 請求項１に記載の部材割付システムにおいて、
前記判定手段は、前記ｘｉが前記制約条件を満たしながら０から１までの間の数値をとり、前記評価式Σｆ（ｘｉ）の値の最小値が一定値になる関数であるとき、
後から得られた非整数解による前記評価式の値が先に得られた非整数解による前記評価式の値に比べて減少していれば、前記判定基準を満たすと判定することを特徴とする部材割付システム。 - 請求項１に記載の部材割付システムにおいて、
順次得られた非整数解による前記評価式の値を焼き鈍し法を用いて比較をする判定基準により判定することを特徴とする部材割付システム。 - 請求項１に記載の部材割付システムにおいて、
非整数解であって局所最適解を通過した場合に、評価式の値がいったん減少してから増加に転じる状態にあるときに前記判定基準を満たすと判定することを特徴とする部材割付システム。 - 請求項１乃至５のいずれかに記載の部材割付システムにおいて、
前記第１制約条件式と第３制約条件式の制約条件の下で、前記シンプレックス演算処理を実行し、非整数解を伴う実行可能解が得られたときであって、別の新たな非整数解を求めるシンプレックス演算処理を繰り返すことを特徴とする部材割付システム。 - それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する手段と、最適化された部材割り付けデータを受け入れて、前記ｍ本の製品を、順次供給される前記ｋ種類の原材料から切り出すプレカット装置とを備え、
求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させる製品長設定手段と、
用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させる原材料長設定手段と、
求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙する割付パターンベクトル生成手段と、
前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させる割付パターン行列生成手段と、
前記割付パターン行列に含まれたｎ個の割付パターンから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させる目的関数生成手段と、
前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする第１制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させる制約条件生成手段と、
任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させる初期設定手段と、
前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するシンプレックス演算手段と、
前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択して、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼し、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、この新たな制約条件で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御する探索制御手段を備え、
前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較する判定手段を備え、
前記探索制御手段は、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開することを特徴とする部材加工装置。 - コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラム。
- コンピュータを、請求項１に記載の各手段として機能させる部材割付プログラムを記録したコンピュータで読み取り可能な記録媒体。
- それぞれ所定の長さのｍ本の製品を、それぞれ所定の長さのｋ種類の原材料から切り出すときに必要な各種類の原材料の本数を求め、各原材料に割り付ける製品の組合せを最適化する方法であって、
製品長設定手段が、求められているｍ本の製品の製品長データの入力を受け付けて、製品長を要素とするｍ次の製品長ベクトルLpと、製品要求数量を要素とする製品要求数量ベクトルｂとを生成して、記憶装置に記憶させるステップと、
原材料長設定手段が、用意されたｋ種類の長さの原材料長データの入力を受け付けて、原材料長を要素とするｋ次の原材料長ベクトルLmを生成し、記憶装置に記憶させるステップと、
割付パターンベクトル生成手段が、求められている前記ｍ本の製品の製品長データと用意された前記ｋ種類の原材料の原材料長データとを比較して、１本または複数本の製品を経済的に割り付けることができる原材料と製品との関係を示す、ｍ次の割付パターンベクトルを列挙するステップと、
割付パターン行列生成手段が、前記割付パターンベクトル生成手段の生成した割付パターンベクトルを並べた割付パターン行列Ａを生成して、記憶装置に記憶させるステップと、
目的関数生成手段が、前記割付パターン行列に含まれたｎ個の割付パターンをから選択して該当する原材料を選択する各要素がｘiの使用本数ベクトルｘを定義し、前記原材料長ベクトルLmに対応するｍ次の費用係数ベクトルと前記使用本数ベクトルｘの積の総和を示す目的関数を生成して、記憶装置に記憶させるステップと、
制約条件生成手段が、前記割付パターン行列Ａから選択されたｎ個の割付パターンで切り出した各製品数は、それぞれ求められている各製品の数量以上でなければならないとする制約条件式Ａｘ≧ｂと使用本数ベクトルｘの各要素ｘiが０≦ｘi≦１であるという緩和した第３制約条件式を生成して、記憶装置に記憶させるステップと、
初期設定手段が、任意の方法で求められた初期実行可能解の入力を受け付けて、記憶装置に記憶させるステップと、
シンプレックス演算手段が、前記初期実行可能解と前記目的関数と前記制約条件式の入力を受け付けて、シンプレックス演算処理を実行するステップと、
探索制御手段が、前記シンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、前記初期実行可能解の目的関数の値を最大値とし、前記シンプレックス演算処理の結果得られた目的関数の値を最小値として、その範囲の目的関数の値をとる原材料の使用本数の組合せを列挙し、その中から目的関数が前記最小値に近いものを選択するステップと、
前記探索制御手段が、前記制約条件生成手段に対して、どの長さの原材料を何本選択して割付けに使用するかを定める、原材料使用行列Ｃと原材料の使用本数ベクトルｘの積が原材料使用予定数量ベクトルｄと等しいとする第２制約条件式Ｃｘ＝ｄの生成を依頼するステップと、
前記探索制御手段が、前記制約条件で、シンプレックス演算手段に演算処理を依頼するステップと、
前記探索制御手段が、その後得られたシンプレックス演算処理により、ｘiの値が０または１のいずれかであって、それ以外のものを含まない解のときは、その解を最適解として部材割付データを出力し、それ以外の場合には、列挙された前記原材料の使用本数の組合せの中から、目的関数が前記最小値に近い次の候補を選択して、前記制約条件生成手段に対して、新たな第２制約条件式Ｃｘ＝ｄの生成を依頼し、前記第１制約条件式と前記第２制約条件式と前記第３制約条件式の制約条件下で、シンプレックス演算手段に演算処理を依頼するという動作を繰り返すように制御するステップと、
判定手段が、前記ｘｉが前記制約条件式を満たしながら０から１までの間の数値をとるとき、その最大値または最小値が一定値になる関数Σｆ（ｘｉ）を評価式に設定して、ピボット演算処理の結果複数の非整数解が得られたとき、これらの非整数解の関係を前記評価式を適用して比較するステップと、
前記探索制御手段が、前記判定手段が一定の判定基準を満たすと判定した場合にはピボット演算処理を続行し、判定基準を満たさないと判定した場合には、ピボット演算処理を開始するときの初期条件を変更してピボット演算処理を再開するステップを含むことを特徴とする部材割付方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2010030975A JP5000735B2 (ja) | 2010-02-16 | 2010-02-16 | 部材割付システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2010030975A JP5000735B2 (ja) | 2010-02-16 | 2010-02-16 | 部材割付システム |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2011170408A JP2011170408A (ja) | 2011-09-01 |
| JP5000735B2 true JP5000735B2 (ja) | 2012-08-15 |
Family
ID=44684505
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2010030975A Expired - Fee Related JP5000735B2 (ja) | 2010-02-16 | 2010-02-16 | 部材割付システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP5000735B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP5983976B1 (ja) * | 2016-01-18 | 2016-09-06 | 株式会社Ｊｌｓ | 部材割付システムと部材割付プログラムと記録媒体と部材加工装置 |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109492800B (zh) * | 2017-11-24 | 2023-05-02 | 华东理工大学 | 一种用于自动化仓库的车辆路径优化方法 |
| JP7147243B2 (ja) * | 2018-04-23 | 2022-10-05 | 日本製鉄株式会社 | スケジュール作成装置、方法及びプログラム |
| JP6890765B2 (ja) * | 2018-06-27 | 2021-06-18 | 株式会社Ｊｌｓ | 部材割付システム |
| JP7526155B2 (ja) * | 2021-10-12 | 2024-07-31 | Ｊｆｅスチール株式会社 | 最適化問題求解装置及び最適化問題求解方法 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3565262B2 (ja) * | 1999-09-20 | 2004-09-15 | 住友林業株式会社 | 部材割付け方法及び部材割付け加工装置 |
| JP4427302B2 (ja) * | 2003-11-12 | 2010-03-03 | 三菱重工業株式会社 | プラント保守計画生成システム、プラント保守計画の生成方法 |
| JP4909869B2 (ja) * | 2007-10-17 | 2012-04-04 | 住友林業株式会社 | 部材割付システム |
-
2010
- 2010-02-16 JP JP2010030975A patent/JP5000735B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP5983976B1 (ja) * | 2016-01-18 | 2016-09-06 | 株式会社Ｊｌｓ | 部材割付システムと部材割付プログラムと記録媒体と部材加工装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2011170408A (ja) | 2011-09-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Alagöz et al. | Rescheduling of identical parallel machines under machine eligibility constraints | |
| Chen et al. | An alternative framework to Lagrangian relaxation approach for job shop scheduling | |
| JPH06202882A (ja) | 複数のタスク及びジョブのスケジューリング方法 | |
| JP5000735B2 (ja) | 部材割付システム | |
| US7552067B2 (en) | System and method supply chain demand satisfaction | |
| CN111861412B (zh) | 面向完成时间优化的科学工作流调度方法及系统 | |
| CN112328395B (zh) | 一种云资源容量规划方法和系统 | |
| JP5838047B2 (ja) | 部材割付システム | |
| CN115689246B (zh) | 用于确定排产计划的方法、装置、存储介质及处理器 | |
| US20180039514A1 (en) | Methods and apparatus to facilitate efficient scheduling of digital tasks in a system | |
| De CM Nogueira et al. | Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties | |
| JP2017514247A5 (ja) | ||
| Das et al. | Workload uncertainty characterization and adaptive frequency scaling for energy minimization of embedded systems | |
| JP4909869B2 (ja) | 部材割付システム | |
| CN103455131B (zh) | 一种基于概率的嵌入式系统中能耗最小化的任务调度方法 | |
| Goux et al. | Solving large MINLPs on computational grids | |
| CN118093126A (zh) | 任务调度方法、装置、系统、服务器及存储介质 | |
| Beaumont et al. | Minimizing weighted mean completion time for malleable tasks scheduling | |
| US20150381520A1 (en) | Data set multiplicity change device, server, data set multiplicity change method and computer redable medium | |
| JP6470209B2 (ja) | サーバ、システム及び探索方法 | |
| Meolic et al. | Flexible job shop scheduling using zero-suppressed binary decision diagrams | |
| CN108268316A (zh) | 作业调度的方法及装置 | |
| JP2009098924A5 (ja) | ||
| CN119166278B (zh) | 一种面向在线训练的算力资源弹性分配系统 | |
| Abouee-Mehrizi et al. | Exact analysis of capacitated two-echelon inventory systems with priorities |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20111206 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20111208 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20120510 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20120516 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 5000735 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20150525 Year of fee payment: 3 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313117 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |