慶應義塾大学 理工学部 管理工学科４年 曹研究室 遠藤 健司

Presentation on theme: "慶應義塾大学 理工学部 管理工学科４年 曹研究室 遠藤 健司"— Presentation transcript:

1 慶應義塾大学 理工学部 管理工学科４年 曹研究室 60803571 遠藤 健司
第2回輪講 (火) 慶應義塾大学 理工学部 管理工学科４年 曹研究室　 遠藤 健司

2 論文10 choice 鋼材加熱炉の装入スケジューリングと燃焼制御の同時最適化
Simultaneous Optimization of Charging Scheduling and Heating Control in Reheating Furnace 鉄と鋼　Vol.96(2010), No.7 pp 藤井 奨, 裏山 晃史, 加嶋 健司, 井村 順一, 黒川 哲明, 足立 修一

3 Integration of Systems Engineering-based Paradigms for the Scheduling and Control of an Experimental Hot-rolling Mill ISIJ International　Vol. 49 (2009), No. 1 pp.64-73 Miguel A. Gama d Mahdi Mahfouf A Modelling and Tabu Search Heuristic for a Continuous Galvanizing Line Scheduling Problem ISIJ International　Vol. 49 (2009) , No. 3 pp Lixin Tang and Cong Gao

4 Two Hybrid Metaheuristic Algorithms for Hot Rolling Scheduling
ISIJ International　 Vol. 49 (2009) , No. 4 pp Lixin Tang, Xiaoxia Zhang and Qingxin Guo A multi-population parallel genetic algorithm for highly constrained continuous galvanizing line scheduling Kapanoglu M (Kapanoglu, Muzaffer), Koc IO (Koc, Ilker Ozan) Almeida F; Aguilera MJB; Blum C; Vega JMM; Perez MP; Roli A; Sampels M HYBRID METAHEURISTICS, PROCEEDINGS LECTURE NOTES IN COMPUTER SCIENCE    Vol.4030 (2006) pp:28-41

5 Steel-making process scheduling using Lagrangian relaxation International Journal of Production Research International Journal of Production Research Volume 40, Issue 1, 2002, Pages Lixin Tang; Peter B. Luh; Jiyin Liu; Lei Fang Auction-based approach to resolve the scheduling problem in the steel making process Volume 44, Issue 8, 2006, Pages Vikas Kumar; Shashi Kumar; M. K. Tiwari; F. T. S. Chan

6 A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex European Journal of Operational Research Volume 182, Issue 3, 1 November 2007, Pages Lixin Tang and Guoli Liu Production scheduling in a steelmaking-continuous casting plant Computers & Chemical Engineering Volume 28, Issue 12, 15 November 2004, Pages Dario Pacciarelli and Marco Pranzo

7 Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling Computers & Operations Research Volume 34, Issue 9, September 2007, Pages Lixin Tang , Hua Xuan, and Jiyin Liu

8 今回取り扱った論文 「Steel-making process scheduling using Lagrangian relaxation」 Lixin Tang; Peter B; Jiyin Liu; Lei Fang Internatioal Journal of Production Research 2002, Vol40, No.1, 55-70

9 目的 学術論文に触れる。 英語の論文を熟読してみる。 鉄鋼製造スケジューリング（主に上工程）で用いられる数学的アルゴリズムを学ぶ。
今回はラグランジュ緩和

10 論文の構成 導入 問題の数学的定式化 解決方法 コンピューターによる実験 結論

11 予め…

12 1.導入 製鉄(高炉),製鋼(転炉)において… 鉄鋼製造プロセススケジューリングは「ジョブ(作業)」として定義されている。
アップグレードやメンテナンス時間が短い… しっかりとした制御管理によって次の４つの項目が達成できる。 But Then

13 製鉄,製鋼プロセス管理 同じ管理によって、同質 (規格)の鉄鋼が提供できる。 顧客に提供するスラブの幅を、一定の規格域に収めることができる。
納入期間を短縮できる。 溶鉱炉におけるスラブの容量を95％から100％に広げることができる。

14 1.導入 連続鋳造において… 同一鋳造には次のような技術的制約を満たす必要がある。
鉄鋼製造プロセススケジューリングは「グループ作業」として定義される。 同一鋳造には次のような技術的制約を満たす必要がある。

15 連続鋳造プロセス管理 鋳造された隣接している鋼質は均一でなければならない。 異なる鋳造によるスラブの規格は均一でなければならない。
同じ鋳造によるスラブの幅は降順でなければならない。 同じ鋳造によるスラブの幅の違いは規格内に収め、最大許容量を超えてはならない。 鋳造機の耐用年数は上限下限内に収める。 同じ鋳造による鋼材の納期はできるだけ短くする。

16 長期的なセットアップや移動時間の管理もある…
これら全ての項目を管理するのは大変。 長期的なセットアップや移動時間の管理もある… 機械によるスケジューリング計画＆管理（Tang et al. 2001） スケジューリングにおける３つの問題 sub-scheduling rough scheduling optimal scheduling

17 スケジューリングにおける３つの問題 非線形モデル→線形スケジューリングモデル （Tang et al. 2000）
低信頼複合的ナップザック問題→ヒューリスティック法（Kalagnanam et al. 2000） 整数計画モデルとネットワーク・ヒューリスティック法→銑鋼一貫製鋼所と鋳造へ （Cowling and Rezig 2000） 整数計画型ロットスケジューリングモデル →まるめ計画、列生成アプローチ（Chang et al. 2000）

