(57)【要約】【課題】設備制約を満たさない組合せや、冗長な組合せを排除して、組合せの全てを探索できるようにし、計算効率が良い、最適な板取計画を決定できるようにする。【解決手段】複数の鋼片に１以上の注文を充当して板取計画を作成する際に、設備制約、及び、冗長な組合せを排除するための制約の下で考えられる全ての組合せを分岐限定法により列挙した後、列挙された組合せの中から０−１計画法を用いて、注文枚数の制約の下で、目的の評価関数を最大とする鋼片を選択することによって、最適な板取計画を決定する。【選択図】      図１
2004276034.tif 000002
【特許請求の範囲】
【請求項１】
複数の鋼片に１以上の注文をそれぞれ充当して板取計画を作成する際に、設備制約、及び、冗長な組合せを排除するための制約の下で、考えられる全ての組合せを分岐限定法により列挙した後、列挙された組合せの中から０−１計画法を用いて、注文枚数の制約の下で、目的の評価関数を最大とする鋼片を選択することによって、板取計画を決定することを特徴とする板取方法。
【請求項２】
前記分岐限定法として、
長方向に注文を並べた組合せを、更に幅方向に組み合わせるための分岐限定法と、
幅方向に注文を並べた組合せを、更に長方向に組み合わせるための分岐限定法と、を併用することを特徴とする請求項１に記載の板取方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、板取方法、特に製鉄所において、複数の鋼片に１以上の注文を引き当てる際に適用して好適な、板取方法に関する。
【０００２】
【従来の技術】
一般に、複数の鋼片に１以上の注文を引き当てる（充当する）板取計画においては、まずあるルールに従って初期組合せを決定しておき、その後、遺伝アルゴリズムやシミュレーティッドアニーリングといった発見的手法によって、計算時間の許す限り、初期組合せを改善していく手法が一般的である（例えば、特許文献１参照）。
【０００３】
【特許文献１】
特開平６−１４２７２５号公報
【０００４】
【発明が解決しようとする課題】
しかしながら、先に挙げたような、遺伝アルゴリズムやシミュレーティッドアニーリングといった発見的手法によって、計算時間の許す限り、初期組合せを改善していく手法では、計算時間を短縮するために、特開平７−９６３１１号公報に示されているように初期値組合せのルールを改善するか、評価関数値の高い組合せを、随時、組合せの対象から外していくといった方法しかなく、組合せの改善方法自体は、交叉や突然変異といった発見的手法に限られていた。又、それ故に、図６（Ａ）に示すように圧延可能サイズを越えるために設備制約を満たさない組合せや、同図（Ｂ）に示すように順番が入れ替わっただけの探索する必要の無い冗長な組合せが、組合せ探索の段階で多数生じており、改善のための計算効率が悪いという問題があった。更に、このような発見的手法には、可能な組合せの全域を探索する訳ではないため、最適性が保証されていないという問題もあった。
【０００５】
本発明は、前記従来の問題点を解決するべくなされたもので、組合せ探索の段階で、設備制約を満たさない組合せや、探索する必要のない冗長な組合せが生じないようにできると共に、可能な組合せの全域を探索できるようにすることにより、計算効率を改善し、しかも最適な板取計画を決定することができる板取方法を提供することを課題とする。
【０００６】
【課題を解決するための手段】
本発明は、複数の鋼片に１以上の注文をそれぞれ充当して板取計画を作成する際に、設備制約、及び、冗長な組合せを排除するための制約の下で、考えられる全ての組合せを分岐限定法により列挙した後、列挙された組合せの中から０−１計画法を用いて、注文枚数の制約の下で、目的の評価関数を最大とする鋼片を選択することによって、板取計画を決定するようにしたことにより、前記課題を解決したものである。
【０００７】
【発明の実施の形態】
以下、図面を参照して、本発明の実施の形態について詳細に説明する。
【０００８】
図１は、本発明に係る一実施形態の板取方法の手順の概要を示すフローチャートである。
【０００９】
本実施形態では、まず第一段階で、設備制約を満たし、且つ、冗長な組合せを排除した組合せを分岐限定法により列挙し（ステップ１、２）、次に第二段階で、評価関数値の高い組合せのみを０−１計画法にて選択する（ステップ４）ことによって、最適な板取計画を決定する。
【００１０】
即ち、第一段階では、設備制約を満たし、且つ、冗長な組合せを排除した組合せを分岐限定法により全て列挙する。この際、上記フローチャートのステップ１、ステップ２にそれぞれ従って、図２にイメージで示すような２つの組合せを共に考慮するため、
▲１▼長方向に注文を並べた組合せを、更に幅方向に組み合わせるための分岐限定法と、
▲２▼幅方向に注文を並べた組合せを、更に長方向に組み合わせるための分岐限定法
の２通りの方法で列挙を行なう。因みに、前記特許文献１では▲２▼の列挙のみを行なっているという点でも最適性が保証されていない。
【００１１】
上記ステップ１による▲１▼、ステップ２による▲２▼の各処理は、組残しの注文がＮ未満になるまで繰り返す（ステップ３）。このＮは、板取計画を立てるに十分な注文数を充当したか否かを判定する整数であり、注文数の大小や計算時間の多少により適宜調整される。但し、可能な限り小さい数であることが望ましい。
【００１２】
ここで、本実施形態における分岐限定法に使用される制約条件をまとめて示す。
【００１３】
（Ｉ）設備制約の主なものは以下のＣ１〜Ｃ６である。
【００１４】
Ｃ１：最大圧延長
Ｃ２：最大圧延幅
Ｃ３：最大鋼片長
Ｃ４：最小鋼片長
Ｃ５：成分系組合せ可否
Ｃ６：せん断設備制約
Ｃ７：注文枚数
【００１５】
（ＩＩ）上記▲１▼の冗長な組合せを排除するための制約条件は、以下のＤ１〜Ｄ５である。
【００１６】
Ｄ１：長方向は注文の幅の広いものから並べる。
Ｄ２：幅の同じものは注文の長の長いものから並べる。
Ｄ３：幅も長も同じものは注文番号の若い順に並べる。
Ｄ４：幅の差がδ１以上のものは隣り合わせとしない。
Ｄ５：組合せ後の歩留りδ２以下となる組合せは行なわない。
Ｄ６：長方向に組み合わせたものを幅方向に組み合わせる際にＥ１〜Ｅ５を満たす。
【００１７】
（ＩＩＩ）上記▲２▼の冗長な組合せを排除するための制約条件は、同様に以下のＥ１〜Ｅ５である。
【００１８】
Ｅ１：幅方向は注文の長の長いものから並べる。
Ｅ２：長の同じものは注文の幅の広いものから並べる。
Ｅ３：長も幅も同じものは注文番号の若い順に並べる。
Ｅ４：長の差がε１以上のものは隣り合わせとしない。
Ｅ５：組合せ後の歩留りε２以下となる組合せは行なわない。
Ｅ６：幅方向に組み合わせたものを長方向に組み合わせる際にＤ１〜Ｄ５を満たす。
【００１９】
なお、Ｄ１〜Ｄ３及びＥ１〜Ｅ３は、それぞれ長方向及び幅方向に板を組み合わせる場合に単に配列の順番だけ異なるものは排除するための制約である。
【００２０】
次に、前記分岐限定法を具体的に説明するが、▲１▼と▲２▼の方法は、方向が逆になるだけで、手順は実質的に同一なので、以下では簡単にするために、▲１▼長方向に注文を並べて組合せた後、更にそれらを幅方向に組み合わせるための分岐限定法について説明する。
【００２１】
▲１▼の分岐限定法の処理手順は、図３に示すフローチャートで表わすことができる。この図３において、制約（１）〜（４）は前出の制約のうち、それぞれ以下の制約を表わす。
【００２２】
制約（１）：Ｃ５、Ｃ７、Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５
制約（２）：Ｃ１
制約（３）：Ｃ５、Ｃ７、Ｄ６（＝Ｅ１〜Ｅ５）
制約（４）：Ｃ２、Ｃ３、Ｃ４、Ｃ６
【００２３】
図３のフローチャートに従う処理を理解し易くするために、注文数が少ない６つの場合の例について、探索図に置き換えたものを図４に示す。
【００２４】
まず、図４（Ａ）に示す注文群の中から頂点となる１つの注文を選択し、この頂点について長方向に制約（１）を満たすか否かを判定する（ステップ１２、１３）。但し、図示は省略したが、実際の処理ではステップ１１で頂点を選択した段階で１枚だけでも制約条件を判定し、それを満たす場合は１枚だけのパターンも候補として残す。
【００２５】
上記ステップ１３で制約（１）を満たした場合は、その注文を長方向に追加し（ステップ１４）、制約（２）、即ち長方向に並べた長さが「最大圧延長」のＣ１を満すか判定し（ステップ１５）、ＯＫの場合はその注文を新ノードとして生成させ（ステップ１６）、後に行なう０−１計画法等に使用するために歩留りや圧延能率を計算する（ステップ１７）。なお、この計算は、フローチャートの最後にまとめて行なってもよい。
【００２６】
次いで、ステップ１６で新ノードを生成したか否かを判定し（ステップ１８）、その深さの注文に対して新ノード生成が確認された（Ｙ）の場合には、その注文に続ける次の深さの注文に進めるために、前記ステップ１２に戻り、同様の処理を行なう（ステップ１９）。
【００２７】
なお、前記ステップ１３及び１５で制約条件を満たさなかった場合と、ステップ１８で新ノードが生成されていなかった場合は、全ての注文追加が終了していなければ、同様にステップ１２に戻り、次の追加注文を選択する（ステップ２０）。
【００２８】
ステップ２０で全ての注文追加が終了した後、新たな頂点として選択する注文が残っている場合は、ステップ１１に戻り、同様の処理を繰り返す。
【００２９】
以上のステップ１１〜２０までの処理を、新たな頂点としての注文がなくなるまで繰り返す（ステップ２１）。
【００３０】
因みに、図４（Ｂ）は、ステップ１１で選択した注文１について、深さ１として注文２、３・・・６を選択したが、全て制約（１）中のＤ１「幅の広いものから並べる」を満たしていないため、いずれも黒丸で示したように新ノードを生成させない場合を示している。
【００３１】
同図（Ｃ）は、次に頂点として選択した注文２について同様に深さ１の注文を追加したところ、注文１と３については制約（１）と同時に制約（２）も満たしたため、白丸で示したように、ステップ１８で新ノードを確定し、更にこの新ノードに対して次の深さ２の注文を追加したところ、注文３は制約（１）を満たさなかったが、注文１は満たしていたため、更に次に新ノードとして生成させ、確定した状態を示している。次に、この新ノードに対しては、更に次の深さに進み、注文を長方向に追加して３枚、４枚…と深さを増していき、新ノードが生成されなくなった時点で終了する。
【００３２】
前記ステップ２１で、長方向に新たな頂点に選択できる注文が無くなった場合には、幅方向の組合せを検索するためにステップ２２に進む。そして、前記ステップ１１〜２１の繰り返し処理により制約（１）及び（２）を共に満たして残ったノードの組合せ同士を、ステップ２２〜３２に従って処理することにより幅方向に追加し、最終的な鋼片の組合せ候補を決定する。このステップ２２〜３２の探索方法は、前記ステップ１１〜２１による頂点に注文を追加していくアルゴリズムにおいて、「注文」→「組合せ」、「長方向」→「幅方向」と置き換えれば同様であるので、詳細な説明は省略する。
【００３３】
因に、図４（Ｄ）は、同図（Ｃ）に示した新ノードが生成された注文２、３、１の長方向の組合せについて、幅方向の組合せを選択した結果、幅方向の深さ１について制約（３）と制約（４）を満たした例を白丸で、満たさなかった例を黒丸で示した。同様の処理を、幅方向に必要な回数だけ繰り返すことになる。
【００３４】
このようにして分岐限定法により生成された組合せそれぞれに対し、歩留り、圧延能率、せん断能率、納期達成率、成分コスト等を総合的に考慮した評価指標を計算する。その後、前記図１のステップ４に示したように、０−１計画法を用いて、生成された組合せの中から、注文枚数を満たすという制約の下で、最適な組合せを選択する。図５には、この０−１計画法による処理のイメージを示す。この方法によれば、前記図３のフローチャートに従って生成された４枚までの注文によるパターン生成結果が、仮に同図上方の長丸内に示した８種類であるとすると、その中から同図下方の長丸内に示した２つのパターンを最適化された鋼片に決定することができる。
【００３５】
０−１計画法のアルゴリズムに関しては、汎用的なアルゴリズムなので省略するが、近年の計算機技術の発達により、数千〜１万程度の決定変数を持つ０−１計画法であれば、５分以内に最適解を求解することができる。
【００３６】
この問題は次のように表わすことができる。Ｎを１を要素とする行列（注文数×１行列）、ａｉを各組合せｉに必要となる注文を表わす行列（注文数×１行列）、ｘｉを０又は１の値をとる決定変数（１×１行列）、Ｊｉを各組合せａｉの評価関数値（１×１行列）とすると、
ΣＪｉ・ｘｉ→ｍａｘ
（但し、Σａｉ・ｘｉ＝Ｎ）
を満たす。
【００３７】
【実施例】
次に、本発明の実施例を示す。
【００３８】
注文数２１２枚の注文群に対し、
▲１▼長方向に注文を並べた組合せを更に幅方向に組み合わせるための分岐限定法を行なった結果、８６５０通りの組合せが得られた。
【００３９】
又、
▲２▼幅方向に注文を並べた組合せを更に長方向に組み合わせるための分岐限定法を行なった結果、４６０７通りの組合せが得られた。
【００４０】
そこで、合計１３２５７通りの組合せの中から、前出の目的関数値ΣＪｉ・ｘｉを最大とする鋼片を０−１計画法により求めたところ、３６通りの組合せが得られた。
【００４１】
このようにして、２１２枚の注文群を３６本の鋼片に最適に充当することができた。
【００４２】
なお、一般的なパソコンによるこのときの計算時間は、分岐限定法部分が３分１４秒、０−１計画法部分が２分５６秒であり、充分実用可能な計算時間であった。
【００４３】
以上詳述した本実施形態では、まず第一段階で、設備制約を満たし、且つ、冗長な組合せを排除した組合せを分岐限定法により列挙し、次に第二段階で、評価関数値の高い組合せのみを０−１計画法にて選択することによって、最適な板取を決定する。これにより、遺伝アルゴリズムやシミュレーティッドアニーリングといった発見的手法に頼ることなく、実用時間内に、最適な注文の組合せ、即ち板取計画が可能となった。
【００４４】
以上、本発明の実施例を具体的に説明したが、本発明は前記実施形態に示したものに限られるものでなく、要旨を逸脱しない範囲で種々変更可能である。
【００４５】
【発明の効果】
以上説明したとおり、本発明によれば、組合せ探索の段階で、設備制約を満たさない組合せや、探索する必要のない冗長な組合せが生じないようにできると共に、可能な組合せの全域を探索できるようにすることにより、計算効率を改善し、しかも最適な板取計画を決定することができる。
【図面の簡単な説明】
【図１】本発明に係る一実施形態による処理手順の概要を示すフローチャート
【図２】長方向後、幅方向の分岐限定法と、幅方向後、長方向の分岐限定法のイメージを示す説明図
【図３】長方向後、幅方向の分岐限定法の手順を示すフローチャート
【図４】長方向後、幅方向の分岐限定法の手順の一例を示す探索図
【図５】分岐限定法と０−１計画法を組合せた作用のイメージを示すフローチャート
【図６】探索する必要のない注文の組合せの例を示す説明図
【符号の説明】
１〜６…注文番号
【図１】
2004276034.tif 000003
【図２】
2004276034.tif 000004
【図３】
2004276034.tif 000005
【図４】
2004276034.tif 000006
【図５】
2004276034.tif 000007
【図６】
2004276034.tif 000008