(57)【特許請求の範囲】
【請求項１】
鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様な順に積み上げて、該ヤードの後工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画装置であって、
前記山分け計画を決定する際に決定されるべき変数である決定変数を設定する決定変数設定手段と、
前記複数の鋼材それぞれを前記複数の払出山のうちの１つに割り当てるときの制約である山仕分け制約式を設定する山仕分け制約式設定手段と、
該払出山の積姿に関する制約である積姿制約式を設定する積姿制約式設定手段と、
前記払出山の総数を少なくすることと、同一の前記払出山に積まれる任意の二つの前記鋼材について、ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を少なくすることと、を目的とする目的関数を設定する目的関数設定手段と、
前記山仕分け制約式と、前記積姿制約式とを満足し、前記目的関数を最小にする様に山分けを決定する山仕分け決定手段とを有し、
前記決定変数には、
前記鋼材のうちの一の鋼材が、前記払出山のそれぞれについて選択される、当該払出山を代表する１つの前記鋼材である代表鋼材が代表する払出山に積まれる場合には、当該代表鋼材が前記一の鋼材を代表するものとし、前記一の鋼材が前記代表鋼材が代表する払出山に積まれない場合は当該代表鋼材が前記一の鋼材を代表しないものとする代表関係変数を含み、
前記山仕分け制約式は、
前記代表鋼材が、当該代表鋼材自身と、当該代表鋼材が代表する払出山に積まれる鋼材を代表することを規定する第１の制約式と、
前記積姿制約式に違反する為に同一の払出山に積むことが出来ない任意の２つの前記鋼材は、一方の前記鋼材が他方の前記鋼材を代表しないことを規定する第２の制約式と、
前記積姿制約式に違反する為に同一の払出山に積むことが出来ない任意の２つの鋼材は、当該２つの鋼材と異なる前記鋼材には代表されないことを規定する第３の制約式と、
全ての前記鋼材が、何れかの代表鋼材によって代表されることを規定する第４の制約式と、
それぞれの前記払出山に積まれる前記鋼材の総数を示す値である、前記それぞれの代表鋼材が代表する鋼材の総数が、上限値以下であることを規定する第５の制約式と、
一方がもう一方を代表する任意の二つの前記鋼材について、ヤードへの到着順が早い鋼材を上に積む場合に前記逆転の関係が生じることを規定する第６の制約式と、
を含み、
前記目的関数において、
前記代表鋼材の総数を前記払出山の総数とし、前記第６の制約式で規定される前記逆転の関係にある鋼材の対の数を前記逆転対の数とすることを特徴とする鋼材の山分け計画立案装置。
【請求項２】
前記鋼材には、一意の序列が付与され、
前記山仕分け制約式は、前記序列が相対的に低い前記鋼材は、前記序列が相対的に高い鋼材を代表することができないことを規定する第７の制約式を更に含むことを特徴とする請求項１に記載の鋼材の山分け計画立案装置。
【請求項３】
前記逆転の関係が成立する数が相対的に多い前記鋼材に付与される前記序列を、前記逆転の関係が成立する数が相対的に少ない前記鋼材に付与される前記序列よりも高くすることを特徴とする請求項２に記載の鋼材の山分け計画立案装置。
【請求項４】
前記山分け計画を、複数の鋼材からなる鋼材グループの単位で立案することを特徴とする請求項１〜３の何れか１項に記載の鋼材の山分け計画立案装置。
【請求項５】
請求項１〜４の何れか１項に記載の鋼材の山分け計画立案装置の各手段としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鋼材の山分け計画立案装置およびプログラムに関し、特に、ヤードにおける鋼材の山分け計画を立案するために用いて好適なものである。
【背景技術】
【０００２】
金属製造プロセスの一例である鉄鋼プロセスにおいて、例えば製鋼工程から次工程の圧延工程へ鋼材を搬送する際、鋼材は、一旦ヤードと呼ばれる一時保管場所に置かれた後、次工程である圧延工程の処理時刻に合わせてヤードから搬出される。そのヤードのレイアウトの一例を図８に示す。ヤードとは、図８に示すように、上流工程より払い出されたスラブなどの鋼材を、下流工程に供給するためのバッファーエリアとして、縦横に区画された置場８０１〜８０４である。縦方向の分割区分を"棟"、横方向の分割区分を"列"と称することが多い。クレーン(１Ａ、１Ｂ、２Ａ、２Ｂ)は棟内を移動可能であり、同一棟内での異なる列の間で鋼材の移送を行う。また搬送テーブルにより棟間の鋼材の移送を行う。搬送指令を作成する際は"棟"及び"列"を指定することにより、どこへ鋼材を搬送するかを示す（図８の置場８０１〜８０４に括弧書きで付されている番号（１１）、（１２）、（２１）、（２２）を参照）。
【０００３】
図８を例にヤードでの基本的な作業の流れを示す。まず、前工程である製鋼工程の連鋳機８１０から搬出された鋼材は、パイラー８１１を経由して受入テーブルＸでヤードまで搬入され、クレーン１Ａ、１Ｂ、２Ａ、２Ｂにより、区画された置場８０１〜８０４の何れかに搬送され、山積みして置かれる。そして、次工程である圧延工程の製造スケジュールに合わせ、再びクレーン１Ａ、１Ｂ、２Ａ、２Ｂにより払出テーブルＺに載せられ、圧延工程へと搬送される。一般に、ヤードにおいて鋼材は、前記の様に山積みされた状態で置かれる。これは、限られたヤード面積を有効に活用するためである。一方、鋼材を積み上げる際、次工程へ供給し易いよう、次工程の処理順番に鋼材が上から積まれている必要がある。さらに、積み姿が不安定な逆ピラミッド状に鋼材を積まないようにする必要がある。このように、鋼材を複数の最適山（＝払出山：次工程へ払い出す最終的な山姿となった山）に分けることを山分けと呼ぶ。
【０００４】
ここで、次工程である圧延工程の加熱炉の燃料原単位を削減するため、可及的に高い温度の鋼材を加熱炉に払い出す（装入する）ことが求められる。このため、昨今、ヤード内に保温設備を設置し、保温設備の中に前述したようにして鋼材を山積みした状態で保管することが行われている。このように保温設備を用いる場合でも、置場８０１〜８０４に直接鋼材を山積みする場合と同様に、保温設備を有効に活用するため、保温設備の中において、可及的に高さの高い払出山を作成することが必要である。また、次工程の処理順番に鋼材が上から積まれるようにすると共に逆ピラミッド状に鋼材を積まないようにする必要がある。
【０００５】
以上のように、サイズや次工程での処理順序が異なる複数の鋼材を複数の山に分けて山積みする山分け計画を立案する際には、計画の立案対象となる鋼材により生成可能な全ての山分け候補の中から、山数と山繰り負荷（クレーン等の搬送設備による鋼材のハンドリング負荷）を最小化する最適化問題を解くことになるが、計画の立案対象となる鋼材の数が多いと、かかる問題は大規模問題となる。
【０００６】
そこで、特許文献１には、計画の立案対象となる鋼材を要素とする全体集合に対し、山積み制約を満たす部分集合である実現可能山を全て列挙し、山数および山繰り負荷を最小化する目的関数の下、集合分割問題として最適な実現可能山の組み合わせを求めることにより最適な山分け計画を行う手法が開示されている。
【０００７】
また、特許文献２には、複数の搬送ロット（一度に搬送機器により搬送できる鋼材のまとまり）をしかるべき山（最適山＝払出山）に割り当てる、多対１の割当問題として定式化する手法が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−１３７６１２号公報
【特許文献２】特開２０１１−１０５４８３号公報
【非特許文献】
【０００９】
【非特許文献１】M. Campleo, R. Correa, and Y. Frota, "Cliques, holes and the vertex coloring polytope," Information Processing Letters, 89 (2004), pp. 159-164
【非特許文献２】M. Campelo, V. A. Campos, and R. C. Correa, "On the asymmetric representatives formulation for the vertex coloring problem," Discrete Applied Mathematics, 156 (2008), pp. 1097-1111
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１、２に記載の方法には、以下の課題がある。
まず、特許文献１に示す集合分割問題を応用した解法では、任意の鋼材ペアのサイズ（幅・長さ）の条件と払出順の条件とから要請される積み順が食い違うことにより、同一の山にできない鋼材ペアが比較的少ない場合には、実現可能山の数が多くなる。この数が数百万を超えると、実現可能山の列挙および最適山の算出計算のいずれにも時間を要し、要請される時間内（例えば３〜５分程度）には計算が完了せず計画が作成できないこととなる。山分け問題の場合、実現可能山の数が数千万を超えると実用的な時間（例えば１０分程度）内では実現可能解を得ることが難しくなる。このような場合には、特許文献２に示す多対１の割当問題として定式化する方法により、許容可能な時間内に求解出来るケースもあり得る。しかしながら、特許文献２に示す方法にも、以下の課題がある。
【００１１】
すなわち、特許文献２に示す方法では、ヤードへの到着順とヤードにおける積み順とが逆になるような鋼材ペア（逆転対）が多い場合に計算時間を要し、実用的な時間内に計算を完了できない虞がある。
【００１２】
この様に、従来の方法では、問題の性格に応じ、実用的な時間内に求解が可能な場合と不可能な場合とがある。したがって、どの様な問題に対しても安定的に求解できる手法が求められている。また、実現可能山の数が数千万を超え、逆転対の比率が高い鋼材群の山分け計画を作成する場合には、実用的な時間内に求解することはできない。よって、実現可能山の数が一千万を超える様な大規模な問題の場合や、逆転対が多い場合にも、実用的な時間内に求解する方法が必要である。
【００１３】
本発明は、以上のような問題点に鑑みてなされたものであり、解くべき問題の性格に関わらず、実用的な時間内で山分け計画を立案できるようにすることを目的とする。
【課題を解決するための手段】
【００１４】
本発明の鋼材の山分け計画立案装置は、鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入された複数の鋼材を、次工程への払出順が早い鋼材が上になる様な順に積み上げて、該ヤードの後工程に払い出すための複数の払出山を作成するための山分け計画を立案する鋼材の山分け計画装置であって、前記山分け計画を決定する際に決定されるべき変数である決定変数を設定する決定変数設定手段と、前記複数の鋼材それぞれを前記複数の払出山のうちの１つに割り当てるときの制約である山仕分け制約式を設定する山仕分け制約式設定手段と、該払出山の積姿に関する制約である積姿制約式を設定する積姿制約式設定手段と、前記払出山の総数を少なくすることと、同一の前記払出山に積まれる任意の二つの前記鋼材について、ヤードへの到着順が早い方の前記鋼材が遅い方の前記鋼材よりも上に積まれる逆転の関係にある逆転対の数を少なくすることと、を目的とする目的関数を設定する目的関数設定手段と、前記山仕分け制約式と、前記積姿制約式とを満足し、前記目的関数を最小にする様に山分けを決定する山仕分け決定手段とを有し、前記決定変数には、前記鋼材のうちの一の鋼材が、前記払出山のそれぞれについて選択される、当該払出山を代表する１つの前記鋼材である代表鋼材が代表する払出山に積まれる場合には、当該代表鋼材が前記一の鋼材を代表するものとし、前記一の鋼材が前記代表鋼材が代表する払出山に積まれない場合は当該代表鋼材が前記一の鋼材を代表しないものとする代表関係変数を含み、前記山仕分け制約式は、前記代表鋼材が、当該代表鋼材自身と、当該代表鋼材が代表する払出山に積まれる鋼材を代表することを規定する第１の制約式と、前記積姿制約式に違反する為に同一の払出山に積むことが出来ない任意の２つの前記鋼材は、一方の前記鋼材が他方の前記鋼材を代表しないことを規定する第２の制約式と、前記積姿制約式に違反する為に同一の払出山に積むことが出来ない任意の２つの鋼材は、当該２つの鋼材と異なる前記鋼材には代表されないことを規定する第３の制約式と、全ての前記鋼材が、何れかの代表鋼材によって代表されることを規定する第４の制約式と、それぞれの前記払出山に積まれる前記鋼材の総数を示す値である、前記それぞれの代表鋼材が代表する鋼材の総数が、上限値以下であることを規定する第５の制約式と、一方がもう一方を代表する任意の二つの前記鋼材について、ヤードへの到着順が早い鋼材を上に積む場合に前記逆転の関係が生じることを規定する第６の制約式と、を含み、前記目的関数において、前記代表鋼材の総数を前記払出山の総数とし、前記第６の制約式で規定される前記逆転の関係にある鋼材の対の数を前記逆転対の数とすることを特徴とする。
【００１６】
本発明のプログラムは、前記鋼材の山分け計画立案装置の各手段としてコンピュータを機能させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、解くべき問題の性格に関わらず、実用的な時間内で山分け計画を立案することができる。
【図面の簡単な説明】
【００１８】
【図１】単純無向グラフの一例を示す図である。
【図２】鋼材の山分け計画立案装置の機能的な構成の一例を示す図である。
【図３】鋼材の山分け計画立案装置の動作の一例を説明するフローチャートである。
【図４】スラブグループに対して順序付け（番号付け）を行う方法の一例を概念的に説明する図である。
【図５】スラブグループに対して順序付け（番号付け）を行う方法の一例を説明するフローチャートである。
【図６】山分け計画の作成結果の第１の例を表形式に示す図である。
【図７】山分け計画の作成結果の第２の例を表形式に示す図である。
【図８】ヤードのレイアウトの一例を示す図である。
【発明を実施するための形態】
【００１９】
＜頂点彩色問題の概要＞
後述するように本実施形態では、頂点彩色問題を山分け問題に適用する。頂点彩色問題自体は公知の技術であるが、頂点彩色問題を山分け問題に適用する際の本実施形態との差異を明確にするため、本発明の実施形態を説明する前に、一般的な頂点彩色問題について説明する。
【００２０】
図１は、単純無向グラフの一例を示す図である。
頂点彩色問題は、グラフ理論における著名な問題の一つであり、単純無効グラフＧ＝（Ｖ，Ｅ）上で定義される（Ｖ:グラフの頂点集合、Ｅ：グラフの辺（枝）集合）。図１に示すように、単純無向グラフＧの各頂点をある色で塗り、しかも隣接する（辺で結ばれた）どの２つの頂点も異なる色で塗り分けられるとき、この着色を単純無向グラフＧの彩色と呼ぶ。彩色に用いた色がｃ色（ｃは２以上の整数）のとき、単純無向グラフＧはｃ−彩色可能であるという。単純無向グラフＧがｃ−彩色可能となるｃの最小値を、単純無向グラフＧの彩色数といい、χ（Ｇ）で表す。頂点彩色問題は、単純無向グラフＧにおける彩色数χ（Ｇ）を求める問題である。
【００２１】
頂点彩色問題の解法として、非特許文献１、２に記載されている対称代表点法および非対称代表点法がある。対称代表点法および非対称代表点法を用いることにより、頂点彩色問題の一般的な解法に比べ、問題を高速に解くことができることが期待できる。
【００２２】
［対称代表点法］
対称代表点法では、単純無向グラフＧの彩色に関して、各色から一つずつその色の代表点となる頂点を選ぶ。代表点となった頂点は、その頂点自身と同色の他の頂点を代表する。代表点は、異なる色の頂点を代表しないものとする。任意の順序付頂点対（ｕ，ｖ）∈Ｖ2について、０‐１変数ｘuvを導入する。この変数ｘuvは、頂点ｕが頂点ｖを代表している場合に「１」となり、そうでない場合に「０（ゼロ）」となる０−１変数として定義される。
【００２３】
ｘuv＝１の場合、順序付頂点対[ｕ，ｖ]は、一方が他方を代表する関係にあるものとする。仮に、頂点ｖが代表点であれば、ｘvv＝１となる。このとき、単純無向グラフＧの各頂点に対して彩色された色数は、代表点の数に等しく、Σv∈Vｘvvで表される。単純無向グラフＧにおいて隣接する（すなわち辺（枝）で相互に結ばれた）順序付頂点対｛ｕ，ｖ｝∈Ｅは同じ色に彩色することができないため、これら２つの頂点ｕ，ｖは、一方が他方を代表する関係にない。よって、ｘuv＝ｘvu＝０となる。また、単純無向グラフＧにおいて隣接する順序付頂点対｛ｕ，ｖ｝∈Ｅは、同じ頂点tを代表点として持つことができない。よって、ｘtu＋ｘtv≦ｘtt  （∀ｔ∈Ｖ，∀｛ｕ，ｖ｝∈Ｅ）を満たさなければならない。また、全ての頂点は、それ自身または他の頂点の内の一つに必ず代表されなければならない。よって、全ての頂点ｖ∈Ｖについて、Σu∈Vｘuv＝１が成り立つ。また、頂点ｕが他の頂点を代表するとき、頂点ｕ自身は代表点でなくてはならない。すなわち、全ての頂点ｕ、ｖについてｘuv≦ｘuuが満たされなければならない。したがって、対称代表点法においては、以下の（ｂ）式〜（ｆ）式の制約式を満足する範囲で（ａ）式の目的関数を最小化する変数ｘvvを導出することになる。
【００２４】
【数１】
0006515339.tif 000002
【００２５】
［非対称代表点法］
単純無向グラフＧの頂点集合ＶをＶ＝｛１，２，・・・，ｎ｝とし、これらの頂点に対し、正の整数の大小関係で頂点の全ての順序が与えられているとする。対称代表点法では全ての頂点が代表点になることが可能である。これに対し、非対称代表点法では、ｕ＜ｖで順序付けられた順序付頂点対｛ｕ，ｖ｝について、頂点ｖは頂点ｕを代表することができない。よって、全てのｕ＜ｖとなる順序付頂点対｛ｕ，ｖ｝に対し、ｘvu＝０が満たされなければならない。したがって、非対称代表点法においては、以下の（ｂ）式〜（ｆ）式の制約式を満足する範囲で（ａ）式の目的関数を最小化する変数ｘvvを導出することになる。
【００２６】
【数２】
0006515339.tif 000003
【００２７】
このように、非対称代表点法では、対称代表点法における制約式に（ｇ）式が追加されたものになる（その他は、非対称代表点法と対称代表点法とで異なるところはない）。
また、（ｇ）式によりｕ＜ｖにおけるｘvuの値が規定されているので、（ｂ）式、（ｃ）式、および（ｅ）式は、以下の（ｂ´）式、（ｃ´）式、および（ｅ´）式を非対称点法における制約式としてもよい。
【００２８】
【数３】
0006515339.tif 000004
【００２９】
（ｃ）´式において、ｍｉｎ｛ｕ，ｖ｝は、ｕ、ｖのうち小さい方の値であることを示す。
以上のようにオリジナルの頂点彩色問題は、単純無向グラフＧの各頂点を或る色で彩色し、且つ、相互に隣接する（辺（枝）で結ばれた）どの２つの頂点も異なる色で彩色される彩色数が最小となるように全ての頂点をグルーピングする問題である。一方、山分け問題では、総山数を最小にすることと、山繰り数を最小にすることとのトレードオフが取られた解を求める必要がある。総山数については、後に説明するように、彩色数により自然な形で定式化することができる。一方、山繰り数については、オリジナルな頂点彩色問題はもとよりそれを変形した様々な問題に対しても、山繰り数を評価するような定式化はなされていない。このような課題に対し、本発明者らは、以下に示す本発明の実施形態のようにして、頂点彩色問題を山分け問題に適用できることを見出した。
【００３０】
以下、図面を参照しながら、本発明の実施形態を説明する。
（第１の実施形態）
まず、第１の実施形態を説明する。
＜鋼材の山分け計画立案装置２００の構成および処理＞
図２は、鋼材の山分け計画立案装置２００の機能的な構成の一例を示す図である。図３は、鋼材の山分け計画立案装置２００の動作の一例を説明するフローチャートである。鋼材の山分け計画立案装置２００のハードウェアは、例えば、ＣＰＵ、ＲＯＭ、ＲＡＭ、ＨＤＤ、および各種のインターフェースを備えた情報処理装置、ＰＬＣ（Programmable Logic Controller）、またはＡＳＩＣ（Application Specific Integrated Circuit）等の専用のハードウェアを用いることにより実現することができる。尚、以下の説明では、鋼材の山分け計画立案装置２００を必要に応じて山分け計画立案装置２００と略称する。
【００３１】
［入力部２０１：対象スラブグループリスト入力工程Ｓ３０１］
入力部２０１は、山分け計画の立案対象であるスラブ（鋼材）のリストである山分け対象スラブグループリストを取得する。尚、山分け対象スラブグループリストは、一定周期に取得されてもよいし、特定の事象の生起等をトリガーとして不定期に取得されてもよい。
入力部２０１は、例えば、ＣＰＵが、不図示の鋼材管理系計算機から通信インターフェースを介して受信した山分け対象スラブグループリストのデータをＨＤＤやＲＡＭに記憶することにより実現される。鋼材管理系計算機は、スラブに到着する鋼材全般に関するデータベースを有する上位のコンピュータである。
【００３２】
本実施形態では、クレーン等の搬送機器にて搬送される際に分割されることのない最小の単位となる複数のスラブの単位で、当該複数のスラブがヤードに同時刻に到着する場合を例に挙げて説明する。ただし、このように複数のスラブがヤードに同時刻に到着しないものとしてもよい。その場合、かかる複数のスラブのうち最後にヤードに到着するスラブがヤードに到着した後に、当該複数のスラブの山積みが開始される。以下の説明では、かかる複数のスラブを必要に応じて「スラブグループ」と称する。
【００３３】
本実施形態では、山分け対象スラブグループリストには、それぞれのスラブグループについて、識別番号と、到着予定時刻と、払出順と、鋼材数と、最大幅と、最小幅と、最大長と、最小長の情報が含まれる。
識別番号は、各スラブグループを一意に識別する番号である。
到着予定時刻は、各スラブグループのヤードへの到着予定時刻である。本実施形態では、ヤードに未だ１つもスラブが置かれていない場合の山分け計画を作成する。したがって、山分け計画の立案対象の全てのスラブグループについて到着予定時刻が与えられる。
【００３４】
払出順は、各スラブグループの圧延工程への搬送順である。
鋼材数は、各スラブグループを構成するスラブの数である。
最大幅・最小幅は、それぞれ、各スラブグループを構成するスラブの最大幅・最小幅である。
最大長・最小長は、それぞれ、各スラブグループを構成するスラブの最大長・最小長である。
【００３５】
尚、ここでは、スラブグループ毎のリストを取得する場合を例に挙げて説明したが、スラブ毎のリストを取得してもよい。このようにする場合、各スラブについて、当該スラブが属するスラブグループの識別番号がリストに含まれるようにする。また、最大幅、最小幅、最大幅、最小幅の代わりに、各スラブについて、当該スラブの幅および長さがリストに含まれるようにする。
【００３６】
［変数設定部２０２：変数設定工程Ｓ３０２、目的関数設定部２０３：目的関数設定工程Ｓ３０３、制約式設定部２０４：制約式設定工程Ｓ３０４］
変数設定部２０２は、後述する目的関数および制約式に含まれる変数のうち、固定値ではない変数を設定する。目的関数設定部２０３は、変数設定部２０２により設定された変数に基づいて、目的変数を設定する。また、制約式設定部２０４は、変数設定部２０２により設定された変数に基づいて、制約式を設定する。以下に、本実施形態で定式化される目的関数と制約式について説明する。
【００３７】
[[決定変数（代表関係変数）ｘij]]
それぞれの払出山に属する複数のスラブグループから、１つの代表スラブグループを選択し、代表スラブグループは、当該代表スラブグループが属する払出山に含まれる全てのスラブグループを（代表スラブグループ自身も含み）代表するものとする。
【００３８】
本実施形態では、任意の２つのスラブグループの組｛ｉ，ｊ｝∈Ｎ2に対する０−１変数であって、以下の（１）式で表される０−１変数ｘijを決定変数とする。ここで、Ｎは、スラブグループの集合（Ｎ＝｛１，２，・・・，ｎ｝）である。（１）式に示すように、決定変数ｘijは、スラブグループｉがスラブグループｊを代表する場合に「１」を示し、そうでない場合に「０（ゼロ）」を示す変数である。尚、決定変数ｘij以外の変数は、決定変数ｘijが決まると定まる従属変数である。また、前述したように、代表スラブグループは、自身も代表する。したがって、決定変数ｘijのｉ，ｊは、同じ値をとり得る。
【００３９】
【数４】
0006515339.tif 000005
【００４０】
[[積姿制約]]
積姿制約は、払出山の積姿に関する制約である。本実施形態では、積姿制約には、同一山禁止制約が含まれる。
＜同一山禁止制約＞
同一山禁止制約は、同一の払出山に山積みしていけないスラブグループを規定するものである。本実施形態では、以下の幅条件および長さ条件を満たさないスラブグループは同一の払出山に山積みしてはいけないものとする。
【００４１】
・幅条件
或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも狭いならば無条件で、当該或るスラブグループを、当該下に位置するスラブグループの上に置ける。或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも広い場合には、両者の幅の差が、作業制約により定まる基準値（例えば３００［ｍｍ］）未満であれば、当該或るスラブグループを、当該下に位置するスラブグループの上に置けるが、それを越えると置けない。
【００４２】
すなわち、幅条件を満たす場合は、或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも狭い場合と、或るスラブグループの最大幅が、当該或るスラブグループの下に位置するスラブグループの最小幅よりも広く、且つ、両者の幅の差が基準値（例えば３００［ｍｍ］）未満である場合である。
【００４３】
・長さ条件
或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも短いならば無条件で、当該或るスラブグループを、当該下に位置するスラブグループの上に置ける。或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも長い場合には、両者の長さの差が、作業制約により定まる基準値（例えば３０００［ｍｍ］）未満であれば、当該或るスラブグループを、当該直下に位置するスラブグループの上に置けるが、それを越えると置けない。
【００４４】
すなわち、長さ条件を満たす場合は、或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも短い場合と、或るスラブグループの最大長が、当該或るスラブグループの下に位置するスラブグループの最小長よりも長く、且つ、両者の長さの差が基準値（例えば３０００［ｍｍ］）未満である場合である。
【００４５】
ここで、同一の払出山に山積みすることができない２つのスラブグループの組を禁止対と称し、この禁止対の集合を必要に応じて禁止対集合Ｆと称する。また、以下の説明では、２つのスラブグループの組を必要に応じてスラブグループ対と称する。禁止対集合Ｆは、以下の（３）式で表される。
【００４６】
【数５】
0006515339.tif 000006
【００４７】
（３）式において、ｉ．ｊは幅条件および長さ条件の少なくとも何れか一方を満たさないスラブグループである。本実施形態では、（３）式に示すように、幅条件と長さ条件の少なくとも何れか一方の条件を満たさない（すなわち、同一の払出山に山積みしてはいけない）スラブグループ対（枝）の集合を禁止対集合Ｆとして導入する。
【００４８】
[[逆転対同一山積変数ｒij]]
任意の２つのスラブグループ｛ｉ，ｊ｝⊆Ｎついて、同一の払出山に山積みすることはできるが、同一の払出山に山積みする際には、ヤードへの到着順と同一の払出山における積順とを入れ替える必要があるスラブグループ対を逆転対と定義する。以下の説明では、この逆転対の集合を必要に応じて、逆転対集合Ｒと称する。ヤードへの到着順と同一の払出山における積順とが逆転しているとは、同一の払出山において積順が上になるスラブグループの方が、積順が下になるスラブグループよりも、ヤードへの到着順が早いことをいう。逆転対集合Ｒは、以下の（４）式で表される。
【００４９】
【数６】
0006515339.tif 000007
【００５０】
（４）式は、スラブグループｉ、ｊを同じ払出山に山積みする際に当該スラブグループｉ、ｊを入れ替える必要があることを示す。本実施形態では、この逆転対集合Ｒに属する全てのスラブグループ対｛ｉ，ｊ｝∈Ｒに対し、以下の（５）式に示す０−１変数を逆転対同一山積変数ｒijとして導入する。本実施形態では、（４）式に示すように、逆転対同一山積変数ｒijは、逆転対であるスラブグループｉ、ｊを同じ払出山に山積みする場合に「１」を示し、そうでない場合に「０（ゼロ）」を示す０−１変数である。
【００５１】
【数７】
0006515339.tif 000008
【００５２】
[[山仕分け制約]]
山仕分け制約式は、複数のスラブグループそれぞれをいずれかの払出山に仕分る際に生じる制約式である。山仕分け制約は、他のスラブグループを代表するスラブグループは、１つの払出山に１つのみ存在し、且つ、他のスラブグループを代表するスラブグループはそれが仕分けられた払出山以外の払出山に仕分けられた他のスラブグループを代表することはできないことを示すものである。本実施形態では、山仕分け制約式には、第１〜第６の制約式が含まれる。以下の説明では、他のスラブグループを代表するスラブグループを必要に応じて代表スラブグループと称する。
【００５３】
＜第１の制約式＞
スラブグループｉがその他のスラブグループｊを代表するとき、スラブグループｉ自身は代表スラブグループでなければならない。このことから、以下の（７）式に示す第１の制約式が与えられる。第１の制約式は、代表スラブグループが、当該代表スラブグループ自身と、当該代表スラブグループと同一の払出山に積まれるその他のスラブグループを代表することを規定する制約式である。
ｘij≦ｘii  （∀ｉ，ｊ∈Ｎ，ｉ≠ｊ）・・・（７）
【００５４】
＜第２の制約式＞
禁止対集合Ｆに含まれるスラブグループ対｛ｉ，ｊ｝∈Ｆは、同一の払出山に積めないため、一方が他方を代表する関係にない。このことから、以下の（８）式に示す第２の制約式が与えられる。第２の制約式は、前記積姿制約に違反するために同一の払出山に積むことができない任意の２つのスラブグループは、一方が他方を代表しないことを規定する制約式である。
ｘij＝ｘji＝０  （∀｛ｉ，ｊ｝∈Ｆ）・・・（８）
【００５５】
＜第３の制約式＞
禁止対集合Ｆに含まれるスラブグループ対｛ｊ，ｋ｝∈Ｆは、同一の払出山に積めないため、当該スラブグループ対を構成するスラブグループｊ，ｋをそれとは異なる同一のスラブグループiが代表することはない。このことから、以下の（９）式に示す第３の制約式が与えられる。第３の制約式は、前記積姿制約に違反するために同一の払出山に積むことができない任意の２つのスラブグループをそれとは異なる同一のスラブグループが代表することはないことを規定する制約式である。
ｘij＋ｘik≦ｘii  （∀ｉ∈Ｎ，∀｛ｊ，ｋ｝∈Ｆ）・・・（９）
【００５６】
＜第４の制約式＞
全てのスラブグループは、自身またはその他のスラブグループのうちの１つに必ず代表されなければならない。このことから、以下の（１０）式に示す第４の制約式が与えられる。第４の制約式は、全てのスラブグループが、何れか１つのスラブグループによって代表されることを規定する制約式である。
Σi∈Nｘij＝１  （∀ｊ∈Ｎ）・・・（１０）
【００５７】
＜第５の制約式＞
１つの払出山の高さが基準値以下でなければならない。
本実施形態では、全てのスラブの厚みが同じであるものとする。したがって、１つの払出山に積めるスラブの枚数が基準枚数（例えば１２［枚］）以下であるという条件を山高さ制約とする。ここで、１つの払出山に積めるスラブの数の上界をｈ（ｈ∈Ｚ+（自然数））と表記する。
【００５８】
そうすると、全てのスラブグループｉ∈Ｎに対し、以下の（６）式の山高さ制約式（第５の制約式）を満足しなければならない。
【００５９】
【数８】
0006515339.tif 000009
【００６０】
（６）式の左辺は、スラブグループｉを含む払出山のスラブグループの総数である。より具体的に説明すると、（６）式の左辺の第１項（w(i)）は、スラブグループｉ（∀ｉ∈Ｎ）のスラブ数（w(i)：Ｎ→Ｚ+（自然数））である。w(i)は、例えば、１以上６以下の自然数である（１≦w(i)≦６）。
【００６１】
また、（６）式の左辺の第２項（Σの項）は、スラブグループｉ（∈Ｎ）によって代表されるその他のスラブグループｊの総数を表す。
尚、（６）式において、（６）式の左辺の第２項のΣは、スラブグループ集合Ｎの中のスラブグループｉ以外のスラブグループｊに対する総和を表す（このことは以降の式においても同じである）。
【００６２】
＜第６の制約式＞
逆転対集合Ｒに属するスラブグループ対であって、一方が他方を代表する関係にあるスラブグループ対｛ｉ，ｊ｝∈Ｒについては同一の払出山に積まれなければならず、この場合、スラブグループ対ｉ，ｊについて山繰りが生じる。また、逆転対集合Ｒに属するスラブグループ対であって、一方が他方を代表する関係にない（いずれもそれ以外の同一のスラブグループｉに代表される）スラブグループ対｛ｊ，ｋ｝∈Ｒについては同一の払出山に積まれた場合、スラブグループ対ｊ、ｋについては山繰りが生ずる。このことから、以下の（１１）式、（１２）式に示す第６の制約式が与えられる。第６の制約式は、一方がもう一方を代表する関係にある任意のスラブグループ対について、ヤードへの到着順が早いスラブグループを上に積む場合に逆転の関係（＝山繰り）が生じることを規定する制約式である。
ｒij≧ｘij，ｒji≧ｘji（∀｛ｉ，ｊ｝∈Ｒ）・・・（１１）
ｒjk≧ｘij＋ｘik−１  （∀ｉ∈Ｎ，∀｛ｊ，ｋ｝∈Ｒ）・・・（１２）
【００６３】
[[評価指標]]
次に、目的関数における評価指標を説明する。
本実施形態では、総山数（山高さ）と山繰り数、すなわち同一の払出山に積まれた逆転対集合Ｒに属するスラブグループ対の総数との重み付き線形和を目的関数とする。尚、重み付き線形和とは、総山数（山高さ）に対する重み係数、山繰り数に対する重み係数を、総山数（山高さ）、山繰り数にそれぞれ乗算した値を加算したものをいう。総山数（山高さ）に対する重み係数とは、総山数（山高さ）に対する評価の、山繰り数に対する評価とのバランスを表す係数である。山繰り数に対する重み係数とは、山繰り数に対する評価の、総山数（山高さ）に対する評価とのバランスを表す係数である。
【００６４】
総山数（山高さ）を評価指標とするのは、ヤードにおける山分けでは、保温設備の収容能力が限定されていることや、スラブの置場が限られていることや、置場にスラブを直接置く場合には最上段および最下段のスラブの放冷が他のスラブに比べて大きくなること等の理由で、山高さを出来るだけ高くして総山数を出来るだけ少なくすることが要請されるからである。
【００６５】
山繰り数を評価指標とするのは、以下の理由による。まず、山分けを行う上で、作業スペースの問題や作業を行うクレーン等の搬送機器の能力の兼ね合いから、山積みを行うための搬送作業数ができるだけ少ないことが求められる。山分けの場合には、ヤードに到着する順にスラブを積んでいくことが出来れば理想的である。一方で、払出時の山繰りを無くし、払出作業を迅速に行う為に、払出山に於いては、下工程への払出が早いものを上に積むのが基本である。従って、現実的には、ヤードへの到着順と払出山における積順とが食い違う場合がある。すなわち、ヤードへの到着順が早い方のスラブを遅い方のスラブよりも同一の払出山の上の段に積まなければならない場合がある。その場合には、相対的に下段に積まれるスラブがヤードに到着するまで、先にヤードに到着したスラブを一旦仮置き場に仮置きし、相対的に下段に積まれるスラブがヤードに到着し山積みされてから、そのスラブの上に、仮置き場のスラブを積む作業が必要となる。したがって、この様な作業ができるだけ少なくなるような山分けをすることが望まれる。このような仮置きの発生数は、数学的には逆転数または転倒数として表現される。逆転数（転倒数）とは、ヤードへの到着順と同一の払出山における積順とが逆転する関係が成立するスラブグループ対の総数である。このように山繰り数は、逆転数で表される。
【００６６】
[[目的関数]]
１つの払出山において代表スラブグループは１つであるから、代表グループの総数（＝Σi∈Nｘii）が総山数になる。
また、逆転数（＝山繰り数）は、同一の払出山に積まれる逆転対の総数であるから、同一の払出山に積まれる逆転対の総数（＝Σ[i,j]∈Rｒij）で表される。
総山数（山高さ）に対する重み係数をｋ1とし、逆転数に対する重み係数をｋ2とすると、目的関数は「ｋ1×総山数＋ｋ2×逆転数」となる。
したがって、目的関数は、以下の（１３）式で表される。
ｋ1×Σi∈Nｘii＋ｋ2×Σ[i,j]∈Rｒij  ・・・（１３）
【００６７】
[[目的関数と制約式]]
以上より、本実施形態では、以下のように、（６）式〜（１２）式、（１４）式、（１５）式の制約式による制約を満足する範囲で、（１３）式の目的関数の値を最小化する決定変数ｘijを導出することになる。
【００６８】
【数９】
0006515339.tif 000010
【００６９】
変数設定部２０２は、例えば、山分け対象スラブグループリストと、幅条件および長さ条件における基準値とに基づいて、同一の山に山積みしてはいけないスラブグループ対（枝）の集合Ｆ（禁止対集合Ｆ）を導出する。幅条件および長さ条件における基準値は、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。また、変数設定部２０２は、入力部２０１により入力された対象スラブグループリストに基づいて、決定変数ｘij、逆転対同一山積変数ｒijのｉ、ｊとしてとり得る値を設定すると共に、同一山スラブ枚数ｗ（ｉ）の値を設定する。尚、決定変数ｘijについては、ｉとｊが同じ値のものと異なる値のものとを設定する。
【００７０】
目的関数設定部２０３は、変数設定部２０２で設定された決定変数ｘijおよび逆転対同一山積変数ｒijを（１３）式に設定する。また、目的関数設定部２０３は、総山数（山高さ）に対する重み係数ｋ1と、逆転数に対する重み係数ｋ2を設定する。これらの重み係数ｋ1、ｋ2は、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。
【００７１】
制約式設定部２０４は、変数設定部２０２で設定された決定変数ｘijおよび逆転対同一山積変数ｒijを（６）式〜（１２）式、（１４）式、（１５）式に設定する。また、制約式設定部２０４は、１つの払出山に積めるスラブの枚数の上界ｈを（６）式に設定する。１つの払出山に積めるスラブの枚数の上界ｈは、例えば、入力部２０１が鋼材管理系計算機から取得してもよいし、山分け計画立案装置２００のユーザインターフェースに対するオペレータによる操作により取得してもよい。
【００７２】
［山分け問題と頂点彩色問題との関係］
ここで、山分け問題と頂点彩色問題との関係について説明する。
スラブグループの集合Ｎを頂点の集合とし、禁止対集合Ｆ（同一の払出山に山積みしてはいけないスラブグループ対の集合）を辺（枝）とする単純無向グラフＧとする。山分け問題において、同一の払出山に積むことができないスラブグループ対は、単純無向グラフＧにおいて隣接する（辺（枝）で結ばれた）頂点対と見なすことができる。また、ヤードにおいてスラブを複数の払出山に積み分けることは、単純無向グラフＧの頂点をいくつかの色に塗り分けることに対応する。すなわち、同一の色の頂点に対応するスラブグループが同一の払出山に山積みされることになり、異なる色の頂点に対応するスラブグループは異なる払出山に山積みされることになる。このようにすることにより、山高さ制約を除外し、目的関数として総山数のみを考慮した場合、山分け問題は、頂点彩色問題と等価な問題となる。この様に、山分け問題は、頂点彩色問題と似た性質を持つため、頂点彩色問題の定式化を応用することが可能である。
【００７３】
一方、一般的な頂点彩色問題では山繰り数を評価するような定式化はなされていない。そこで、本実施形態では、積順が上になるスラブグループの方が、積順が下になるスラブグループよりも、ヤードへの到着順が先になる逆転の関係が生じるスラブグループ対（逆転対）の集合を逆転対集合Ｒとして定義する。そして、逆転対集合Ｒの要素であるスラブグループ対が代表関係にあるかあるいは同一の代表スラブグループによって当該スラブグループ対が代表されるか否かを判定する制約式を設けると共に、逆転対集合Ｒの要素であるスラブグループ対が代表関係にあるかあるいは同一の代表スラブグループによって当該スラブグループ対が代表される場合には、そのスラブグループ対の数を計数する項を目的関数に含める。このようにすることによって、頂点彩色問題を山分け問題に適用することができる。
【００７４】
［最適解導出部２０５：最適解導出工程Ｓ３０５］
最適解導出部２０５は、（６）式〜（１２）式、（１４）式、（１５）式の制約式による制約を満足する範囲で、（１３）式の目的関数の値を最小化する決定変数ｘij（すなわち、決定変数ｘijの最適解）を導出する。
【００７５】
本実施形態では、以下の仮定の下で、最適化計算を行う。
（ａ）払出山のスラブを次工程に払い出す際に、払出山の上にあるスラブグループから順に払い出せるように、積順が相対的に上であるスラブグループの次工程への払出順が、積順が相対的に下であるスラブグループの次工程への払出順よりも早くなるように各スラブを山積みする。
【００７６】
（ｂ）次工程へのスラブグループの払出順に自由度がある場合には、ヤードへの到着順が早いスラブグループである程、払出山の下に積む。例えば、同じロット番号のスラブグループについては、次工程へのスラブグループの払出順に制限はない。ロットとは、次工程（例えば、熱延工程）での処理の纏まりを表すもので、ロット番号は、その纏まりの次工程での処理の順番を表す、
（ｃ）ヤードへの到着順は一意に定まり、異なるスラブグループ間での重複はないものとする。
このような仮定により、スラブグループの任意の部分集合Ｎ´⊆Ｎに対し、積み上げる順序が唯一つに定まる。
尚、0-1整数計画法による最適化計算は、公知の技術を用いることにより実現されるので、ここでは、その詳細な説明を省略する。
【００７７】
［出力部２０６：出力工程Ｓ３０６］
出力部２０６は、最適解導出部２０５で導出された決定変数ｘijの最適解に基づく情報を出力する。例えば、出力部２０６は、最適解導出部２０５で導出された決定変数ｘijの最適解を出力することができる。この場合、オペレータは、決定変数ｘijの最適解から、山分け対象スラブグループリストに含まれるスラブグループのそれぞれについての、当該スラブグループが属する払出山と当該払出山における積順とを含む情報を作成することができる。また、出力部２０６は、最適解導出部２０５で導出された決定変数ｘijの最適解から、このような情報を導出して出力することができる。その他、出力部２０６は、山分け対象スラブグループリストと決定変数ｘijの最適解とに基づいて、どのタイミングでどの搬送機器によりどのスラブグループをどの場所に搬送するのかを特定し、特定した内容に基づいて、搬送機器に対する動作指令を行うことができる。このようにする場合には、決定変数ｘijの最適解を出力してもしなくてもよい。
【００７８】
［まとめ］
以上のように本実施形態では、総山数を少なくすることと、山繰り数（同一の払出山においてヤードへの到着順が早い方のスラブグループを遅い方のスラブグループよりも上に積むために必要になる仮置きの数）を少なくすることとを目的とする目的関数の値を最小化する最適化問題を数理計画法による最適化計算を行うことにより解く。その際に、頂点をスラブグループに対応させ、辺（枝）により相互に連結される２つの頂点に対応する２つのスラブグループを、同一の払出山に積んではいけない関係（禁止対の関係）になる２つのスラブグループとして表す。また、他のスラブグループを代表するスラブグループであって、１つの払出山に１つのみ存在し、且つ、それ以外の払出山において他のスラブグループを代表することはできないスラブグループである代表スラブグループの数を総山数として表現する。また、同一の払出山に山積みすることはできるが、同一の払出山に山積みする際には、ヤードへの到着順と同一の払出山における積順とを入れ替える必要があるスラブグループ対である逆転対の内、同一の払出山に積まれた逆転対の総数を逆転数とし、これを山繰り数として表現する。
【００７９】
具体的に本実施形態では、逆転対の集合を逆転対集合Ｒとして定義する。そして、一方が他方を代表する関係にある任意のスラブグループ対が、逆転対となる場合及び同一の代表スラブグループによって当該スラブグループ対が代表される場合に山繰りが生じることを規定する制約式を制約式に含める。
【００８０】
したがって、山分け問題を頂点彩色問題に適用することができる。このようにすることによって、山分け計画の立案対象のスラブグループの中に、同一の払出山に積むと山繰り負荷が大きくなるようなスラブグループが多い場合や、山分け計画の立案対象のスラブグループの数が多い場合でも、実用的な時間内でヤードにおける山分け計画を作成することが可能になる。すなわち、解くべき問題の性格に関わらず、実用的な時間内でヤードにおける山分け計画を作成することができる。
【００８１】
例えば、本実施形態では、集合分割問題の様に実行可能山を列挙し、その数だけ変数を用意する必要はなくなる。特許文献１に示す集合分割問題における部分集合の数は、集合の要素数をｎとすると２nとなるので指数時間アルゴリズムになる。これに対し、本実施形態ではｎ2の多項式のオーダの変数により問題を定式化することができる。よって、実行可能山（部分集合）の数に左右されないアルゴリズム構築が可能である。また、本実施形態の手法では、頂点が代表頂点（スラブグループｉが代表スラブグループ）である場合に変数ｘii＝１と約束することにより、彩色数χ（Ｇ）をχ（Ｇ）＝Σi∈Vｘiiと簡潔に表すことができる。したがって、特許文献２の手法と比較しても、特許文献２で必要となった、山が存在するか否かを示す変数（頂点彩色問題においては色の存在を表す変数）が不要となること等、変数の数や探索範囲を大幅に削減できることから、逆転対が多い場合にも高速に求解可能となる。
【００８２】
＜変形例＞
［変形例１］
本実施形態では、総山数（山高さ）と山繰り数（逆転数）との重み付き線形和を最小化することを目的とする目的関数を例に挙げて説明した。しかしながら、目的関数は、総山数（山高さ）と山繰り数（逆転数）との重み付き線形和に限定されない。例えば、１つの払出山が出来上がるまでの時間（１つの山を作るための搬送機器の作業時間）の、全ての払出山についての総和と、総山数（山高さ）と、山繰り数（逆転数）との重み付き線形和を目的関数としてもよい。また、１つの払出山において、最初に次工程に払い出すスラブから最後に払い出すスラブを払い出すまでに要する時間（１つの払出山における最初のスラブの払い出し時刻から最後のスラブの払い出し時刻までの時間）の、全ての払出山についての総和と、総山数（山高さ）と、山繰り数（逆転数）との重み付き線形和を目的関数としてもよい。前者について、１つの払出山が出来上がるまでの時間が短ければ、例えば、保温設備をスラブの受け入れのために開けておく時間を短くすることができ、スラブの温度の低下を抑制することができる。後者について、１つの払出山において、最初に次工程に払い出すスラブから最後に払い出すスラブを払い出すまでに要する時間が短ければ、保温設備からの払い出しのために保温設備が開いている時間を短くすることができ、スラブの温度の低下を抑制することができる。
【００８３】
［変形例２］
本実施形態では、目的関数の値を最小化する最適化問題を数理計画法により解く場合を例に挙げて説明した。しかしながら、例えば（２３）式の各項に（−１）を掛けることにより、目的関数の値を最大化する最適化問題としてもよい。
【００８４】
［変形例３］
本実施形態では、全てのスラブの厚みが同じである場合を例に挙げて説明した。しかしながら、スラブの厚みは同じでなくてもよい。この場合、w(i)を、スラブグループｉに含まれるスラブの厚みの総和とすればよい。
【００８５】
［変形例４］
本実施形態では、スラブグループ単位で山分け計画を作成する場合を例に挙げて説明した。しかしながら、１つのスラブ単位で山分け計画を作成してもよい。その場合には、これまでの説明の「スラブグループ」を「スラブ」と読み替え、その鋼材数は１枚となり（したがって、例えば、スラブグループｉのスラブ数w(i)は「１」になる）、最大幅と最小幅が当該スラブの幅で同じ値となる。最大長、最小長も同様に当該スラブの長さで同じ値となる。
【００８６】
（第２の実施形態）
次に、第２の実施形態を説明する。第１の実施形態では、対称代表点法を解法として用いる頂点彩色問題に山分け計画を適用する場合を例に挙げて説明した。これに対し、本実施形態では、非対称代表点法を解法として用いる頂点彩色問題に山分け計画を適用する場合を例に挙げて説明する。したがって、本実施形態と第１の実施形態は、制約式の一部が主として異なる。よって、本実施形態の説明において、第１の実施形態と同一の部分については、図１〜図３に付した符号と同一の符号を付す等して詳細な説明を省略する。
【００８７】
スラブグループの集合Ｎ（Ｎ＝｛１，２，・・・，ｎ｝）のそれぞれに正の整数の大小関係で順序をつける。前述したように、非対称代表点法では、２つのスラブグループｉ，ｊについて、ｉ＜ｊであれば、スラブグループｊはスラブグループｉを代表することはできない。すなわち、全てのｉ＜ｊとなるスラブグループｉ、ｊについて決定変数ｘjiは０（ｘji＝０）になる。したがって、非対称代表点法を解法として用いる場合の目的関数と制約式は、以下のようになる。
【００８８】
【数１０】
0006515339.tif 000011
【００８９】
（９´）式および（１２´）式において、ｍｉｎ｛ｊ，ｋ｝は、ｊ、ｋのうち小さい方の値であることを示す。また、（１６）式は、前述した（ｇ）式に対応し、第１の実施形態で説明した山仕分け制約式に含まれる第７の制約式である。（８´）式、（９´）式、（７´）式は、それぞれ前述した（ｂ´）式、（ｃ´）式、（ｅ´）式に対応する制約式であり、第１の実施形態で説明した（８）式、（９）式、（７）式で設定した制約式のパラメータｉの範囲を（１６）式の規定を利用して減らした制約式である。また、（６´）式は、第１の実施形態で説明した（６）式に対応するものであり、山高さ制約式（第５の制約式）である。
【００９０】
以上のように本実施形態では、それぞれのスラブグループ（頂点）に対し一意の序列を付与し、序列が相対的に低いスラブグループは、序列が相対的に高いスラブグループを代表することができないようにする。対称代表点法だけでなく、非対称代表点法を解法として用いた場合でも、頂点彩色問題に山分け計画を適用することができる。そして、全てのｉ＜ｊとなるスラブグループｉ、ｊについて決定変数ｘjiは０（ｘji＝０）となるので、計算時間をより短くすることができる。
尚、本実施形態においても、第１の実施形態で説明した種々の変形例を採用することができる。
【００９１】
（第３の実施形態）
次に、第３の実施形態を説明する。第２の実施形態では、スラブグループの集合Ｎ（Ｎ＝｛１，２，・・・，ｎ｝）に対する順序のつけ方が任意である場合を例に挙げて説明した。これに対し、本実施形態では、スラブグループの集合Ｎに対する順序のつけ方に制限をつける。このように本実施形態と第２の実施形態は、スラブグループの集合Ｎに対する順序のつけ方が異なることによる処理が主として異なる。したがって、本実施形態の説明において、第１、第２の実施形態と異なる部分については、図１〜図３に付した符号と同一の符号を付す等して詳細な説明を省略する。
【００９２】
第２の実施形態で説明した制約式のうち（１２´）式に注目すると、各逆転対｛ｊ，ｋ｝∈Ｒに対し（ｍｉｎ｛ｊ，ｋ｝−１）個の制約式を必要とする。これは、逆転対｛ｊ,ｋ｝に対応するスラブグループｊ，ｋに付与された番号が小さければ、（１２´）式の制約式の数を少なくできることを意味する。つまり、非対称代表点法では、スラブグループへの順序（番号）の付け方によって、逆転対に関する制約式を減らすことができる。
【００９３】
そこで、本実施形態では、変数設定部２０２は、以下のようにしてスラブグループに対して順序付け（番号付け）を行う。
図４は、スラブグループに対して順序付け（番号付け）を行う方法の一例を概念的に説明する図である。また、図５は、スラブグループに対して順序付け（番号付け）を行う方法の一例を説明するフローチャートである。図４および図５を参照しながら、スラブグループに対して順序付け（番号付け）を行う方法の一例を説明する。
【００９４】
まず、ステップＳ５０１において、変数設定部２０２は、スラブグループの集合Ｎを頂点の集合Ｖとし、逆転対集合Ｒ（積順が上になるスラブグループの方が、積順が下になるスラブグループよりも、ヤードへの到着順が先になる逆転の関係が生じるスラブグループ対（逆転対）の集合）を辺（枝）とする単純無向グラフΓ（Ｖ，Ｒ）を作成する。尚、他の何れのスラブグループとも逆転対とはならないスラブグループについては、当該スラブグループに対応する頂点が孤立して存在することになる（すなわち、当該頂点は、他の何れの頂点とも辺（枝）で接続されないことになる）。
【００９５】
図４の上から１番目の図が、この単純無向グラフΓの一例である。このとき、変数設定部２０２は、各スラブグループの集合Ｎに対応する頂点に、相互に重複しないように、１〜Ｎまでの番号を仮に付す。図４の上から１番目の図には、この番号を各頂点の傍らに示す。また、変数設定部２０２は、列Ｑを空列とする。列Ｑの各列には、スラブグループの識別番号が与えられ、ｊ列目のスラブグループに番号ｊが付与されるものとする（ｊは正の整数である）。
【００９６】
次に、ステップＳ５０２において、変数設定部２０２は、単純無向グラフΓ（Ｖ，Ｒ）に頂点があるか否かを判定する。この判定の結果、単純無向グラフΓ（Ｖ，Ｒ）に頂点がない場合には、各スラブグループに対して順序付け（番号付け）が終了することになるので、図５のフローチャートによる処理を終了する。
【００９７】
一方、単純無向グラフΓ（Ｖ，Ｒ）に頂点が（１つでも）ある場合には、ステップＳ５０３に進む。図４の上から１番目の図の例では、単純無向グラフΓ（Ｖ，Ｒ）に頂点があるので、ステップＳ５０３に進むことになる。
ステップＳ５０３に進むと、変数設定部２０２は、単純無向グラフΓ（Ｖ，Ｒ）の頂点のうち、最も次数が高い頂点（すなわち、頂点に接続されている辺（枝）の数が最大の頂点）を選択する。尚、最も次数が高い頂点が複数ある場合、変数設定部２０２は、当該複数の頂点のうち、ステップＳ５０１で仮につけた番号が最も小さい頂点を選択する。図４の上から１番目の図の例では、仮の番号「５」が付された頂点に接続されている辺（枝）の数は「４」であり、当該頂点の次数が最も高い。したがって、変数設定部２０２は、番仮の号「５」が付された頂点を選択する。
【００９８】
次に、ステップＳ５０４において、変数設定部２０２は、ステップＳ５０３で選択した頂点と、当該頂点に接続されている辺（枝）を削除する。図４の上から１番目の図の例では、図４の上から２番目の図に示すように、仮の番号「５」が付された頂点と、当該頂点に接続されている辺（枝）を削除する。尚、図５では、削除されたものを破線で示す。
【００９９】
次に、ステップＳ５０５において、変数設定部２０２は、ステップＳ５０３で選択した頂点に対応するスラブグループに対する番号を変更する。列Ｑの最後尾に、ステップＳ５０３で選択した頂点に対応するスラブグループの識別番号を挿入することにより、ステップＳ５０３で選択した頂点に対応するスラブグループに対する番号を変更する。図４の上から２番目の図に示す例では、まだ列Ｑに、スラブグループの識別番号が挿入されていない。したがって、列Ｑの先頭に、仮の番号「５」が付された頂点に対応するスラブグループの識別番号が挿入される。このようにして、仮の番号「５」が付された頂点に対応するスラブグループの番号が「５」から「１」に変更される。
【０１００】
そして、前述したステップＳ５０２に戻る。そして、ステップＳ５０２において、変数設定部２０２は、単純無向グラフΓ（Ｖ，Ｒ）に頂点があるか否かを判定する。図４の上から２番目の図に示す例では、まだ、ステップＳ５０１で付けられた仮の番号が「１」、「２」、「３」、「４」の４つの頂点がある。したがって、ステップＳ５０３において、変数設定部２０２は、当該頂点のうち、次数が最も高い頂点である、仮の番号「２」が付された頂点を選択する。
【０１０１】
そして、変数設定部２０２は、ステップＳ５０４において、図４の上から３番目の図に示すように、仮の番号「２」が付された頂点と、当該頂点に接続されている辺（枝）を削除し、ステップＳ５０５において、列Ｑの最後尾（２列目）に、仮の番号「２」が付された頂点に対応するスラブグループの識別番号を挿入する。これにより、図４の上から３番目の図に示すように、仮の番号「２」が付された頂点に対応するスラブグループの番号は「２」になる。
【０１０２】
図４の上から３番目の図に示す例では、まだ、ステップＳ５０１で付けられた仮の番号が「１」、「３」、「４」の３つの頂点がある。したがって、変数設定部２０２は、ステップＳ５０２において、単純無向グラフΓ（Ｖ，Ｒ）に頂点があると判定する。図４の上から３番目の図に示す例では、現在残っている頂点の中に、辺（枝）で接続されている頂点がない（全ての頂点の次数は同じである）。したがって、ステップＳ５０３において、変数設定部２０２は、仮の番号が「１」、「３」、「４」の３つの頂点のうち、最も小さい仮の番号「１」の頂点を選択する。
【０１０３】
そして、変数設定部２０２は、ステップＳ５０４において、図４の上から４番目の図に示すように、仮の番号「１」が付された頂点を削除し、ステップＳ５０５において、列Ｑの最後尾（３列目）に、仮の番号「１」が付された頂点に対応するスラブグループの識別番号を挿入する。これにより、図４の上から４番目の図に示すように、仮の番号「１」が付された頂点に対応するスラブグループの番号は「３」になる。
以降、仮の番号「１」が付与された頂点に対する処理と同様にして、図４の上から４番目の図に示すように、仮の番号「３」、「４」が付された頂点に対応するスラブグループの番号として、それぞれ「４」、「５」が設定される。以上のようにして全ての頂点がなくなると、前述したように図５のフローチャートによる処理を終了する。
【０１０４】
以上のように本実施形態では、スラブグループの集合Ｎを頂点の集合Ｖとし、逆転対集合Ｒを辺（枝）とする単純無向グラフΓ（Ｖ，Ｒ）において、他の頂点と接続される辺（枝）の数が多い頂点から順に、当該頂点と当該頂点に接続される辺（枝）を削除すると共に当該頂点に対応するスラブグループの番号に対し１から昇順に１ずつ増加する番号を付す。したがって、より多くの他のスラブグループと逆転対の関係になるスラブグループであるほど、相対的に小さな番号が付与されることになる。したがって、逆転対に関する制約式である（１２´）式として列挙する式の数を少なくすることができる。よって、計算時間をより一層短くすることができる。
尚、本実施形態においても、第１、第２の実施形態で説明した種々の変形例を採用することができる。
【０１０５】
（実施例）
次に、実施例を説明する。
＜実施例１＞
本実施例では、第３の実施形態による解法（発明例）と、特許文献１による解法（比較例１）と、特許文献２による解法（比較例２）とのそれぞれにより、山分け計画を作成し、求解に要する時間の比較を行った。ただし、計算時間が３分（１８０秒）以上となる場合には、その時点で得られた解の精度を表す双対ギャップにより評価した。
双対ギャップは、以下の（１７）式で表される。
双対ギャップ＝｛（上界値−下界値）／上界値｝×１００  ・・・（１７）
【０１０６】
（１７）式において、上界値は、計算を開始してから３分が経過した時点で得られた、山分け計画を実現可能な解の中で最も良い解の目的関数の値である。下界値は、計算を開始してから３分が経過した時点で得られた、緩和問題を解いた場合の最適解の中で、最も大きな（最も悪い）目的関数の値である。尚、上界値と下界値とが一致した場合、そのときの解は最適解である。また、緩和問題とは、最適化問題の０−１変数の条件を緩和した（０−１変数が０、１以外の０〜１の間の値をとることを許容した）問題をいう。
【０１０７】
また、何れの解法でも、スラブグループの総数を５０とし、同一のスラブグループについて、山分け計画を作成した（すなわち、同一の山分け対象スラブグループリストを用いた）。
また、何れの解法でも、ｋ1×総山数＋ｋ2×逆転数を目的関数とした。ここで、総山数（山高さ）に対する重み係数ｋ1を５．０（ｋ1＝５．０）とし、逆転数に対する重み係数ｋ2を１．０（ｋ2＝１．０）とした。
図６は、これらの解法による山分け計画の作成結果を表形式に示す図である。
【０１０８】
図６において、「禁止％」とは、スラブグループ対の総数に対する、同一の払出山に山積みしてはいけないスラブグループ対（枝）の数の割合を、百分率で表記したものである。「逆転％」とは、スラブグループ対の総数から同一の払出山に山積みしてはいけないスラブグループ対の数を差し引いた値に対する、ヤードへの到着順と払出山における積順とが逆転するスラブグループ対の数の割合を、百分率で表記したものである。「Ｆ．Ｍｔ」は、実現可能山の数（単位は百万個）である。「Ｏｐｔ．Ｖ」は、最適解が得られたときの目的関数の値、または、上界値である。「山数」は、最適化計算の結果として得られた払出山の数である。「逆転」は、最適化計算の結果として得られた、ヤードへの到着順と払出山における積順とが逆転するスラブグループ対の数である。
【０１０９】
図６において色塗りをいているのは、３つの解法のうちで最良の解が得られたものである。図６に示すように、使用した１９個のデータのうち、１４個のデータにおいて、発明例による解法（非対称代表点法）の方が、比較例１による解法（集合分割）および比較例２による解法（多対１割当）よりも早く良い解に達する。比較例１による解法（集合分割）による解が最も良かったのは３個のデータ（データＩＤ０３、０５、１５）のみである。そのうち、２個のデータ（データＩＤ０３、０５）において、発明例による解法（非対称代表点法）と比較例１による解法（集合分割）とで同レベルの解が得られており、のこる１個のデータ（データＩＤ１５）に於いても、ほぼ同レベルの解が得られている。また、比較例２による解法（多対１割当）では、最も良い解が得られたケースはない。
【０１１０】
比較例１による解法（集合分割）による解の方が、発明例による解法（非対称代表点法）よりも良い場合は、実現可能山の数が高々３百万程度までであり、実現可能山の数が１千万個に近づくと、比較例１による解法（集合分割）では３分以内に実現可能解が得られない。これに対し、発明例による解法（非対称代表点法）では、実現可能山の数が数千万から１億個となっても３分以内で最適値あるいはそれに近い値を求解できる。このように、発明例による解法（非対称代表点法）では、実現可能山の数が多くなっても３分以内にほぼ最適解を求めることができる。
【０１１１】
＜実施例２＞
本実施例では、第３の実施形態による解法（非対称代表点法（発明例）と記載）と、第１の実施形態による解法（対称代表点法（発明例）と記載）とのそれぞれにより、山分け計画を作成し、求解に要する時間の比較を行った。山分け計画に用いたデータ、山分け計画の作成条件、および山分け計画の評価方法は、実施例１と同じである。
図７は、これらの解法による山分け計画の作成結果を表形式に示す図である。図７において、「（１２´）式」、「（１２）式」は、それぞれ、（１２´）式、（１２）式として列挙される式の数である。また、「％」は、（１２´）式として列挙される式の数を（１２）式として列挙される式の数で割った値を百分率で表わしたものである。
図７に示すように、使用した１９個のデータのうち、１４個のデータの全てにおいて、
第３の実施形態による解法（非対称代表点法）の方が、第１の実施形態による解法（対称代表点法）よりも、早く良解に達する。ただし、第１の実施形態による解法（対称代表点法）でも、実現可能解が得られなかったケースはなく、図６に示した比較例１による解法（集合分割）および比較例２による解法（多対１割当）に比べ、実現可能山の数が多くなっても早く良い解を得ることができる。
【０１１２】
（その他の変形例）
尚、以上説明した本発明の実施形態は、コンピュータがプログラムを実行することによって実現することができる。また、前記プログラムを記録したコンピュータ読み取り可能な記録媒体及び前記プログラム等のコンピュータプログラムプロダクトも本発明の実施形態として適用することができる。記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
また、以上説明した本発明の実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【０１１３】
（請求項との関係）
以下に請求項と実施形態との関係の一例を示す。尚、請求項と実施形態との関係が以下の関係に限定されないのは、変形例等で説明した通りである。
＜請求項１＞
決定変数設定手段は、例えば、変数設定部２０２を用いることにより実現される。
山分け制約式設定手段および積姿制約式設定手段は、例えば、制約式設定部２０４を用いることにより実現される。
目的関数設定手段は、例えば、目的関数設定部２０３を用いることにより実現される。
払出山の総数は、例えば、Σi∈Nｘiiを用いることにより実現される。
逆転数は、例えば、Σ[i,j]∈Rｒijを用いることにより実現される。
山分け決定手段は、例えば、最適解導出部２０５を用いることにより実現される。
代表関係変数（決定変数）は、例えば、ｘijにより実現される（尚、ｉとｊは同じものと異なるものとを含む）。
積姿制約式は、例えば、（３）式を用いることにより実現される。
第１の制約式は、例えば、（７）式を用いることにより実現される。
第２の制約式は、例えば、（８）式を用いることにより実現される。
第３の制約式は、例えば、（９）式を用いることにより実現される。
第４の制約式は、例えば、（１０）式を用いることにより実現される。
第５の制約式は、例えば、（６）式を用いることにより実現される。
第６の制約式は、例えば、（１１）式および（１２）式（または（１１）´式および（１２）´式）を用いることにより実現される。
＜請求項２＞
第７の制約式は、例えば、（１６）式を用いることにより実現される。
＜請求項３＞
請求項３は、例えば、変数設定部２０２（による図５のフローチャートによる処理）を用いることにより実現される。
＜請求項４＞
鋼材グループは、例えば、スラブグループに対応する。
【符号の説明】
【０１１４】
２００：鋼材の山分け計画立案装置、２０１：入力部、２０２：変数設定部、２０３：目的関数設定部、２０４：制約式設定部、２０５：最適解導出部、２０６：出力部
【図１】
0006515339.tif 000012
【図２】
0006515339.tif 000013
【図３】
0006515339.tif 000014
【図４】
0006515339.tif 000015
【図５】
0006515339.tif 000016
【図６】
0006515339.tif 000017
【図７】
0006515339.tif 000018
【図８】
0006515339.tif 000019