18 HFS（hybrid flow shop） SPスケジューリングに広く用いられていた。
目的関数であるメイクスパンの最小化についての問題が、NP完全問題であることを指摘。（Vignier et al. 1998） SPはジョブグループや優先度のような多数の制約条件を要し、HFSでは定義できない。 SPのスケジューリング基準には、待ち時間や納期期日などの複雑な要素があり、HFSではメイクスパンの最小化しか定義できない。

19 HFS（hybrid flow shop）

20 2.問題の数学的定式化 2.1 問題提起と必要条件のモデル化
いつ、どの装置で、制御するかを決めることがSPスケジューリング HFSで実行可能な問題 前提 製鉄、製鋼、連続鋳造、それぞれの段階において、制御は一つの装置で処理し、並行して行う装置は同一のものとする。 装置は一度に一つの作業しか処理しない。 作業はどんな時でも、一度に一台の装置で処理される。 作業処理に先買権はない。

21 HFS以外の箇所の要約 スケジューリングされた管理工程は多くない。しかし、100t以上の高温の熔鉄を管理する必要がある。
鋳造は同じ機械で処理し、鋳造段階ではグループ管理に予め制約がある。 鋳造前後に、セットアップや移動が必要。その時間は処理時間と区別する。（セットアップは処理前に、移動は処理後に行う。） 鋳造機の中断などによるアイドル時間はコストが別途必要で望ましくない。 異なる段階の処理をしている間の待ち時間は、温度の低下を招き、加熱にはコストがかかる。 作業終了の遅速はコストを招く。（ex.在庫、顧客への賠償）

22 数学的に解釈すると… 目的：生産プロセスを継続的に行うこと、流れ作業から成るコスト要素を最小化し最終製品のJITを図ること。
鋳造の中断による損失は、同じ鋳造時間内における損失とみなす。 熔鉄の温度低下によるコストは作業間の待ち時間によるものとする。 遅速による損失は、スラブをできる限り納期に間に合わせる、という形で保証する。

23 2.2 表記 計画期間は小単位時間に分割し、整数の時間というパラメータを用いる。(例えば、処理、セットアップ、移動、移送は整数時間で表す。)
2.2　表記 計画期間は小単位時間に分割し、整数の時間というパラメータを用いる。(例えば、処理、セットアップ、移動、移送は整数時間で表す。) 製鉄、製鋼、連続鋳造は、段階1,2,3でそれぞれ表す。 パラメータ: Ω:全管理数 Ω={1,2,…,N} N:製造数 Ωg:g番目に鋳造する全管理数 g={1,2,…,M} M:鋳造数 Ωh∩Ωg=∅ ∀h g∈{1,2,…,M} g≠h　Ω1∪Ω2∪…∪ΩM=Ω sgp:鋳造gにおけるp番目の管理 p=1,2,…,|Ωg| di:管理iにおける納期(単位時間の終了地点)

24 パラメータ（続き） C1g:鋳造gにおける中断の損失率 C2ij:段階j終了後、管理iにおける待ち時間の損失率
C3i:納期前に完了した管理iにおける製品損失率 C4i:期日の遅れによる管理iの製品損失率 Tij:段階jにおける管理iの処理時間 tj,j+1:段階jから段階j+1に移る際の移動時間 Sij:段階jにおける管理iのセットアップ時間(鋳造最初の管理でj=3の時にセットアップが必要。それ以外はi,j,Sij=0) Rij:段階jにおける管理iの処理後移動時間(鋳造最後の管理でj=3の時に移動が必要。それ以外はi,j,Sij=0) Mjk:単位時間kの段階jにおいて利用できる機械数 K:計画期間の単位時間総数

25 決定変数 σijk = 1:管理iが単位時間kの段階jで処理する場合 0:その他 Cij:作業j内の管理i完了時間 i∈Ω j=1,2,3

26 定式化（目的関数） 連続鋳造における中断損失 製鉄、製鋼における待ち時間損失 納期の遅速による損失
計画期間においての、鋳造中断、待ち時間、遅速における総コストの最小化

27 定式化（制約条件） 段階jから段階j+1までの移動時間(tj,j+1) 段階jにおける管理iの完了地点(Ci,j+1)
製鉄、製鋼管理段階における作業の先行、同じ時間に二つ以上の段階の作業は行わない。 段階jから段階j+1までの移動時間(tj,j+1) 段階jにおける管理iの完了地点(Ci,j+1) 段階jにおける管理iの完了地点（Cij） 段階j+1における管理iの処理時間(Ti,j+1)

28 定式化（制約条件） 鋳造における管理(g,p+1)の処理時間（TSg,p+1,3）
鋳造における管理(g,p)の完了地点（CSgp3） 鋳造における管理(g,p+1)の完了地点（CSg,p+1,3）

29 定式化（制約条件） 各段階で機械が作業するために必要とされる総時間 全体のセットアップ時間 全体の処理時間 全体の移動時間

30 定式化（制約条件） ある段階で管理によって機械に必要とされる間隔 機械の容量制約 利用可能な領域

31 次回の予定 論文の続きを読む。（解法：①ラグランジュ緩和、②ダイナミックプログラミング、③オリジナル解法、④ラグランジュ乗数の応用）
要所に出てきた数学的アルゴリズムを勉強できれば… （ex. integer programming, dynamic programming etc…）