ビジネス・アナリティクス - 熱延スケジューリング


熱延スケジューリング


プロジェクトの背景

製鉄所の熱延工程におけるスケジューリング問題は、大域的な制約、局所的な 制約が入り交じっており、また問題の規模も大きいため、これまで計算機による自 動化が進んでいませんでした。 熱延工程のスケジューリング問題を対象とした研究 論文もありますが、それらは局所的な制約のみに注目したものがほとんどで、その 多くが巡回セールスマン問題として定式化し局所探索で解くという手法です。 そのため、 これらを大域的な制約が重要で無視できないような実際の製鉄所において使用する ことは難しかったというのが実情なのです。


熱延工程におけるスケジューリング問題

製鉄所における熱延工程(Hot Strip Mill)とは、スラブと呼ばれる鋼鉄のかたま りを一枚ずつローラーで上下から挟んで引き延ばし、コイルと呼ばれる薄板に加工 する工程です。 生産されるコイルの表面品質はローラーの表面状態に依存します。 スラブの圧延を繰り返すとローラーの表面状態が悪くなっていくので、ある程度 の数のスラブを圧延すると、ローラーは新しいものに取り替えられます。 ローラーの取り替えから、次の取り替えまでの間のことをラウンドと呼びます。 このようなローラーの表面状態の変化のため、例えば高い品質が要求されるコイル を生産するには、ローラーの取り替え後、ローラーの傷みが少ない初めのうちに圧 延しなければならないなどの制約があります。 薄いコイルを圧延するには高い圧力が必要で温度も上昇するため、薄いコイルを圧 延するとローラーが徐々に痛んでいきます。 そのため、薄いコイルを連続して圧延できる数には制限があります。 また、ローラーの表面状態を回復させるために、厚みのあるコイルを挿入しなけれ ばなりません。

熱間圧延工程におけるスケジューリング問題とは、スラブプールの中から適切なス ラブを選択し、様々な制約を満たす複数ラウンドのスケジュールを作る問題です。

製鉄プロセスにおける熱間圧延工程

熱間圧延工程のスケジューリング問題は、ナップザック問題、制約充足問題、巡回 セールスマン問題が組み合わさった問題として捉えることができます。

ナップザック問題: 複数のラウンド間の解のバランスを取るために、またより長いラウンドを作るため に、スラブプールから適切なスラブを選択しなければなりません。

制約充足問題(大域的制約): ラウンド内の離れた場所にある2つのスラブにかかる制約です。 例えば、属性Aを持つスラブと、属性Bを持つスラブは同一ラウンドにおいては いけない。あるいは、属性Cを持つスラブは属性Dを持つスラブよりも前に圧延しな ければならない等です。

巡回セールスマン問題(局所的制約): 隣り合う2つのスラブに関わる制約を考慮しなければなりません。 例えば、隣り合う2つのスラブのコイルの厚さ、巾、張力などは、差が小さく移行 がなめらかなほどよいとされます。


An algorithm for HSM problem

この問題の難しいところは、現実的な時間(30分以内)で、 制約違反のない、人間のスケジュールの専門家が作り出すものに匹敵するスケジュー ルを自動生成することです。 私たちは、 最初にラウンドの大雑把な構成を決め、その後、徐々に詳細を決定していくような、 4ステップからなるCoarse-to-Fineアプローチをとりました。

  1. クラスタリング: 前処理として、局所制約を満たす、スラブ数が5~10程度の短いスラブ列をたく さん生成します。
  2. 粗スケジュール: 典型的なラウンドのパターン(最初に高品質コイル、次に薄いコイル、次に厚みの あるコイル、など)をブロックパターンとして定義しました。 そして、スラブクラスタをブロックパターンに割り当てる問題を整数計画問題とし て定式化しました。 整数計画問題では、大域的制約を考慮することができます。
  3. 詳細スケジュール: 粗スケジュールの結果を受けて、ラウンドの先頭部分や末尾の部分、また各ブロッ クの間などを、ラウンドが実行可能になるように、適当なスラブを挿入することで 補完していきます。
  4. 局所改善: ラウンドの良さを表す目的関数を向上させるために、ローカルサーチを適用します。 これにより、ラウンドをより長くしたり、隣り合うスラブの属性をなめらかにする ことなどが可能になります。

スケジューリングのキーとなる大域的制約を粗スケジュールで解決することで、 より良いスケジュールに繋がるラウンドの大枠を決定することができます。 またその後のステップの探索空間を制限することに寄与します。 その結果、人間のスケジューリングの専門家に匹敵するようなラウンドを自動的に 生成することができます。

Coarse to Fineアプローチによる解法