(57)【特許請求の範囲】
【請求項１】
鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様に前記ヤードにおいて積み上げて、次工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画立案装置であって、
前記払出山の総数を評価する項と、同一の前記払出山において前記ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を評価する項とを含む目的関数を設定する目的関数設定手段と、
前記鋼材を山積みするときの制約を示す制約式を設定する制約式設定手段と、
前記制約式による制約を満足する範囲で前記目的関数の値を最大化または最小化する様に、数理計画法による最適化計算を行うことにより、前記鋼材を前記複数の払出山に分けるための計算を行う最適解導出手段と、を有し、
前記制約式は、頂点が前記鋼材に対応し、且つ、枝により相互に連結される２つの前記頂点に対応する２つの前記鋼材が同一の前記払出山に積まれる２つの前記鋼材であることを表す無向グラフを、相互に前記頂点が重複しない複数のクリークに分割することを規定する制約式を含み、
前記目的関数設定手段は、前記払出山の総数を評価する項として前記クリークの総数を評価する項を含み、前記逆転対の数を評価する項として前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数を評価する項を含む前記目的関数を設定し、
前記最適解導出手段は、前記数理計画法による最適化計算の際に、前記クリークの総数と、前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数とを評価することを特徴とする鋼材の山分け計画立案装置。
【請求項２】
１つの前記クリークを構成する前記頂点に対する重みの総和が１になるように前記頂点の夫々に対して重みが設定され、
前記払出山の総数は、前記頂点の夫々に対して設定された重みの、前記無向グラフを構成する前記頂点の全てについての総和として規定されることを特徴とする請求項１に記載の鋼材の山分け計画立案装置。
【請求項３】
前記払出山の総数は、前記頂点と、当該頂点を含む前記クリークを構成するその他の前記頂点とを相互に連結する前記枝の数に１を加算した値の逆数である非線形関数の、前記無向グラフを構成する前記頂点の全てについての総和として規定されることを特徴とする請求項２に記載の鋼材の山分け計画立案装置。
【請求項４】
前記払出山の総数は、前記頂点に対応する前記鋼材の数を、当該頂点を含む前記クリークを構成する全ての前記頂点に対応する前記鋼材の総数で割った値である非線形関数の、前記無向グラフを構成する前記頂点の全てについての総和として規定されることを特徴とする請求項２に記載の鋼材の山分け計画立案装置。
【請求項５】
前記払出山の総数は、前記頂点と、当該頂点を含む前記クリークを構成するその他の前記頂点とを相互に連結する前記枝の数に１を加算した値の逆数である非線形関数の、前記無向グラフを構成する前記頂点の全てについての総和と、前記頂点に対応する前記鋼材の数を、当該頂点を含む前記クリークを構成する全ての前記頂点に対応する前記鋼材の総数で割った値である非線形関数の、前記無向グラフを構成する前記頂点の全てについての総和と、の２通りに規定されることを特徴とする請求項２に記載の鋼材の山分け計画立案装置。
【請求項６】
前記払出山の総数は、前記頂点ごとに設定される連続変数であって、前記非線形関数から変換される区分線形関数に対する上限値を表す連続変数の、前記無向グラフを構成する前記頂点の全てについての総和として規定されることを特徴とする請求項３〜５の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項７】
前記連続変数の、前記無向グラフを構成する前記頂点の全てについての総和を整数変数とし、前記整数変数を前記払出山の総数として規定することを特徴とする請求項６に記載の鋼材の山分け計画立案装置。
【請求項８】
前記制約式は、前記頂点に対応する前記鋼材と、当該頂点を含む前記クリークを構成するその他の前記頂点に対応する前記鋼材の数が上限値以下であることを示す山高さ制約式を含むことを特徴とする請求項１〜７の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項９】
前記制約式設定手段は、前記鋼材の大きさに基づいて、同一の前記払出山に積むことができない２つの前記鋼材の組を導出し、
前記制約式は、同一の前記払出山に積むことができない２つの前記鋼材の組の集合に対し、同一の前記払出山に積むことを禁止することを示す同一山禁止制約式を含むことを特徴とする請求項１〜８の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項１０】
前記頂点に対応する鋼材は、複数の鋼材からなる鋼材グループであることを特徴とする請求項１〜９の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項１１】
前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝に対する重みとして１が設定され、そうでない前記枝に対する重みとして０（ゼロ）が設定され、
前記逆転対の数は、前記枝に対して設定された重みの値の総数として表現されることを特徴とする請求項１〜１０の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項１２】
前記制約式は、前記クリークを構成する前記頂点のうちの３つの頂点である第１の頂点、第２の頂点、および第３の頂点について、前記第１の頂点に対応する前記鋼材と前記第２の頂点に対応する前記鋼材とが同一の前記払出山に積まれ、且つ、前記第２の頂点に対応する前記鋼材と前記第３の頂点に対応する前記鋼材とが同一の前記払出山に積まれるのであれば、前記第１の頂点に対応する前記鋼材と前記第３の頂点に対応する前記鋼材も同一の前記払出山に積まれなければならないことを示す推移性制約式を含むことを特徴とする請求項１〜１１の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項１３】
鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様に前記ヤードにおいて積み上げて、次工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画立案方法であって、
前記払出山の総数を評価する項と、同一の前記払出山において前記ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を評価する項とを含む目的関数を設定する目的関数設定工程と、
前記鋼材を山積みするときの制約を示す制約式を設定する制約式設定工程と、
前記制約式による制約を満足する範囲で前記目的関数の値を最大化または最小化する様に、数理計画法による最適化計算を行うことにより、前記鋼材を前記複数の払出山に分けるための計算を行う最適解導出工程と、を有し、
前記制約式は、頂点が前記鋼材に対応し、且つ、枝により相互に連結される２つの前記頂点に対応する２つの前記鋼材が同一の前記払出山に積まれる２つの前記鋼材であることを表す無向グラフを、相互に前記頂点が重複しない複数のクリークに分割することを規定する制約式を含み、
前記目的関数設定工程は、前記払出山の総数を評価する項として前記クリークの総数を評価する項を含み、前記逆転対の数を評価する項として前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数を評価する項を含む前記目的関数を設定し、
前記最適解導出工程は、前記数理計画法による最適化計算の際に、前記クリークの総数と、前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数とを評価することを特徴とする鋼材の山分け計画立案方法。
【請求項１４】
請求項１〜１２の何れか１項に記載の鋼材の山分け計画立案装置の各手段としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鋼材の山分け計画立案装置、鋼材の山分け計画立案方法、およびプログラムに関し、特に、ヤードにおける鋼材の山分け計画を立案するために用いて好適なものである。
【背景技術】
【０００２】
金属製造プロセスの一例である鉄鋼プロセスにおいて、例えば製鋼工程から次工程の圧延工程へ鋼材を搬送する際、鋼材は、一旦ヤードと呼ばれる一時保管場所に置かれた後、次工程である圧延工程の処理時刻に合わせてヤードから搬出される。そのヤードのレイアウトの一例を図５に示す。ヤードとは、図５に示すように、上流工程より払い出されたスラブなどの鋼材を、下流工程に供給するためのバッファーエリアとして、縦横に区画された置場５０１〜５０４である。縦方向の分割区分を"棟"、横方向の分割区分を"列"と称することが多い。クレーン(１Ａ、１Ｂ、２Ａ、２Ｂ)は棟内を移動可能であり、同一棟内での異なる列の間で鋼材の移送を行う。また搬送テーブルにより棟間の鋼材の移送を行う。搬送指令を作成する際は"棟"及び"列"を指定することにより、どこへ鋼材を搬送するかを示す（図５の置場５０１〜５０４に括弧書きで付されている番号（１１）、（１２）、（２１）、（２２）を参照）。
【０００３】
図５を例にヤードでの基本的な作業の流れを示す。まず、前工程である製鋼工程の連鋳機５１０から搬出された鋼材は、パイラー５１１を経由して受入テーブルＸでヤードまで搬入され、クレーン１Ａ、１Ｂ、２Ａ、２Ｂにより、区画された置場５０１〜５０４の何れかに搬送され、山積みして置かれる。そして、次工程である圧延工程の製造スケジュールに合わせ、再びクレーン１Ａ、１Ｂ、２Ａ、２Ｂにより払出テーブルＺに載せられ、圧延工程へと搬送される。一般に、ヤードにおいて鋼材は、前記の様に山積みされた状態で置かれる。これは、限られたヤード面積を有効に活用するためである。一方、鋼材を積み上げる際、次工程へ供給し易いよう、次工程の処理順番に鋼材が上から積まれている必要がある。さらに、積み姿が不安定な逆ピラミッド状に鋼材を積まないようにする必要がある。このように、鋼材を複数の最適山（＝払出山：次工程へ払い出す最終的な山姿となった山）に分けることを山分けと呼ぶ。
【０００４】
ここで、次工程である圧延工程の加熱炉の燃料原単位を削減するため、可及的に高い温度の鋼材を加熱炉に払い出す（装入する）ことが求められる。このため、昨今、ヤード内に保温設備を設置し、保温設備の中に前述したようにして鋼材を山積みした状態で保管することが行われている。このように保温設備を用いる場合でも、置場５０１〜５０４に直接鋼材を山積みする場合と同様に、保温設備を有効に活用するため、保温設備の中において、可及的に高さの高い払出山を作成することが必要である。また、次工程の処理順番に鋼材が上から積まれるようにすると共に逆ピラミッド状に鋼材を積まないようにする必要がある。
【０００５】
以上のように、サイズや次工程での処理順序が異なる複数の鋼材を複数の山に分けて山積みする山分け計画を立案する際には、計画の立案対象となる鋼材により生成可能な全ての山分け候補の中から、山数と山繰り負荷（クレーン等の搬送設備による鋼材のハンドリング負荷）を最小化する最適化問題を解くことになるが、計画の立案対象となる鋼材の数が多いと、かかる問題は大規模問題となる。
【０００６】
そこで、特許文献１には、計画の立案対象となる鋼材を要素とする全体集合に対し、山積み制約を満たす部分集合である実現可能山を全て列挙し、山数および山繰り負荷を最小化する目的関数の下、集合分割問題として最適な実現可能山の組み合わせを求めることにより最適な山分け計画を行う手法が開示されている。
【０００７】
また、特許文献２には、複数の搬送ロット（一度に搬送機器により搬送できる鋼材のまとまり）をしかるべき山（最適山＝払出山）に割り当てる、多対１の割当問題として定式化する手法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−１３７６１２号公報
【特許文献２】特開２０１１−１０５４８３号公報
【非特許文献】
【０００９】
【非特許文献１】M.GROTSCHEL，Y.WAKABAYASHI，"A CUTTING PLANE ALGORITHM FOR A CLUDTERING PROBLEM"，Mathematical Programming，45 （1989），p.59-96
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１、２に記載の方法には、以下の課題がある。
まず、特許文献１に示す集合分割問題を応用した解法では、任意の鋼材ペアのサイズ（幅・長さ）の条件と払出順の条件とから要請される積み順が食い違うことにより、同一の山にできない鋼材ペアが比較的少ない場合には、実現可能山の数が多くなる。この数が数百万を超えると、実現可能山の列挙および最適山の算出計算のいずれにも時間を要し、要請される時間内（例えば３〜５分程度）には計算が完了せず計画が作成できないこととなる。山分け問題の場合、実現可能山の数が数千万を超えると実用的な時間（例えば１０分程度）内では実現可能解を得ることが難しくなる。このような場合には、特許文献２に示す多対１の割当問題として定式化する方法により、許容可能な時間内に求解出来るケースもあり得る。しかしながら、特許文献２に示す方法にも、以下の課題がある。
【００１１】
すなわち、特許文献２に示す方法では、ヤードへの到着順とヤードにおける積み順とが逆になるような鋼材ペア（逆転対）が多い場合に計算時間を要し、実用的な時間内に計算を完了できない虞がある。
【００１２】
この様に、従来の方法では、問題の性格に応じ、実用的な時間内に求解が可能な場合と不可能な場合とがある。したがって、どの様な問題に対しても安定的に求解できる手法が求められている。また、実現可能山の数が数千万を超え、逆転対の比率が高い鋼材群の山分け計画を作成する場合には、実用的な時間内に求解することはできない。よって、実現可能山の数が一千万を超える様な大規模な問題の場合や、逆転対が多い場合にも、実用的な時間内に求解する方法が必要である。
【００１３】
本発明は、以上のような問題点に鑑みてなされたものであり、解くべき問題の性格に関わらず、実用的な時間内で山分け計画を立案できるようにすることを目的とする。
【課題を解決するための手段】
【００１４】
本発明の山分け計画立案装置は、鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様に前記ヤードにおいて積み上げて、次工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画立案装置であって、前記払出山の総数を評価する項と、同一の前記払出山において前記ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を評価する項とを含む目的関数を設定する目的関数設定手段と、前記鋼材を山積みするときの制約を示す制約式を設定する制約式設定手段と、前記制約式による制約を満足する範囲で前記目的関数の値を最大化または最小化する様に、数理計画法による最適化計算を行うことにより、前記鋼材を前記複数の払出山に分けるための計算を行う最適解導出手段と、を有し、前記制約式は、頂点が前記鋼材に対応し、且つ、枝により相互に連結される２つの前記頂点に対応する２つの前記鋼材が同一の前記払出山に積まれる２つの前記鋼材であることを表す無向グラフを、相互に前記頂点が重複しない複数のクリークに分割することを規定する制約式を含み、前記目的関数設定手段は、前記払出山の総数を評価する項として前記クリークの総数を評価する項を含み、前記逆転対の数を評価する項として前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数を評価する項を含む前記目的関数を設定し、前記最適解導出手段は、前記数理計画法による最適化計算の際に、前記クリークの総数と、前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数とを評価することを特徴とする。
【００１５】
本発明の山分け計画作成方法は、鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様に前記ヤードにおいて積み上げて、次工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画立案方法であって、前記払出山の総数を評価する項と、同一の前記払出山において前記ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を評価する項とを含む目的関数を設定する目的関数設定工程と、前記鋼材を山積みするときの制約を示す制約式を設定する制約式設定工程と、前記制約式による制約を満足する範囲で前記目的関数の値を最大化または最小化する様に、数理計画法による最適化計算を行うことにより、前記鋼材を前記複数の払出山に分けるための計算を行う最適解導出工程と、を有し、前記制約式は、頂点が前記鋼材に対応し、且つ、枝により相互に連結される２つの前記頂点に対応する２つの前記鋼材が同一の前記払出山に積まれる２つの前記鋼材であることを表す無向グラフを、相互に前記頂点が重複しない複数のクリークに分割することを規定する制約式を含み、前記目的関数設定工程は、前記払出山の総数を評価する項として前記クリークの総数を評価する項を含み、前記逆転対の数を評価する項として前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数を評価する項を含む前記目的関数を設定し、前記最適解導出工程は、前記数理計画法による最適化計算の際に、前記クリークの総数と、前記逆転の関係が成立する２つの前記鋼材に対応する２つの前記頂点を相互に連結する前記枝の総数とを評価することを特徴とする。
【００１６】
本発明のプログラムは、前記鋼材の山分け計画立案装置の各手段としてコンピュータを機能させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、解くべき問題の性格に関わらず、実用的な時間内で山分け計画を立案することができる。
【図面の簡単な説明】
【００１８】
【図１】無向グラフの一例を示す図である。
【図２】鋼材の山分け計画立案装置の機能的な構成の一例を示す図である。
【図３】鋼材の山分け計画立案装置の動作の一例を説明するフローチャートである。
【図４】山分け計画の作成結果を表形式に示す図である。
【図５】ヤードのレイアウトの一例を示す図である。
【発明を実施するための形態】
【００１９】
＜クリーク分割問題の概要＞
後述するように本発明の実施形態は、クリーク分割問題（Clique Partitioning Problem）を山分け問題に適用する。クリーク分割問題自体は公知の技術であるが、クリーク分割問題を山分け問題に適用する際の本発明の実施形態の手法との差異を明確にするため、本発明の実施形態を説明する前に、一般的なクリーク分割問題の解法の概要について説明する。
【００２０】
図１は、無向グラフの一例を示す図である。
クリーク（Clique)とは、頂点集合Ｖ、枝集合Ｅから構成される無向グラフＧ＝（Ｖ，Ｅ）において、完全グラフとなっている部分グラフ（完全部分グラフ）のことである。完全グラフとは、頂点集合Ｖの部分集合Ｖ'（⊆Ｖ）となるグラフのうち、部分集合Ｖ'に属する何れの２つの頂点間にも枝があるグラフである。部分グラフとは、元のグラフの一部の頂点と一部の枝からなるグラフである（ただし、頂点が１つである場合には枝は含まれない）。図１に示す例では、以下の頂点の部分集合がクリークとなる（１つの｛｝が１つのクリークを示し、｛｝内に示す数字は、図１に示す頂点の傍らに付した数字を示す）。
[1,2,3,4],[1,2,3],[1,2,4],[1,4,3],[1,4,5],[2,3,4],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[3,6],[4,5],[5,6],[1],[2],[3],[4],[5],[6]
【００２１】
クリーク分割問題は，与えられた無向グラフＧ＝（Ｖ，Ｅ）を、相互に頂点の重複がないようにクリーク（完全部分グラフ）に分割する問題であり、クラスタリングをモデル化する際に用いられるグラフ上の最適化問題である。クリーク分割問題に対する標準的な定式化は、非特許文献１に示されている0-1 整数計画問題として定式化できる。
【００２２】
非特許文献１に示されるように、一般には、完全無向グラフＧ＝（Ｖ，Ｅ）において、頂点集合Ｖの部分集合Ｖ'（＝｛Ｖ1，Ｖ2，・・・，Ｖp｝）の枝集合Ａ⊆Ｅが、以下の（１）式を満たすとき、枝集合Ａは、無向グラフＧのクリーク分割と呼ばれる。すなわち、或る無向グラフについて、相互に頂点が重複しない複数のクリークに分割することをクリーク分割という。尚、｛ｉ，ｊ｝は、頂点ｉ、ｊ間の枝であることを表す。
【００２３】
【数１】
0006540360.tif 000002
【００２４】
一般に、クリーク分割問題は、正負を問わない枝重みｒ：Ｅ→Ｒ（実数）が与えられたとき、重みの総和が最大となるクリーク分割を求める問題である。
非特許文献１に示されるように、頂点集合ＶをＶ＝｛１，２，・・・，ｎ｝とし、枝集合Ｅに対し、０−１変数ベクトルｘ→＝（ｘij）1≦i≦j≦nを対応させる（→はｘがベクトルであることを示す。以下同じ）。各成分ｘijは、｛ｉ，ｊ｝∈Ａならば１をとり、｛ｉ，ｊ｝∈Ａでないならば０をとる。例えば、図１に示す無向グラフを、頂点１、２、３、４からなるクリークと、頂点５、６からなるクリークとの２つのクリークに分割される場合を例に挙げると、０−１変数ベクトルｘ→は以下の様になる。
ｘ→＝（ｘ12，ｘ13，ｘ14，ｘ15，ｘ16，ｘ23，ｘ24，ｘ25，ｘ26，ｘ34，ｘ35，ｘ36，ｘ45，ｘ46，ｘ56）＝（１，１，１，０，０，１，１，０，０，１，０，０，０，０，１）
「枝集合Ａがクリーク分割である」ことと、「任意のｉ，ｊ，ｋ∈Ｖについて、｛ｉ，ｊ｝∈Ａ且つ｛ｊ,ｋ｝∈Ａならば｛ｉ，ｋ｝∈Ａである」こととの同値性に着目すると、一般に、クリーク分割問題は、以下の（２）式〜（６）式のように定式化できる。
【００２５】
【数２】
0006540360.tif 000003
【００２６】
ただし、ｒijは、枝｛ｉ，ｊ｝の重みである．また、（３）式〜（５）式の不等式制約は、推移性制約と呼ばれる。この定式化では、変数の数は、ｎ（ｎ−１）／２個であり、推移性制約の数は、ｎ（ｎ−１）（ｎ−２）／２個ある（ｎは前述したように無向グラフの頂点の数である）。尚、推移性制約は、任意の３つの頂点（三角）の２辺の成分ｘijの値が１であれば、必ず残りの１辺の成分の値も１とならなければならないという制約である。
【００２７】
以上のように、一般的なクリーク分割問題の０−１整数計画問題では、推移性制約を満たす範囲で（２）式（すなわちクリークを構成する重みｒijの総和）を最大化する０−１変数ベクトルｘ→の各成分ｘijを求めることになる。このとき、例えば、（２）式に（−１）を掛けることにより、（２）式を最小化する問題とすることもできる。
【００２８】
以上のようにオリジナルのクリーク分割問題は、選択された枝の重みの総和が最大（または最小）となるようなクリークを求める問題である。一方、山分け問題では、総山数を最小にすることと、山繰り数を最小にすることとのトレードオフが取られた解を求める必要がある。山繰り数については、後に説明するように枝重みにより自然な形で定式化することができる。一方、総山数については、オリジナルなクリーク分割問題はもとよりそれを変形した様々な問題に対しても、クリーク数を評価するような定式化はなされていない。クリークにまつわる最適化問題として最大クリーク問題があるが、これは「無向グラフが与えられたとき、最大位数（頂点数）の完全部分グラフを求める問題」であり山分け問題とは繋がらない。このような課題に対し、本発明者らは、以下に示す本発明の実施形態のようにして、クリーク分割問題の０−１整数計画問題を山分け問題に適用できることを見出した。
【００２９】
以下、図面を参照しながら、本発明の実施形態を説明する。
（第１の実施形態）
まず、第１の実施形態を説明する。
＜鋼材の山分け計画立案装置２００の構成および処理＞
図２は、鋼材の山分け計画立案装置２００の機能的な構成の一例を示す図である。図３は、鋼材の山分け計画立案装置２００の動作の一例を説明するフローチャートである。鋼材の山分け計画立案装置２００のハードウェアは、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ、ＨＤＤ、および各種のインターフェースを備えた情報処理装置、ＰＬＣ（Programmable Logic Controller）、またはＡＳＩＣ（Application Specific Integrated Circuit）等の専用のハードウェアを用いることにより実現することができる。尚、以下の説明では、鋼材の山分け計画立案装置２００を必要に応じて山分け計画立案装置２００と略称する。
【００３０】
［入力部２０１：対象スラブグループリスト入力工程Ｓ３０１］
入力部２０１は、山分け計画の立案対象であるスラブ（鋼材）のリストである山分け対象スラブグループリストを取得する。尚、山分け対象スラブグループリストは、一定周期に取得されてもよいし、特定の事象の生起等をトリガーとして不定期に取得されてもよい。
入力部２０１は、例えば、ＣＰＵが、不図示の鋼材管理系計算機から通信インターフェースを介して受信した山分け対象スラブグループリストのデータをＨＤＤやＲＡＭに記憶することにより実現される。鋼材管理系計算機は、スラブに到着する鋼材全般に関するデータベースを有する上位のコンピュータである。
【００３１】
本実施形態では、クレーン等の搬送機器にて搬送される際に分割されることのない最小の単位となる複数のスラブの単位で、当該複数のスラブがヤードに同時刻に到着する場合を例に挙げて説明する。ただし、このように複数のスラブがヤードに同時刻に到着しないものとしてもよい。その場合、かかる複数のスラブのうち最後にヤードに到着するスラブがヤードに到着した後に、当該複数のスラブの山積みが開始される。以下の説明では、かかる複数のスラブを必要に応じて「スラブグループ」と称する。
【００３２】
本実施形態では、山分け対象スラブグループリストには、それぞれのスラブグループについて、識別番号と、到着予定時刻と、払出順と、鋼材数と、最大幅と、最小幅と、最大長と、最小長の情報が含まれる。
識別番号は、各スラブグループを一意に識別する番号である。
到着予定時刻は、各スラブグループのヤードへの到着予定時刻である。本実施形態では、ヤードに未だ１つもスラブが置かれていない場合の山分け計画を作成する。したがって、山分け計画の立案対象の全てのスラブグループについて到着予定時刻が与えられる。
【００３３】
払出順は、各スラブグループの圧延工程への搬送順である。
鋼材数は、各スラブグループを構成するスラブの数である。
最大幅・最小幅は、それぞれ、各スラブグループを構成するスラブの最大幅・最小幅である。
最大長・最小長は、それぞれ、各スラブグループを構成するスラブの最大長・最小長である。
【００３４】
尚、ここでは、スラブグループ毎のリストを取得する場合を例に挙げて説明したが、スラブ毎のリストを取得してもよい。このようにする場合、各スラブについて、当該スラブが属するスラブグループの識別番号がリストに含まれるようにする。また、最大幅、最小幅、最大幅、最小幅の代わりに、各スラブについて、当該スラブの幅および長さがリストに含まれるようにする。
【００３５】
［目的関数設定部２０２：目的関数設定工程Ｓ３０２、制約式設定部２０３：制約式設定工程Ｓ３０３］
目的関数設定部２０２は、入力部２０１により入力された山分け対象スラブグループリストに基づいて、目的変数を設定する。また、制約式設定部２０３は、入力部２０１により入力された山分け対象スラブグループリストに基づいて、制約式を設定する。以下に、本実施形態で定式化される目的関数と制約式について説明する。
【００３６】
[[無向グラフＧと重みｒの定義]]
Ｇ＝（Ｎ，Ｅ）：スラブグループの集合Ｎ（Ｎ＝｛１，２，・・・ｎ｝）は、個々のスラブグループを頂点とする完全無向グラフ（Ｇ＝（Ｎ，Ｅ））とする。図１に示す頂点の１つが１つのスラブグループに対応する。また、Ｅは、枝ｅの集合である。
尚、図１においては、枝の両端の頂点に対応する２つのスラブグループ｛ｉ，ｊ｝は同一の払出山に山積みできることを示し、枝で相互に連結されていない２つの頂点に対応する２つのスラブグループは、同一の山に山積みできないことを示す。
【００３７】
ｒ：Ｅ→｛０，１｝：任意の２つのスラブグループ｛ｉ，ｊ｝⊆Ｅに対し、スラブグループｉとスラブグループｊとを同一の払出山に積んだ場合に、ヤードへの到着順と同一の払出山における積順とが逆転しているならば「１」、そうでないならば「０（ゼロ）」であることを示す０−１変数ｒ（｛ｉ，ｊ｝）を枝｛ｉ，ｊ｝の重みとする。図１に示す２つの頂点に対応する２つのスラブグループについて、ヤードへの到着順と同一の払出山における積順が逆転しているならば、当該２つの頂点間の枝の重みは「１」であり、逆転していないならば、当該２つの頂点間の枝の重みは「０（ゼロ）」である。ここで、ヤードへの到着順と同一の払出山における積順とが逆転しているとは、積順が上になるスラブグループの方が、積順が下になるスラブグループよりも、ヤードへの到着順が早いことをいう。尚、以下の説明では、２つのスラブグループの組を必要に応じてスラブグループ対と称する。
【００３８】
[[決定変数]]
完全無向グラフＧの各枝ｅ∈Ｅに対し、０−１変数ｘ(e)を導入する。簡単のために、枝ｅ＝｛ｉ，ｊ｝∈Ｅに対し、変数x(e)をx([i，j])と表記する。この変数x([i，j])は、以下の（７）式で表される。
【００３９】
【数３】
0006540360.tif 000004
【００４０】
（７）式は、前述した（６）式に対応するものである。ここで、０−１変数ベクトルｘ→∈｛０，１｝Eにおいて、値が「１」になっている（要素）変数x([i，j])に対する枝集合を以下の（８）式のように表記するものとする。
【００４１】
【数４】
0006540360.tif 000005
【００４２】
以上のように本実施形態では、変数x([i，j])（＝ｘ(e)）が決定変数になり、その他の変数は、変数x([i，j])（＝ｘ(e)）の従属変数になる。
【００４３】
[[制約式]]
山分け計画における主要な制約は、以下の推移性制約、同一山禁止制約、および山高さ制約である。ここでは、推移性制約、同一山禁止制約、および山高さ制約の内容について説明する。尚、目的関数の値を最小化する最適化問題を、非線形計画問題から混合整数計画問題にするために必要となる制約式については、別途説明する。
【００４４】
（ａ）推移性制約（三角不等式）
推移性制約は、前述したように、無向グラフにおける第１の頂点と第２の頂点を結ぶ枝と、第２の頂点と第３の頂点とを結ぶ枝が同一のクリークを構成する枝集合に属するのであれば、第１の頂点と第３の頂点を結ぶ枝も当該クリークを構成する枝集合に属さなければならないという制約である。
【００４５】
０−１変数ベクトルｘ→∈｛０，１｝Eが山積みに対応しているならば、（不完全）無向グラフＧ（Ｖ，E(x)）は、各連結成分がクリーク（完全グラフとなっている部分グラフ）となっていなければならない。したがって、０−１変数ベクトルｘ→∈｛０，１｝Eが山積みに対応するためには、０−１変数ベクトルｘ→が、推移性制約を満たせばよい。よって、無向グラフＧ（Ｖ，E(x)）の各連結成分がクリークであるための必要十分条件は、以下の（９）式〜（１１）式を満たすことである。
【００４６】
【数５】
0006540360.tif 000006
【００４７】
（９）式〜（１１）式は、それぞれ前述した（３）式〜（５）式に対応するものである。以下の説明では、（９）式〜（１１）式の推移性制約式を満たす枝集合をΩと表記する。
（ｂ）同一山禁止制約
同一山禁止制約は、同一の払出山に山積みしていけないスラブグループを規定するものである。本実施形態では、以下の幅条件および長さ条件を満たさないスラブグループは同一の払出山に山積みしてはいけないものとする。
（ｂ−１）幅条件
或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも狭いならば無条件で、当該或るスラブグループを、当該下に位置するスラブグループの上に置ける。或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも広い場合には、両者の幅の差が、作業制約により定まる基準値（例えば３００［ｍｍ］）未満であれば、当該或るスラブグループを、当該下に位置するスラブグループの上に置けるが、それを越えると置けない。
【００４８】
すなわち、幅条件を満たす場合は、或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも狭い場合と、或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも広く、且つ、両者の幅の差が基準値（例えば３００［ｍｍ］）未満である場合である。
【００４９】
（ｂ−２）長さ条件
或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも短いならば無条件で、当該或るスラブグループを、当該下に位置するスラブグループの上に置ける。或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも長い場合には、両者の長さの差が、作業制約により定まる基準値（例えば３０００［ｍｍ］）未満であれば、当該或るスラブグループを、当該直下に位置するスラブグループの上に置けるが、それを越えると置けない。
【００５０】
すなわち、長さ条件を満たす場合は、或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも短い場合と、或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも長く、且つ、両者の長さの差が基準値（例えば３０００［ｍｍ］）未満である場合である。
【００５１】
本実施形態では、以下の（１３）式に示すように、以上の幅条件と長さ条件の少なくとも何れか一方の条件を満たさない（すなわち、同一の払出山に山積みしてはいけない）スラブグループ対（枝）の集合Ｆを導入する。
【００５２】
【数６】
0006540360.tif 000007
【００５３】
（１３）式において、ｉ，ｊは、幅条件と長さ条件の少なくとも何れか一方の条件を満たさないスラブグループを示す。
そうすると、同一の山に山積みしてはいけないスラブグループ対（枝）の集合Ｆ（⊆Ｅ）に対し、以下の（１４）式が、同一山禁止制約式として表される。
【００５４】
【数７】
0006540360.tif 000008
【００５５】
（ｃ）山高さ制約
山高さ制約は、１つの払出山の高さが基準値以下であるという制約である。
本実施形態では、全てのスラブの厚みが同じであるものとする。したがって、１つの払出山に積めるスラブの枚数が基準枚数（例えば１２［枚］）以下であるという条件を山高さ制約とする。ここで、１つの払出山に積めるスラブの数の上界をｈ（ｈ∈Ｚ+（自然数））と表記する。
【００５６】
そうすると、頂点（スラブグループ）ｉ∈Ｎに対し、以下の（１６）式が、山高さ制約式として表される。
【００５７】
【数８】
0006540360.tif 000009
【００５８】
（１６）式の左辺の第１項（w(i)）は、スラブグループｉ（∀ｉ∈Ｎ）のスラブ数（w(i)：Ｎ→Ｚ+（自然数））である。w(i)は、例えば、１以上６以下の自然数である（１≦w(i)≦６）。
【００５９】
また、（１６）式の左辺の第２項（Σの項）は、スラブグループｉ（∈Ｎ）を含む山（クリーク山）の、スラブグループｉ以外のスラブグループｊのスラブの総数を表す。
尚、（１６）式において、（１６）式の左辺の第２項のΣは、頂点集合（スラブグループ集合）Ｖの中の頂点（スラブグループ）ｉ以外の頂点（スラブグループ）ｊに対する総和を表す（このことは以降の式においても同じである）。
【００６０】
[[評価指標]]
次に、目的関数における評価指標を説明する。
本実施形態では、総山数（山高さ）と山繰り数との重み付き線形和を目的関数とする。尚、重み付き線形和とは、総山数（山高さ）に対する重み係数、山繰り数に対する重み係数を、総山数（山高さ）、山繰り数にそれぞれ乗算した値を加算したものをいう。総山数（山高さ）に対する重み係数とは、総山数（山高さ）に対する評価の、山繰り数に対する評価とのバランスを表す係数である。山繰り数に対する重み係数とは、山繰り数に対する評価の、総山数（山高さ）に対する評価とのバランスを表す係数である。
【００６１】
総山数（山高さ）を評価指標とするのは、ヤードにおける山分けでは、保温設備の収容能力が限定されていることや、スラブの置場が限られていることや、置場にスラブを直接置く場合には最上段および最下段のスラブの放冷が他のスラブに比べて大きくなること等の理由で、山高さを出来るだけ高くして総山数を出来るだけ少なくすることが要請されるからである。
【００６２】
山繰り数を評価指標とするのは、以下の理由による。まず、山分けを行う上で、作業スペースの問題や作業を行うクレーン等の搬送機器の能力の兼ね合いから、山積みを行うための搬送作業数ができるだけ少ないことが求められる。山分けの場合には、ヤードに到着する順にスラブを積んでいくことが出来れば理想的である。一方で、払出時の山繰りを無くし、払出作業を迅速に行う為に、払出山に於いては、下工程への払出が早いものを上に積むのが基本である。従って、現実的には、ヤードへの到着順と払出山における積順とが食い違う場合がある。すなわち、ヤードへの到着順が早い方のスラブを遅い方のスラブよりも同一の払出山の上の段に積まなければならない場合がある。その場合には、相対的に下段に積まれるスラブがヤードに到着するまで、先にヤードに到着したスラブを一旦仮置き場に仮置きし、相対的に下段に積まれるスラブがヤードに到着し山積みされてから、そのスラブの上に、仮置き場のスラブを積む作業が必要となる。したがって、この様な作業ができるだけ少なくなるような山分けをすることが望まれる。このような仮置きの発生数は、数学的には逆転数として表現される。逆転数とは、ヤードへの到着順と同一の払出山における積順とが逆転する関係が成立するスラブグループ対の総数である。このように山繰り数は、逆転数で表される。
【００６３】
[[総山数の定式化]]
前述したように、一般的なクリーク分割問題は、枝ｅ（＝｛ｉ，ｊ｝）の重みr(e)の総和を最大化または最小化する問題である。したがって、山分け問題で最も考慮すべき総山数（クリークの総数）に対する評価が考慮出来る様な問題設定になっていない。。よって、クリーク分割問題を山分け問題へ適用するには、総山数の定式化が課題となる。
【００６４】
このような課題に対し、本発明者らは、クリークの総数を求めるには、それぞれのクリークを構成する頂点の数に拘らず、どの様な構成のクリークでも同じ値（この場合「１」）となるような"量"を見つける必要があると考えた。そして、本発明者らは、このようなクリークを構成する頂点の数が多くとも少なくとも同じ値となるような"量"として、クリークを構成する頂点の数が多いほど、各頂点に対する値が小さくなるような量を用いればよいという着想を得た。このような着想の下、本実施形態では、各頂点に対して定義する重みとして、"１／ｐ"（ｐは、クリークにおける１つの頂点に連結する枝数＋１）を採用することとした。分母のp（クリークにおける１つの頂点に連結する枝数＋１）は、当該クリークを構成する頂点の総数を表す。したがって、その逆数である１／ｐの、当該クリークの全ての頂点についての値の和を取ると、１（＝ｐ（当該クリークを構成する頂点の総数）×１／ｐ（＝当該クリークに属する各頂点の持つ重み））となる。よって、この値の全ての頂点での総和を取れば、クリークの総数、すなわち総山数が得られる。
【００６５】
図１に示す無向グラフを、頂点１、２、３、４からなるクリークと、頂点５、６からなるクリークとの２つのクリークに分割される場合を例に挙げて、前述した手法を用いることにより、クリークの総数と総山数とが一致することを説明する。
まず、頂点１、２、３、４からなるクリークにおいて、頂点１に連結する枝数は３であるので、頂点１に対する重みは１／４（＝１／（３＋１））になる。同様に、頂点１、２、３、４からなるクリークにおいて、頂点２、３、４に連結する枝数もそれぞれ３であるので、頂点２、３、４に対する重みはそれぞれ１／４（＝１／（３＋１））になる。
【００６６】
次に、頂点５、６からなるクリークにおいて、頂点５、６に連結する枝数はそれぞれ１であるので、頂点５、６に対する重みはそれぞれ１／２（＝１／（１＋１））になる。
したがって、これらの総和である総山数は２（＝１／４＋１／４＋１／４＋１／４＋１／２＋１／２）であり、クリークの総数に一致する。
【００６７】
以上の考え方に基づき、任意の０−１変数ベクトルｘ→∈Ωに対する総山数（クリーク数）は、以下の（１７）式で表される。尚、前述したように、Ωは、推移性制約を満たす枝集合であり、０−１変数ベクトルｘ→は、変数x([i，j])を要素とするベクトルである。
【００６８】
【数９】
0006540360.tif 000010
【００６９】
[[目的関数の定式化]]
総山数（山高さ）に対する重み係数をｋ1とし、逆転数（＝山繰り数）に対する重み係数をｋ2とすると、前述したように目的関数は「ｋ1×総山数＋ｋ2×逆転数」となる。
任意のｘ∈Ωに対する各払出山の逆転数は、Σe∈Er(e)x(e)で表される。また、総山数は（１７）式で表される。したがって、目的関数は、以下の（１８）式で表される。
【００７０】
【数１０】
0006540360.tif 000011
【００７１】
[[非線形計画問題の混合整数計画問題への変換]]
（１８）式の目的関数は、分母に多項式を持つ有理関数（非線形関数）の和である。したがって、本発明者らは、計算の負荷をより軽減するために、非線形関数を線形化することを検討した。
【００７２】
ここでは、（１８）式の目的関数の第１項の有理関数を線形区分関数で表現することにより線形化する。そのため、頂点（スラブグループ）ｉ毎に、（１８）式の目的関数の第１項の有理関数の上限を表す新たな連続変数αiを導入する。すなわち、以下の（１９）式を満たすべき変数として連続変数αiを定義する。
【００７３】
【数１１】
0006540360.tif 000012
【００７４】
ここで、変数x([i，j])を要素とする０−１変数ベクトルｘ→が、（１８）式の目的関数の値を最小化する問題の許容解であるならば、（１９）式の左辺の分母の多項式の値は、頂点（スラブグループ）ｉを含むクリークを構成する頂点（スラブグループ）の総数に対応する値になる。したがって、（１９）式の左辺の分母の多項式の値は、１以上ｈ以下の整数でなくてはならない。
【００７５】
以上のことから、（１９）式の不等式は、（１９）式の左辺の分母の多項式の値が整数のときにのみに成立すればよい。すなわち、簡単のために（１９）式の不等式の左辺を１／（１＋Ｘ）と表せば、当該左辺は整数点（Ｘ＝０，１，・・・，ｈ−１）のみで、１／（１＋Ｘ）の値と一致する区分線形凸関数で置き換えることができる。
【００７６】
具体的に説明すると、非線形関数（１／（１＋Ｘ））のＸは、Ｘ＝０，１，・・・，ｈ−１という整数値しかとらない。したがって、まず、［０，１］，［１，２］，・・・，［ｈ´−１，ｈ´］，・・・，［ｈ−２，ｈ−１］の区間に分割する。そして、それぞれの区間において、Ｘが整数点であるときのみに、非線形関数（１／（１＋Ｘ））の値に一致するような線形関数で、非線形関数（１／（１＋Ｘ））を近似する。例えば、［０，１］区間であれば、非線形関数（１／（１＋Ｘ））は、（Ｘ，１／（１＋Ｘ））＝（０，１）と（１，１／２）とを結ぶ直線（Ｙ＝（−１／２）Ｘ＋１）に近似される。また、［ｈ´−１，ｈ´］区間であれば、非線形関数（１／（１＋Ｘ））は、（Ｘ，１／（１＋Ｘ））＝（ｈ´−１，１／ｈ´）と（ｈ´，１／（１＋ｈ´））とを結ぶ直線（Ｙ＝（２ｈ´−Ｘ）／｛ｈ´（ｈ´＋１）｝）に近似される。ここで、近似という表現を用いたが、前述したように、（１１）式の左辺の分母の多項式（＝１＋Ｘ）は、整数値しかとらないことから、実現可能な解空間（ｘ(e)∈｛０，１｝）では、非線形関数（１／（１＋Ｘ））と区分線形突関数の値は厳密に一致することになる。
【００７７】
以上のことから、（１９）式は、以下の（２０）式に示すｈ−１個の不等式を用いて表現することができる。
【００７８】
【数１２】
0006540360.tif 000013
【００７９】
以上のようにすることで、非線形関数の項である以下の（２１）式の値の、全ての頂点（スラブグループ）ｉについての総和である以下の（２２）式の値を、整数値しかとり得ないようにすることができる。この特徴を利用して、（１８）式の目的関数の値を最小化する非線形計画問題を混合整数計画問題として定式化することができる。
【００８０】
【数１３】
0006540360.tif 000014
【００８１】
[[混合整数計画問題としての目的関数と制約式の定式化]]
（２２）式の値は整数しかとり得ないことから、整数変数ｚ（ｚ∈Ｚ+（自然数））を定義する。以上のことから、（１８）式は、以下の（２３）式〜（２７）式に変換される。
【００８２】
【数１４】
0006540360.tif 000015
【００８３】
（２３）式において、目的関数にΣi∈Nαiを用いずに、整数変数ｚを用いた理由は、分枝限定法が早く終わる可能性があるからである。具体的に説明すると、前述したように、αiは連続変数であるが、（２４）式の不等式の等号が成立すれば、連続変数αiの全ての頂点（スラブグループ）ｉの総和であるΣi∈Nαi（＝ｚ）は、クリークの総数（総山数）に対応するので、整数になる。したがって、整数変数ｚを用いると、暗に（２４）式において等号が成立することを要請していることになる。すなわち、（変数x(e)（x([i，j])）を要素とする）０−１変数ベクトルｘ→が最適解である場合には、Σi∈Nαiは整数になるので、Σi∈Nαiが整数でない場合には、０−１変数ベクトルｘ→は最適値でないことになる。よって、整数変数ｚを用いると、０−１変数ベクトルｘ→の探索範囲を限定することが期待できる。
【００８４】
[[目的関数と制約式]]
以上より、本実施形態では、以下の（２４）式〜（３３）式の制約式による制約を満足する範囲で、（２３）式の目的関数の値を最小化する変数x(e)（x([i，j])）を導出することになる。
【００８５】
【数１５】
0006540360.tif 000016
【００８６】
（２８）式〜（３０）式は、それぞれ（９）式〜（１１）式に示した推移性制約式に対応し、（２８）式〜（３０）式のｅ、ｆ、ｇは、それぞれ、｛ｉ，ｊ｝、｛ｊ，ｋ｝、｛ｉ，ｋ｝に対応する。（３１）式、（１４）式に示した同一山禁止制約式である。（３３）式は、（１６）式に示した山高さ制約式である。Γ3は、無向グラフ（Ｇ＝（Ｎ，Ｅ））を示す。
【００８７】
したがって、目的関数設定部２０２は、（２３）式の目的関数を設定する。具体的に、目的関数設定部２０２は、例えば、総山数（山高さ）に対する重み係数ｋ1と、逆転数に対する重み係数ｋ2を設定する。これらの重み係数ｋ1、ｋ2は、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。また、目的関数設定部２０２は、山分け対象スラブグループリストに基づいて、変数x(e)（x([i，j])）のｅ（＝ｉ、ｊ）としてとり得る値を設定すると共に、重みr(e)としてとり得る値を設定する。
【００８８】
また、制約式設定部２０３は、（２４）式〜（３３）式の制約式を設定する。具体的に制約式設定部２０３は、例えば、山分け対象スラブグループリストと、幅条件および長さ条件における基準値とに基づいて、同一の山に山積みしてはいけないスラブグループ対（枝）の集合Ｆを導出する。幅条件および長さ条件における基準値は、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。また、制約式設定部２０３は、（２８）式〜（３３）式において、変数x(e)（＝x([i，j])）のｅ（＝ｉ、ｊ）、変数x(f)（＝x(j，k)）のｆ（＝ｊ、ｋ）、変数x(g)（＝x(i，k)）のｇ（＝ｉ、ｋ）としてとり得る値を設定する。また、制約式設定部２０３は、（２４）式、（３３）式において、１つの払出山に積めるスラブの枚数の上界ｈを設定する。１つの払出山に積めるスラブの枚数の上界ｈは、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。
【００８９】
［最適解導出部２０４：最適解導出工程Ｓ３０４］
最適解導出部２０４は、混合整数計画法による最適化計算を行うことによって、（２４）式〜（３３）式の制約式による制約を満足する範囲で、（２３）式の目的関数の値を最小化する変数x(e)（x([i，j])）（すなわち、変数x(e)（x([i，j])）の最適解）を導出する。
【００９０】
本実施形態では、以下の仮定の下で、最適化計算を行う。
（ａ）払出山のスラブを次工程に払い出す際に、払出山の上にあるスラブグループから順に払い出せるように、積順が相対的に上であるスラブグループの次工程への払出順が、積順が相対的に下であるスラブグループの次工程への払出順よりも早くなるように各スラブを山積みする。
【００９１】
（ｂ）次工程へのスラブグループの払出順に自由度がある場合には、ヤードへの到着順が早いスラブグループである程、払出山の下に積む。例えば、同じロット番号のスラブグループについては、次工程へのスラブグループの払出順に制限はない。ロットとは、次工程（例えば、熱延工程）での処理の纏まりを表すもので、ロット番号は、その纏まりの次工程での処理の順番を表す、
（ｃ）ヤードへの到着順は一意に定まり、異なるスラブグループ間での重複はないものとする。
このような仮定により、スラブグループの任意の部分集合Ｎ´⊆Ｎに対し、積み上げる順序が唯一つに定まる。
尚、混合整数計画法による最適化計算は、公知の技術を用いることにより実現されるので、ここでは、その詳細な説明を省略する。
【００９２】
［出力部２０５：出力工程Ｓ３０５］
出力部２０５は、最適解導出部２０４で導出された変数x(e)（x([i，j])）の最適解に基づく情報を出力する。例えば、出力部２０５は、最適解導出部２０４で導出された変数x(e)（x([i，j])）の最適解を出力することができる。この場合、オペレータは、変数x(e)（x([i，j])）の最適解から、山分け対象スラブグループリストに含まれるスラブグループのそれぞれについての、当該スラブグループが属する払出山と当該払出山における積順とを含む情報を作成することができる。また、出力部２０５は、最適解導出部２０４で導出された変数x(e)（x([i，j])）の最適解から、このような情報を導出して出力することができる。その他、出力部２０５は、山分け対象スラブグループリストと、変数x(e)（x([i，j])）の最適解とに基づいて、どのタイミングでどの搬送機器によりどのスラブグループをどの場所に搬送するのかを特定し、特定した内容に基づいて、搬送機器に対する動作指令を行うことができる。このようにする場合には、変数x(e)（x([i，j])）の最適解を出力してもしなくてもよい。
【００９３】
＜まとめ＞
以上のように本実施形態では、総山数を少なくすることと、山繰り数（同一の払出山においてヤードへの到着順が早い方のスラブグループを遅い方のスラブグループよりも上に積むために必要になる山繰りの数）を少なくすることとを目的とする目的関数の値を最小化する最適化問題を数理計画法による最適化計算を行うことにより解く。その際に、頂点をスラブグループに対応させ、枝により相互に連結される２つの頂点に対応する２つのスラブグループを同一の払出山に積まれる２つのスラブグループの候補として表す。そして、クリークの総数を総山数として表現すると共に、逆転の関係が成立する２つのスラブグループに対応する２つの頂点の間の枝の総数（逆転数）を山繰り数として表現する。
【００９４】
したがって、山分け問題をクリーク分割問題に適用することができる。このようにすることによって、山分け計画の立案対象のスラブグループの中に、同一の払出山に積むと山繰り負荷が大きくなるようなスラブグループが多い場合や、山分け計画の立案対象のスラブグループの数が多い場合でも、実用的な時間内でヤードにおける山分け計画を作成することが可能になる。すなわち、解くべき問題の性格に関わらず、実用的な時間内でヤードにおける山分け計画を作成することができる。
【００９５】
例えば、本実施形態では、集合分割問題の様に実行可能山を列挙し、その数だけ変数を用意する必要はなくなる。特許文献１に示す集合分割問題における部分集合の数は、集合の要素数をｎとすると２nとなるので指数時間アルゴリズムになる。これに対し、本実施形態ではｎ2の多項式のオーダの変数により問題を定式化することができる。よって、実行可能山（部分集合）の数に左右されないアルゴリズム構築が可能である。また、特許文献２の手法では定式化に無理のあった山繰り数の評価、すなわち逆転対の評価を自然な形で定式化することができる。これにより実規模の問題を実時間内に計算を完了させることができる。
【００９６】
また、本実施形態では、１つの頂点（スラブグループ）に連結する枝数＋１の逆数の、全ての頂点についての総和を総山数として表現する（（１７）式、（１８）式を参照）。したがって、クリーク分割問題において総山数を定式化することができる。
【００９７】
また、本実施形態では、クリーク（１つの山）における１つの頂点（スラブグループ）に連結する枝数＋１の逆数で表される非線形関数の値に対し、当該クリークにおける１つの頂点に連結する枝数の値でのみ一致する区分線形関数の上限値を当該スラブグループ毎に定める連続変数αiの、全ての頂点（スラブグループ）についての総和（Σi∈Nαi）を総山数として表現する（（２０）式、（２３）式、（２５）式等を参照）。したがって、非線形計画問題を混合整数計画問題に置き換えることができる。よって、混合整数計画法による最適化計算を行うことができ、最適化計算の時間をより短くすることができる。
【００９８】
また、本実施形態では、連続変数αiの、全ての頂点（スラブグループ）についての総和を整数変数ｚとし、整数変数ｚを総山数として表現する（（２３）式、（２５）式等を参照）。したがって、最適解の探索範囲を限定することができ、最適化計算の時間をより一層短くすることができる。
【００９９】
＜変形例＞
［変形例１］
本実施形態では、総山数（山高さ）と山繰り数（逆転数）との重み付き線形和を最小化することを目的とする目的関数を例に挙げて説明した。しかしながら、目的関数は、総山数（山高さ）と山繰り数（逆転数）との重み付き線形和に限定されない。例えば、１つの払出山が出来上がるまでの時間（１つの山を作るための搬送機器の作業時間）の、全ての払出山についての総和と、総山数（山高さ）と、山繰り数（逆転数）との重み付き線形和を目的関数としてもよい。また、１つの払出山において、最初に次工程に払い出すスラブから最後に払い出すスラブを払い出すまでに要する時間（１つの払出山における最初のスラブの払い出し時刻から最後のスラブの払い出し時刻までの時間）の、全ての払出山についての総和と、総山数（山高さ）と、山繰り数（逆転数）との重み付き線形和を目的関数としてもよい。前者について、１つの払出山が出来上がるまでの時間が短ければ、例えば、保温設備をスラブの受け入れのために開けておく時間を短くすることができ、スラブの温度の低下を抑制することができる。後者について、１つの払出山において、最初に次工程に払い出すスラブから最後に払い出すスラブを払い出すまでに要する時間が短ければ、保温設備からの払い出しのために保温設備が開いている時間を短くすることができ、スラブの温度の低下を抑制することができる。
【０１００】
［変形例２］
本実施形態では、目的関数の値を最小化する最適化問題を数理計画法により解く場合を例に挙げて説明した。しかしながら、例えば（２３）式の各項に（−１）を掛けることにより、目的関数の値を最大化する最適化問題としてもよい。
【０１０１】
［変形例３］
本実施形態では、全てのスラブの厚みが同じである場合を例に挙げて説明した。しかしながら、スラブの厚みは同じでなくてもよい。この場合、w(i)を、スラブグループｉに含まれるスラブの厚みの総和とすればよい。
【０１０２】
［変形例４］
本実施形態では、非線形関数を線形区分凸関数に変形し、非線形計画問題を混合整数計画問題に変換して定式化する場合を例に挙げて説明した。前述したように、このようにすれば、最適化計算の時間を短くすることができるので好ましい。しかしながら、非線形計画法による最適化計算を行ってもよい。
【０１０３】
［変形例５］
本実施形態では、連続変数αiの、全ての頂点（スラブグループ）についての総和（Σi∈Nαi）を整数変数ｚとし、整数変数ｚを総山数として表現する場合を例に挙げて説明した。前述したように、このようにすれば、最適解の探索範囲を狭めることができるので好ましい。しかしながら、整数変数ｚを用いずに、連続変数αiの、全ての頂点（スラブグループ）についての総和（Σi∈Nαi）を総山数としてそのまま用いて定式化してもよい。
【０１０４】
［変形例６］
本実施形態では、スラブグループ単位で山分け計画を作成する場合を例に挙げて説明した。しかしながら、１つのスラブ単位で山分け計画を作成してもよい。その場合には、これまでの説明の「スラブグループ」を「スラブ」と読み替え、その鋼材数は１枚となり（したがって、例えば、スラブグループｉ、ｊのスラブ数w(i)、w(j)の値は「１」になる）、最大幅と最小幅が当該スラブの幅で同じ値となる。最大長、最小長も同様に当該スラブの長さで同じ値となる。
【０１０５】
（第２の実施形態）
次に、第２の実施形態を説明する。第１の実施形態では、１つの頂点（スラブグループ）に連結する枝数＋１の逆数の、全ての頂点についての総和を総山数として表現する場合を例に挙げて説明した（１７）式、（１８）式を参照）。これに対し、本実施形態では、１つの頂点（スラブグループ）に含まれるスラブの枚数を、当該頂点を含むクリーク（山）を構成する全ての頂点（スラブグループ）に含まれるスラブの総数で割った値の、全ての頂点についての総和を総山数として表現する。このように本実施形態と第１の実施形態とは、総山数の表現が主として異なる。したがって、本実施形態の説明において、第１の実施形態と同一の部分については、図１〜図３に付した符号と同一の符号を付す等して詳細な説明を省略する。
【０１０６】
[[総山数の定式化]]
図１に示す無向グラフを、頂点１、２、３、４からなるクリークと、頂点５、６からなるクリークとの２つのクリークに分割される場合を例に挙げて、本実施形態のように総山数を表現しても、クリークの総数と総山数とが一致することを説明する。ここで、頂点１、２、３、４、５、６に対応するスラブグループのスラブの枚数が、それぞれ３枚、２枚、１枚、４枚、２枚、２枚であるものとする。
【０１０７】
頂点１（スラブグループ）のスラブの枚数（＝３）を、頂点１を含むクリークを構成する全ての頂点１、２、３、４（スラブグループ）のスラブの総数（＝１０（＝３＋２＋１＋４））で割った値は３／１０である。同様に、頂点２、３、４のスラブの枚数（＝２、１、４）を、頂点１を含むクリークを構成する全ての頂点１、２、３、４（スラブグループ）のスラブの総数（＝１０）で割った値は、それぞれ２／１０、１／１０、４／１０である。さらに、頂点５、６（スラブグループ）のスラブの枚数（＝２、２）を、頂点１を含むクリークを構成する全ての頂点５、６（スラブグループ）のスラブの総数（＝４（２＋２））で割った値は、それぞれ１／２、１／２である。そして、これらの総和である総山数は、２（３／１０＋２／１０＋１／１０＋４／１０＋１／２＋１／２）であり、クリークの総数に一致する。
【０１０８】
以上の考え方に基づき、任意の０−１変数ベクトルｘ→∈Ωに対する総山数（クリーク数）は、以下の（３４）式で表される。
【０１０９】
【数１６】
0006540360.tif 000017
【０１１０】
（３４）式は、第１の実施形態で説明した（１７）式の代わりとなる式である。
[[目的関数の定式化]]
第１の実施形態で説明したように、総山数（山高さ）に対する重み係数をｋ1とし、逆転数に対する重み係数ｋ2とすると、前述したように目的関数は「ｋ1×総山数＋ｋ2×逆転数」となる。
任意のｘ∈Ωに対する各山の逆転数は、Σe∈Er(e)x(e)で表される。また、総山数は（３４）式で表される。したがって、目的関数は、以下の（３５）式で表される。
【０１１１】
【数１７】
0006540360.tif 000018
【０１１２】
（３５）式は、第１の実施形態で説明した（１８）式の代わりとなる式である。
[[非線形計画問題の混合整数計画問題への変換]]
（３５）式の目的関数は、（１８）式と同様に、分母に多項式を持つ有理関数（非線形関数）の和である。したがって、本実施形態でも、第１の実施形態と同様に、非線形関数を線形化する。
【０１１３】
すなわち、（３５）式の目的関数の第１項の有理関数を線形区分関数で表現することにより線形化する。そのため、頂点（スラブグループ）ｉ毎に、（３５）式の目的関数の第１項の有理関数の上限を表す新たな連続変数βiを導入する。すなわち、以下の（３６）式を満たすべき変数として連続変数βiを定義する。
【０１１４】
【数１８】
0006540360.tif 000019
【０１１５】
（３６）式は、第１の実施形態で説明した（１９）式の代わりとなる式である。
第１の実施形態で説明したのと同様に、変数x([i，j])を要素とする０−１変数ベクトルｘ→が、（３５）式の目的関数の値を最小化する問題の許容解であるならば、（３６）式の左辺の分母の多項式の値は、頂点（スラブグループ）ｉが属するクリークを構成する頂点（スラブグループ）の総数に対応する値になる。したがって、（３６）式の左辺の分母の多項式の値は、１以上ｈ以下の整数でなくてはならない。よって、（３６）式の不等式は、（３６）式の左辺の分母の多項式の値が整数のときにのみに成立すればよい。
【０１１６】
以上のことから、簡単のために（３６）式の不等式の左辺をw(i)／（w(i)＋Ｘ）とみなせば、当該左辺は整数点（Ｘ＝０，１，・・・，ｈ−１）のみで、w(i)／（w(i)＋Ｘ）の値と一致する区分線形凸関数で置き換えることができる。
【０１１７】
例えば、［ｈ´−１，ｈ´］区間であれば、非線形関数（w(i)／（w(i)＋Ｘ））は、（ｈ´−１，w(i)／（w(i)＋ｈ´−１））と、（ｈ´，w(i)／（w(i)＋ｈ´））とを結ぶ以下の（３７）式の方程式で表される。
【０１１８】
【数１９】
0006540360.tif 000020
【０１１９】
以上のことから、（３６）式は、以下の（３８）式に示すｈ−１個の不等式を用いて表現することができる。
【０１２０】
【数２０】
0006540360.tif 000021
【０１２１】
（３８）式は、第１の実施形態で説明した（２０）式の代わりとなる式である。
以上のようにすることで、非線形関数の項である以下の（３９）式の値の、全ての頂点（スラブグループ）ｉでの総和である以下の（４０）式の値を、整数値しかとり得ないようにすることができる。この特徴を利用して、（３５）式の目的関数の値を最小化する非線形計画問題を混合整数計画問題として定式化することができる。
【０１２２】
【数２１】
0006540360.tif 000022
【０１２３】
（３９）式、（４０）式は、それぞれ、第１の実施形態で説明した（２１）式、（２２）式の代わりの式となる。
[[混合整数計画問題としての目的関数と制約式の定式化]]
（３９）式の値は整数しかとり得ないことから、整数変数ｚ（ｚ∈Ｚ+（自然数））を定義する。以上のことから、（３５）式は、以下の（４１）式〜（４５）式に変換される。
【０１２４】
【数２２】
0006540360.tif 000023
【０１２５】
（４１）式において、目的関数にΣi∈Nβiを用いずに、整数変数ｚを用いた理由は、第１の実施形態で説明したように、分枝限定法が早く終わる可能性があるからである。
（４１）式〜（４５）式は、それぞれ第１の実施形態で説明した（２３）式〜（２７）式の代わりの式となる。
[[目的関数と制約式]]
以上より、本実施形態では、以下の（２７）式〜（３３）式、（４１）式〜（４３）式の制約式による制約を満足する範囲で、（２３）式の目的関数の値を最小化する変数x(e)（x([i，j])）を導出することになる。
【０１２６】
【数２３】
0006540360.tif 000024
【０１２７】
（２３）式に示すように目的関数は、第１の実施形態と同じである。（２８）式〜（３０）式は、第１の実施形態で説明した推移性制約式である。（３１）式は、第１の実施形態で説明した同一山禁止制約式である。（３３）式は、第１の実施形態で説明した山高さ制約式である。（２７）式は、第１の実施形態と同様に、整数変数ｚが自然数であることを示す制約式である。
【０１２８】
したがって、目的関数設定部２０２は、（２３）式の目的関数を設定する。また、制約式設定部２０３は、（２７）式〜（３３）式、（４１）式〜（４３）式の制約式を設定する。目的関数と制約式の設定は、例えば、第１の実施形態で説明したのと同様にして行われる。
【０１２９】
以上のように、１つの頂点（スラブグループ）のスラブの枚数を、当該頂点を含むクリーク（山）を構成する全てのスラブグループのスラブの総数で割った値の、全ての頂点についての総和を総山数として表現しても、第１の実施形態と同様の効果が得られる。
【０１３０】
尚、第１、第２の実施形態で説明した総山数の表記は一例であり、第１の実施形態の[[総山数の定式化]]の欄において着想点として説明したように、１つのクリークを構成する頂点に対する重みの総和が１になるように頂点の夫々に対して重みを設定し、頂点の夫々に対して設定された重みの、無向グラフを構成する頂点の全てについての総和により総山数を表現していれば、総山数を表す関数は、第１、第２の実施形態で説明したものに限定されない。
また、本実施形態においても、第１の実施形態で説明した種々の変形例を採用することができる。
【０１３１】
（第３の実施形態）
次に、第３の実施形態を説明する。本実施形態は、第１の実施形態で説明した連続変数αiの、全ての頂点（スラブグループ）についての総和（Σi∈Nαi）と、第２の実施形態で説明した連続変数βiの、全ての頂点（スラブグループ）についての総和（Σi∈Nβi）との双方を共通の整数変数ｚとして定式化し、第１の実施形態と第２の実施形態の双方の制約式を用いる。このように本実施形態は、第１、第２の実施形態による制約式を組み合わせたものとなる。したがって、本実施形態の説明において、第１、第２の実施形態と同一の部分については、図１〜図３に付した符号と同一の符号を付す等して詳細な説明を省略する。
【０１３２】
[[目的関数と制約式]]
本実施形態では、以下の（２４）式〜（３３）式、（４１）式〜（４３）式の制約式による制約を満足する範囲で、（２３）式の目的関数の値を最小化する変数x(e)（x([i，j])）を導出することになる。
【０１３３】
【数２４】
0006540360.tif 000025
【０１３４】
したがって、目的関数設定部２０２は、（２３）式の目的関数を設定する。また、制約式設定部２０３は、（２４）式〜（３３）式、（４１）式〜（４３）式の制約式を設定する。目的関数と制約式の設定は、例えば、第１の実施形態で説明したのと同様にして行われる。
【０１３５】
以上のように、連続変数αiの、全ての頂点（スラブグループ）についての総和（Σi∈Nαi）と、連続変数βiの、全ての頂点（スラブグループ）についての総和（Σi∈Nβi）との双方を共通の整数変数ｚとして定式化すれば、最適解の探索範囲をより一層狭めることができる。
尚、本実施形態においても、第１の実施形態で説明した種々の変形例を採用することができる。
【０１３６】
（実施例）
次に、実施例を説明する。
本実施例では、第３の実施形態による解法（発明例）と、特許文献１による解法（比較例１）と、特許文献２による解法（比較例２）とのそれぞれにより、山分け計画を作成し、求解に要する時間の比較を行った。ただし、計算時間が３分（１８０秒）以上となる場合には、その時点で得られた解の精度を表す双対ギャップにより評価した。
双対ギャップは、以下の（４４）式で表される。
双対ギャップ＝｛（上界値−下界値）／上界値｝×１００  ・・・（４４）
【０１３７】
（４４）式において、上界値は、計算を開始してから３分が経過した時点で得られた、山分け計画を実現可能な解の中で最も良い解の目的関数の値である。下界値は、計算を開始してから３分が経過した時点で得られた、緩和問題を解いた場合の最適解の中で、最も大きな（最も悪い）目的関数の値である。尚、上界値と下界値とが一致した場合、そのときの解は最適解である。また、緩和問題とは、最適化問題の０−１変数の条件を緩和した（０−１変数が０、１以外の０〜１の間の値をとることを許容した）問題をいう。
【０１３８】
また、何れの解法でも、スラブグループの総数を５０とし、同一のスラブグループについて、山分け計画を作成した（すなわち、同一の山分け対象スラブグループリストを用いた）。
また、何れの解法でも、ｋ1×総山数＋ｋ2×逆転数を目的関数とした。ここで、総山数（山高さ）に対する重み係数ｋ1を５．０（ｋ1＝５．０）とし、逆転数に対する重み係数ｋ2を１．０（ｋ2＝１．０）とした。
図４は、これらの解法による山分け計画の作成結果を表形式に示す図である。
【０１３９】
図４において、「禁止％」とは、スラブグループ対の総数に対する、同一の払出山に山積みしてはいけないスラブグループ対（枝）の数の割合を、百分率で表記したものである。「逆転％」とは、スラブグループ対の総数から同一の払出山に山積みしてはいけないスラブグループ対の数を差し引いた値に対する、ヤードへの到着順と払出山における積順とが逆転するスラブグループ対の数の割合を、百分率で表記したものである。「Ｆ．Ｍｔ」は、実現可能山の数（単位は百万個）である。「Ｏｐｔ．Ｖ」は、最適解が得られたときの目的関数の値、または、上界値である。「山数」は、最適化計算の結果として得られた払出山の数である。「逆転」は、最適化計算の結果として得られた、ヤードへの到着順と払出山における積順とが逆転するスラブグループ対の数である。
【０１４０】
図４に於いて色塗りをしているのは、３つの解法のうちで最良の解が得られたものである。図４に示すように、実現可能山の数が数千万規模になると、比較例１（特許文献１）の解法では、３分の計算時間内に山分けを実現可能な解を得られなかった。また、比較例２（特許文献２）の解法でも、発明例（前述した実施形態）の解法に比べ、３分の計算時間内に最適解が得られない場合が多く、且つ、解の精度も悪い（すなわちＯｐｔ．Ｖの値が大きい）。一方、発明例（前述した実施形態）の解法では、問題の規模に関わらず安定した求解結果が得られる。尚、データＩＤが「０３」、「０５」、「１５」、「２１」において、発明例（前述した実施形態）の解法では、３分の計算時間内に計算が収束しておらず、３つの解法のうちでの最良解が得られていない。このうち、「０３」、「１５」、「２１」に於いて、、Ｏｐｔ．Ｖの値は、比較例１（特許文献１）の値と同じであるので、結果として最適解が得られていることになる。また、データＩＤが「０５」に於いても、Ｏｐｔ．Ｖの値は、比較例１（特許文献１）で得られた最適解の値とほぼ同じである。従って、本実施例の全てのケースに於いて、発明例（前述した実施形態）の解法では、３つの解法のうちの最良解、或いは、最良解で無い場合にも、最良解とほぼ等しいＯｐｔ．Ｖの値が得られたことが分かる。
【０１４１】
（その他の変形例）
尚、以上説明した本発明の実施形態は、コンピュータがプログラムを実行することによって実現することができる。また、前記プログラムを記録したコンピュータ読み取り可能な記録媒体及び前記プログラム等のコンピュータプログラムプロダクトも本発明の実施形態として適用することができる。記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
また、以上説明した本発明の実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【０１４２】
（請求項との関係）
以下に請求項と実施形態との関係の一例を示す。尚、請求項と実施形態との関係が以下の関係に限定されないのは、変形例等で説明した通りである。
＜請求項１、２、１１＞
目的関数設定手段は、例えば、目的関数設定部２０２を用いることにより実現される。
払出山の総数を評価する項は、例えば、（１８）式、（２３）式、（３５）式の第１項を用いることにより実現される。
山繰り数を評価する項は、例えば、（１８）式、（２３）式、（３５）式の第２項を用いることにより実現される。
制約式設定手段は、例えば、制約式設定部２０３を用いることにより実現される。
最適解導出手段は、例えば、最適解導出部２０４を用いることにより実現される。
払出山の総数は、例えば、（１７）式を用いることにより実現される。
山繰り数は、例えば、（２３）式の第２項のｋ2を除く部分を用いることにより実現される。
＜請求項３＞
払出山の総数は、例えば、（１７）式、（３４）式、または、（２５）式および（４２）式で定義される（２３）式の第１項の整数変数ｚを用いることにより実現される。
＜請求項４＞
払出山の総数は、例えば、（３４）式を用いることにより実現される。
＜請求項５＞
払出山の総数は、例えば、（２５）式および（４２）式で定義される（２３）式の第１項の整数変数ｚを用いることにより実現される（変形例５も参照）。
＜請求項６、７＞
連続変数は、例えば、連続変数αi、βiを用いることにより実現される（変形例５も参照）。整数変数は、整数変数ｚを用いることにより実現される。
＜請求項８＞
山高さ制約式は、例えば、（１６）式を用いることにより実現される。
＜請求項９＞
同一山禁止制約式は、例えば、（１４）式、（１５）式を用いることにより実現される。
＜請求項１０＞
鋼材グループは、例えば、スラブグループに対応する。
＜請求項１２＞
推移性制約式は、例えば、（９）式〜（１１）式を用いることにより実現される。
第１の頂点、第２の頂点、第３の頂点は、例えば、（９）式〜（１１）式に示すスラブグループｉ、ｊ、ｋに対応する頂点により実現される。
【符号の説明】
【０１４３】
２００：鋼材の山分け計画立案装置、２０１：入力部、２０２：目的関数設定部、２０３：制約式設定部、２０４：最適解導出部、２０５：出力部
【図１】
0006540360.tif 000026
【図２】
0006540360.tif 000027
【図３】
0006540360.tif 000028
【図４】
0006540360.tif 000029
【図５】
0006540360.tif 000030