(57)【特許請求の範囲】
【請求項１】
寸法が異なる子材のそれぞれの所要数量を母材から分取するための製造計画作成方法であって、
１又は複数の前記子材及びその数量を定めた複数の組み合わせ候補を形成する第１のステップと、
該第１のステップで形成した組み合わせ候補のうちから、組み合わせ候補に含まれる各子材の数量の比と前記各子材の所要数量の比とが等しい組み合わせ候補、及び両比が近似する組み合わせ候補を選択して対象組み合わせ候補とする第２のステップと、
前記対象組み合わせ候補に対して数理計画法を用いて、対象組み合わせ候補の生成数を算出する第３のステップと
を備えることを特徴とする製造計画作成方法。
【請求項２】
前記第１のステップでは、
母材の幅方向に分取する複数の組み合わせ候補を形成し、
前記第２のステップでは、
それぞれの組み合わせ候補に含まれる各子材の幅の累計が母材幅の上限値以下である組み合わせ候補を前記対象組み合わせ候補として選択すること
を特徴とする請求項１に記載の製造計画作成方法。
【請求項３】
前記第２のステップでは、
それぞれの組み合わせ候補に含まれる各子材の数量に係る第１のベクトル、及び該第１のベクトルの対応ベクトルである前記各子材の所要数量に係る第２のベクトルを組み合わせ候補毎に作成し、
第１のベクトル及び第２のベクトルを正規化し、
正規化された第１のベクトルと第２のベクトルとの内積値を算出し、
算出された内積値が内積閾値以上である組み合わせ候補を前記対象組み合わせ候補として選択すること
を特徴とする請求項１又は２に記載の製造計画作成方法。
【請求項４】
コンピュータに請求項１乃至３の何れか１項の製造計画作成方法を実行させることを特徴とするコンピュータプログラムが記録されている記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、金属帯又は紙帯等の母材から板材又は紙片材等の子材を分取する製造計画を作成する方法、及びそのコンピュータプログラムが記録してあるコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
コイルから引き出した金属帯、又はロールから引き出した紙帯等の母材から、種々の注文に応じた寸法の製品（子材）を切り出す計画を作成する場合、各注文の寸法の製品の数量が注文数量を満足すると共に、注文数量を越えて製造される製品の数量を可及的に低減することが重要である。
【０００３】
図６は切り出し計画を説明する説明図である。いま、長さが同じで、幅が異なる板材に係る複数の注文Ａ（７枚），注文Ｂ（３枚），注文Ｃ（７枚），…（幅寸法：注文Ａ＜注文Ｂ＜注文Ｃ＜…）があるとすると、各注文に対応する１又は複数の製品を組み合わせ、それを母材Ｓの幅方向へ１列に配して組み合わせパターンとし、全ての注文を満足するように、同じ組み合わせパターン又は異なる組み合わせパターンを母材Ｓの長手方向へ生成する。
【０００４】
例えば図６のように、注文Ａに対する製品Ａを母材Ｓの幅方向へ３つ配した組み合わせパターンを１列、注文Ｂに対応する製品Ｂ及び製品Ａを１つずつ母材Ｓの幅方向へ配した組み合わせパターンを４列、注文Ｃに対応する製品Ｃを１つ母材Ｓの幅方向へ配した組み合わせパターンを７列、母材Ｓの長手方向へ生成するという切り出し計画を作成した場合、注文Ｂの注文数は３枚であるにも拘らず、製品Ｂは４枚製造されるため、製品Ｂが１枚だけ過剰に製造されることになる。切り出し計画とは、この過剰製品数量を最小にすると共に全注文を満足するように、製品の組み合わせパターン及び各組み合わせパターンの生成数を決定することである。
【０００５】
このような切り出し計画を数理計画法を用いて作成すべく、ピー．シー．ギルモア（P.C.Gilmore ）、及びアール．イー．ゴモリー（R.E. Gomory ）らは、「切断在庫品問題に対する線型計画法によるアプローチ」（“オペレーションズリサーチ”、第９巻、１９６１年、８４９〜８５９ページ）に、次のような方法を提案している。
【０００６】
即ち、過剰製品数量を最小にする最適な製品の組み合わせパターン及び各組み合わせパターンの生成数を求めるという最適化問題に帰着して、切り出し計画を次の（１−１）式〜（１−３）式で表す。
ｍｉｎ．ｃｘ                  …（１−１）
ｓ．ｔ．Ａｘ≧ｂ              …（１−２）
ｘ≧０  かつ  整数    …（１−３）
但し、ｃ：ｃj を要素とする行ベクトル
ｘ：ｘj を要素とする列ベクトル
Ａ：Ａijを要素とするｉ×ｊ行列
ｂ：ｂi を要素とする列ベクトル
但し、ｉ：受注した製品の種類
ｊ：組み合わせ候補
ｘj ：組み合わせ候補ｊの生成数
Ａij：製品ｉの組み合わせ候補ｊの１単位に含まれる数量
ｂi ：製品ｉの受注数量
ｃj ：組み合わせ候補ｊの１単位に含まれる製品の総数量
【０００７】
上式に含まれる製品ｉの組み合わせ候補ｊの１単位に含まれる数量Ａij（以下数量Ａijともいう）を、次のようにして算出する。（１−２）式及び（１−３）式で表される制約条件を充足するように、数量Ａijを対角行列で作成し、それをA1とする。また、（１−３）式の制約条件から整数の条件を取り除く。このとき、前述した（１−１）式〜（１−３）は次の（２−１）式〜（２−３）式で表される。
ｍｉｎ．ｃｘ                  …（２−１）
ｓ．ｔ．A1ｘ≧ｂ              …（２−２）
ｘ≧０                …（２−３）
【０００８】
（２−１）式〜（２−３）式で表される問題は線型計画問題である。線型計画問題の求解方法に従って（２−１）式〜（２−３）式を解くことによって双対変数行ベクトルｄを得、得られた双対変数行ベクトルｄを用いて、次の（４）式を満たす組み合わせ候補のベクトルａ（以下ベクトルａともいう）を探索する。これによって、目的関数ｃｘの値をより小さくするベクトルａを求めることができる。
ｃj −ｄａ＜０                …（４）
但し、ｃj ：組み合わせ候補ａがもつ目的関数
【０００９】
ベクトルａは、例えば次の（５）式及び（６）式を用いて探索する。
ｍｉｎ  Ｚ＝ｃj −ｄ          …（５）
ｓ．ｔ．ａ∈Ｘ                …（６）
但し、Ｘ：制約条件を充足する組み合わせ候補の集合
上記Ｚが負になるまで（５）式及び（６）式を解き、Ｚが負になったときのベクトルａを得、該ベクトルａを列ベクトルとしてA1に加える。
【００１０】
そして、次の（３−１）式〜（３−４）式で表される問題を解き、得られた双対変数行ベクトルｄを用いて、前同様、（４）式を満たす組み合わせ候補のベクトルａを探索する。このような操作を（４）式を満たす組み合わせ候補のベクトルａが探索し得なくなるまで繰り返す。
ｍｉｎ．ｃｘ                  …（３−１）
ｓ．ｔ．A2ｘ≧ｂ              …（３−２）
A2＝［A1｜ａ］        …（３−３）
ｘ≧０                …（３−４）
【００１１】
また、他の方法として、本発明者らは、「ロール及び長ストリップ材に係る最小製造量制約を伴う切断在庫品問題に対するＭＩＰに基づくアプローチ」（ＡＰＭＳ、第９６巻、１９９６年、６０３〜６０８ページ）に、次のような方法を提案している。
【００１２】
受注した注文に係る全ての組み合わせを生成し、生成した各組み合わせについて、整数条件を緩和した、次の（７−１）式〜（７−３）式で表される問題を線型計画問題の求解方法に従って解いて、採用する組み合わせ及びその組み合わせの生成数を実数で算出する。そして、得られた各生成数の値が整数でないものについて、小数点以下を切り上げる丸め処理を施すことによって製品の切り出し計画を作成する。
ｍｉｎ．ｃｘ                  …（７−１）
ｓ．ｔ．Ａｘ≧ｂ              …（７−２）
ｘ≧０                …（７−３）
【００１３】
【発明が解決しようとする課題】
上述した２つの従来の方法の内の前者の方法では、組み合わせ候補を全て生成することなく求解することができるものの、（６）式で用いる制約条件が複雑になるに従って、各制約条件を表す数式を作成することが困難になると共に、ベクトルａの探索に長時間を要するため実用的な時間内に製造計画を作成することができない。一方、後者の方法では、組み合わせ候補を全て生成し、整数条件を緩和した（７−１）〜（７−３）式で表される問題を解くことによって、製造計画を実用的な時間内に作成することができるものの、整数条件を緩和して求めた組み合わせ候補を用いるため、製造計画の信頼性を向上させるには限界があった。
【００１４】
本発明はかかる事情に鑑みてなされたものであって、その目的とするところは寸法が異なる子材のそれぞれの所要数量を母材から分取するために、１又は複数の前記子材及びその数量を定めた複数の組み合わせ候補を形成し、複数の組み合わせ候補の中から対象組み合わせ候補を選択し、その対象組み合わせ候補の生成数を数理計画法を用いて算出する場合に、組み合わせ候補に含まれる各子材の数量の比と前記各子材の所要数量の比とが等しい組み合わせ候補、及び両比が近似する組み合わせ候補を前記対象組み合わせ候補として選択することによって、実用的な時間内に高い信頼性の計画を作成することができる製造計画作成方法、及びそのプログラムが記録してあるコンピュータ読み取り可能な記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
第１発明に係る製造計画作成方法は、寸法が異なる子材のそれぞれの所要数量を母材から分取するための製造計画作成方法であって、１又は複数の前記子材及びその数量を定めた複数の組み合わせ候補を形成する第１のステップと、該第１のステップで形成した組み合わせ候補のうちから、組み合わせ候補に含まれる各子材の数量の比と前記各子材の所要数量の比とが等しい組み合わせ候補、及び両比が近似する組み合わせ候補を選択して対象組み合わせ候補とする第２のステップと、前記対象組み合わせ候補に対して数理計画法を用いて、対象組み合わせ候補の生成数を算出する第３のステップとを備えることを特徴とする。
【００１６】
第２発明に係る製造計画作成方法は、前記第１のステップでは、母材の幅方向に分取する複数の組み合わせ候補を形成し、前記第２のステップでは、それぞれの組み合わせ候補に含まれる各子材の幅の累計が母材幅の上限値以下である組み合わせ候補を前記対象組み合わせ候補として選択することを特徴とする。
【００１７】
第３発明に係る製造計画作成方法は、前記第２のステップでは、それぞれの組み合わせ候補に含まれる各子材の数量に係る第１のベクトル、及び該第１のベクトルの対応ベクトルである前記各子材の所要数量に係る第２のベクトルを組み合わせ候補毎に作成し、第１のベクトル及び第２のベクトルを正規化し、正規化された第１のベクトルと第２のベクトルとの内積値を算出し、算出された内積値が内積閾値以上である組み合わせ候補を前記対象組み合わせ候補として選択することを特徴とする。
【００１８】
第４発明に係る記録媒体は、コンピュータに前記第１発明乃至第３発明の何れか１つの製造計画作成方法を実行させるコンピュータプログラムが記録されていることを特徴とする。
【００１９】
本発明にあっては、例えば、第１〜第１０までの製造番号が付された寸法が異なる子材を５枚ずつ製造する場合、（第１，第２，…，第１０）＝（１，０，…，０）、（１，１，…，０）、…、（４，１，…，０）、…、（５，５，…，５）というような複数のパターンを形成する。これらのパターンから、そのパターンに含まれる各子材の数量の比と、各子材の所要数量の比とが等しい又は近似するパターンを選択する。
【００２０】
例えば、（１，１，…，０）のパターンに含まれる子材の数量の比は、第１要素の数量／第２要素の数量＝１／１＝１であり、第１子材の所要数量／第２子材の所要数量＝５／５＝１であるので、両比は等しく、従って（１，１，…，０）のパターンを選択する。一方、（４，１，…，０）のパターンに含まれる子材の数量の比は、第１要素の数量／第２要素の数量＝４／１＝４であり、第１子材の所要数量／第２子材の所要数量＝５／５＝１であるので、両比は近似しておらず、従って（４，１，…，０）のパターンは選択しない。
【００２１】
そして、選択した複数のパターンについて、母材の長手方向に生成する生成数を数理計画法を用いて算出する。このように、パターンに含まれる各子材の数量の比と、各子材の所要数量の比とが等しい又は近似するパターンを選択するため、選択したパターンを整数倍生成することによって、過剰子材製造数量を可及的に抑制し得る。また、数理計画法を適用するパターンの数が少ないため、短い時間で各パターンの生成数を算出することができる。従って、短い時間で高い信頼性の計画を作成することができる。
【００２２】
パターンを選択するには、各パターンに含まれる子材の数量を要素とする複数のベクトルを、各ベクトルに含まれる複数の要素の内、値が１以上、即ち値が零でない要素を要素とする部分ベクトルに変換する。また、各部分ベクトルに含まれる要素に係る子材の所要数量を要素とする対応ベクトルをそれぞれ作成する。前述した（１，１，…，０）は（１，１）に変換される。この部分ベクトルの対応ベクトルは（５，５）である。
【００２３】
これら部分ベクトル及び対応ベクトルを、その長さが例えば１になるように正規化して複数対の正規化ベクトルを得、対をなす正規化ベクトルの内積をそれぞれ求める。部分ベクトル及び対応ベクトルの方向が等しい場合、両者の内積は１である。そこで、閾値（例えば、０．９９）を予め設定しておき、該閾値と各内積値とをそれぞれ比較し、閾値より内積値の方が大きい部分ベクトルを特定することによって、パターンに含まれる各子材の数量の比と、各子材の所要数量の比とが等しい又は近似するパターンを選択することができる。
【００２４】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて具体的に説明する。
図１は本発明方法を適用する装置の構成を示す模式図であり、図２及び図３は図１に示した装置による製品製造計画の作成手順を示すフローチャートである。オペレータがキーボード又はマウス等の入力部２を用いて、注文番号、注文幅及び注文枚数等の注文情報、並びに後述する制約条件及び内積閾値（例えば０．９９）を入力すると、コンピュータ１はそれらを取り込む（ステップＳ１）。
【００２５】
図４は注文情報の一例を示す図表である。なお、各注文された製品の長さは全て同じである。図４に示した如く、注文情報として、注文番号の別に、注文された製品の幅及び注文数が設定してある。
【００２６】
第１の制約条件として、母材幅の上下限値（例えば４００及び３００）、組み合わせ内の総注文数量の上限値（例えば８）、組み合わせ内の総注文番号数の上限値（例えば５以下）等を入力し、第２の制約条件として、組み合わせ候補の生成数下限値（４枚分）、及び各注文の注文充足制約等を入力する。
【００２７】
コンピュータ１は、取り込んだ注文情報から、後述する求解の対象とする対象組み合わせ候補を次のようにして形成する（ステップＳ２）。コンピュータ１は、注文情報に含まれる各注文に係る全ての組み合わせを列挙する（ステップＳ21）。組み合わせの一例をベクトルで表記すると、（１，１，１，１，１，１，１，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０）、（９，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０）、（２，０，０，０，０，０，０，１，０，０，０，０，０，０，０，０，０，０，１，０，０，０，０，１，０，０，０）となる。第１例のベクトルは、注文番号が１，２，３，４，５，６，７の注文を母材の幅方向へそれぞれ１条ずつ並べた場合を表しており、第２例のベクトルは、注文番号が１の注文を母材の幅方向へ９条並べた場合を表しており、第３例のベクトルは、注文番号が１，８，19，24の注文を母材の幅方向へそれぞれ２条，１条，１条，１条並べた場合を表している。
【００２８】
コンピュータ１は、列挙した全ての組み合わせの中から、前述した第１の制約条件を満たす組み合わせを選択し（ステップＳ22）、それらを組み合わせ候補とする。例えば、母材幅の上下限値を４００及び３００としたとき、前述した第１例に含まれる各注文の幅の累計は、４２×１＋４３×１＋４４×１＋４９×１＋５２×１＋５４×１＋５８×１＝３４２であり、第２例に含まれる注文の幅の累計は、４２×９＝３７８であり、第３例に含まれる各注文の幅の累計は、４２×２＋５９×１＋１０６×１＋１４１×１＝３９０であるので、第１例，第２例及び第３例は共に母材幅の上下限値内にある。
【００２９】
また、総注文数量の上限値を８としたとき、第１例に含まれる注文の総注文数量は、前記ベクトルに含まれる各要素の総和である７であり、第２例に含まれる注文の総注文数量は９であり、第２例に含まれる注文の総注文数量は５であるので、第１例及び第３例が総注文数量の上限値以下である。
【００３０】
また、総注文番号数の上限値を５としたとき、第１例に含まれる注文の総注文番号数は、前記ベクトルに含まれる各要素の数である７であり、第３例に含まれる注文の総注文番号数は４であるので、第３例が総注文番号数の上限値以下である。従って、上述した第１例，第２例及び第３例にあっては、第３例が組み合わせ候補として選択される。このような操作を列挙した全ての組み合わせについて行い、全ての第１制約条件を満たすものを組み合わせ候補として選択する。
【００３１】
コンピュータ１は、選択した各組み合わせ候補について、その組み合わせ候補のベクトルに含まれる各要素から値が零でない要素を抜き出し、抜き出した各要素を要素とする部分ベクトルをそれぞれ作成する（ステップＳ23）。前述した第３例の場合の部分ベクトルは（２，１，１，１）である。
【００３２】
また、コンピュータ１は、前述した如く抜き出した各要素に対応する注文の注文数量を注文情報から読み出し、各注文数量を要素とするベクトルを作成し（ステップＳ24）、それを前記部分ベクトルに対応する対応ベクトルとする。図４に示した注文情報から、第３例の場合の部分ベクトル（２，１，１，１）に対応する対応ベクトルは、（１０，５，５，５）である。
【００３３】
コンピュータ１は、各部分ベクトル及びそれに対応する対応ベクトルを、長さが１になるように正規化した正規化ベクトルにそれぞれ変換する（ステップＳ25）。前述した第３例の部分ベクトル（２，１，１，１）の正規化ベクトルは（0.7559，0.3780，0.3780，0.3780）であり、その対応ベクトル（１０，５，５，５）の正規化ベクトルは（0.7559，0.3780，0.3780，0.3780）である。
【００３４】
コンピュータ１は、このようにして得た複数対の正規化ベクトルについて、各対の正規化ベクトルの内積をそれぞれ算出する（ステップＳ26）。コンピュータ１は、算出した得られた各内積値と予め設定された内積閾値（例えば０．９９）とを比較し（ステップＳ27）、内積値が内積閾値以上である対の部分ベクトルに係る組み合わせ候補を、後述する求解の対象とする対象組み合わせ候補と決定し（ステップＳ28）、内部メモリ又は外部メモリに与えてそこに記憶させる（ステップＳ29）。前述した第３例に係る対の正規化ベクトルの内積は１．００００であり、この値は内積閾値０．９９より大きいため、第３例の組み合わせ候補は、対象組み合わせ候補である。
【００３５】
このようにして、各注文数量の比と各要素の比とが近似した対象組み合わせ候補が選択される。なお、図４に示した注文情報を用いた場合、略７５０００個の組み合わせから６９６個の対象組み合わせ候補が選択される。これによって、最適な解となる可能性が高い対象組み合わせ候補を、短時間で形成することができる。
【００３６】
コンピュータ１は、このようにして形成した対象組み合わせ候補を母材の長手方向へ生成する生成数を、例えば分枝限定法を用いて次のようにして算出する。コンピュータ１には次の（８）式で示す目的関数、（９）式、（10）式及び（11）式で示す制約条件が予め設定してある。
【００３７】
【数１】
0003950237.tif 000002
【００３８】
上記の（９）式は、前述した第２制約条件の内の各注文の注文充足制約を表しており、（10）式及び（11）式は、組み合わせ候補の生成数下限値を表している。
【００３９】
コンピュータ１は、（８）式〜（11）式を用いて各対象組み合わせ候補の生成数ｘj の最適解を実数で求め（ステップＳ３）、求めた各生成数ｘj について小数点以下を切り上げて整数になす丸め処理を行う（ステップＳ４）。そして、コンピュータ１は、このようにして得た各対象組み合わせ候補の生成数ｘj の最適整数解を記憶する（ステップＳ５）と共に、ＣＲＴ又は液晶ディスプレイ等の表示部３に表示させる（ステップＳ６）。
【００４０】
なお、本実施の形態では、対象組み合わせ候補の生成数を分枝限定法によって算出しているが、本発明はこれに限らず、切除平面法といった他の数理計画法を用いて算出してもよいことはいうまでもない。
【００４１】
なお、図２及び図３に示した製造計画作成のコンピュータプログラムは、図１に示したコンピュータ１のＲＯＭに書き込んでおく以外に、図５に示した如く、コンパクトディスク又はフレキシブルディスク等の記録媒体RMに記録しておき、この記録媒体RMをコンピュータのディスクドライブに装填してロードし、製造計画を作成させる構成であってもよい。
【００４２】
【実施例】
次に比較試験を行った結果について説明する。
図７は本発明方法によって製造計画を作成した結果を示す図表であり、図８は従来方法によって製造計画を作成した結果を示す図表である。両方法とも、図４に示した注文情報を入力した略１００ＭＩＰＳの速度のコンピュータを用いて、未製造量が零になるように製造計画を作成した。なお、従来方法は、前述したＭＩＰに基づくアプローチに従った。
【００４３】
図８から明らかな如く、従来の方法で作成した製造計画では、注文幅が４９，５２，９６，１０６で過製造が多量に発生し、注文幅が５９，９５，１０１，１２０でも過製造が発生しており、総過製造量は４４９枚であった。また、従来の方法で作成した製造計画では、組み合わせ候補を形成し、各組み合わせ候補の生成数を決定するまでに略１７０秒を要した。
【００４４】
一方、図７から明らかな如く、本発明方法にあっては、注文幅が９１，９６，１００，１０１，１２１で過製造が発生しているが、何れもその量は少なく、総過製造量は８枚であった。また、本発明方法にあっては、対象組み合わせ候補を生成し、各対象組み合わせ候補の生成数を決定するまでに略１３０秒を要し、従来の方法より短い実用的な時間で製造計画を作成することができた。
【００４５】
【発明の効果】
以上詳述した如く、本発明にあっては、パターンに含まれる各子材の数量の比と、各子材の所要数量の比とが等しい又は近似するパターンを選択するので、選択したパターンを整数倍生成することによって、過剰子材製造数量を可及的に抑制し得るのに加えて、数理計画法を適用するパターンの数が少ないため、短い時間で各パターンの生成数を算出することができ、従って、短い時間で高い信頼性の計画を作成することができる等、本発明は優れた効果を奏する。
【図面の簡単な説明】
【図１】本発明方法を適用する装置の構成を示す模式図である。
【図２】図１に示した装置による製品製造計画の作成手順を示すフローチャートである。
【図３】図１に示した装置による製品製造計画の作成手順を示すフローチャートである。
【図４】注文情報の一例を示す図表である。
【図５】他の実施の形態を示す模式図である。
【図６】切り出し計画を説明する説明図である。
【図７】本発明方法によって製造計画を作成した結果を示す図表である。
【図８】従来方法によって製造計画を作成した結果を示す図表である。
【符号の説明】
１    コンピュータ
２    入力部
３    表示部
【図１】
0003950237.tif 000003
【図２】
0003950237.tif 000004
【図３】
0003950237.tif 000005
【図４】
0003950237.tif 000006
【図５】
0003950237.tif 000007
【図６】
0003950237.tif 000008
【図７】
0003950237.tif 000009
【図８】
0003950237.tif 000010