第1回輪講 2011.5.10 (火)

慶應義塾大学理工学部
管理工学科４年曹研究室
60803571
遠藤健司
1.
鋼材加熱炉の装入スケジューリングと燃焼制御の同時
最適化
Simultaneous Optimization of Charging Scheduling and
Heating Control in Reheating Furnace
 鉄と鋼
Vol.96(2010), No.7 pp.434-442
 藤井奨, 裏山晃史, 加嶋健司, 井村順一, 黒川哲明, 足
立修一
2.
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.375-384
 Lixin Tang and Cong Gao
4.
Two Hybrid Metaheuristic Algorithms for Hot Rolling
Scheduling
ISIJ International
Vol. 49 (2009) , No. 4 pp.529-538
Lixin Tang, Xiaoxia Zhang and Qingxin Guo
5.
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
6.
Steel-making process scheduling using Lagrangian
relaxation International Journal of Production
Research



7.
International Journal of Production Research
Volume 40, Issue 1, 2002, Pages 55 - 70
Lixin Tang; Peter B. Luh; Jiyin Liu; Lei Fang
Auction-based approach to resolve the scheduling
problem in the steel making process



International Journal of Production Research
Volume 44, Issue 8, 2006, Pages 1503 - 1522
Vikas Kumar; Shashi Kumar; M. K. Tiwari; F. T. S. Chan
8.
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 1453-1468
 Lixin Tang and Guoli Liu
9.
Production scheduling in a steelmaking-continuous casting
plant
 Computers & Chemical Engineering
 Volume 28, Issue 12, 15 November 2004, Pages 2823-2835
 Dario Pacciarelli and Marco Pranzo
10.
Hybrid backward and forward dynamic programming based
Lagrangian relaxation for single machine scheduling
 Computers & Operations Research
Volume 34, Issue 9, September 2007, Pages 2625-2636
 Lixin Tang , Hua Xuan, and Jiyin Liu
Internatioal Journal of Production Research
 2002, Vol40, No.1, 55-70





学術論文に触れる。
英語の論文を熟読してみる。
鉄鋼製造スケジューリング（主に上工
程）で用いられる数学的アルゴリズムを
学ぶ。
今回はラグランジュ緩和
1.
2.
3.
4.
5.
導入
問題の数学的定式化
解決方法
コンピューターによる実験
結論
 製鉄(高炉),製鋼(転炉)において…

鉄鋼製造プロセススケジューリングは「ジョブ
(作業)」として定義されている。
But

アップグレードやメンテナンス時間が短い…
Then

しっかりとした制御管理によって次の４つの項
目が達成できる。
1.
同じ管理によって、同質 (規格)の鉄鋼
が提供できる。
2.
顧客に提供するスラブの幅を、一定の規
格域に収めることができる。
納入期間を短縮できる。
溶鉱炉におけるスラブの容量を95％から
100％に広げることができる。
3.
4.
 連続鋳造において…

鉄鋼製造プロセススケジューリングは「グ
ループ作業」として定義される。
 同一鋳造には次のような技術的制約を満
たす必要がある。
1.
鋳造された隣接している鋼質は均一でなければな
らない。
2.
異なる鋳造によるスラブの規格は均一でなければ
ならない。
3.
同じ鋳造によるスラブの幅は降順でなければなら
ない。
4.
同じ鋳造によるスラブの幅の違いは規格内に収め、
最大許容量を超えてはならない。
鋳造機の耐用年数は上限下限内に収める。
同じ鋳造による鋼材の納期はできるだけ短くする。
5.
6.
これら全ての項目を管理するのは大変。
 長期的なセットアップや移動時間の管理もあ
る…

機械によるスケジューリング計画＆管理
（Tang et al. 2001）
 スケジューリングにおける３つの問題

1.
2.
3.
sub-scheduling
rough scheduling
optimal scheduling
非線形モデル→線形スケジューリングモデル
（Tang et al. 2000）
 低信頼複合的ナップザック問題→ヒューリス
ティック法（Kalagnanam et al. 2000）
 整数計画モデルとネットワーク・ヒューリス
ティック法→銑鋼一貫製鋼所と鋳造へ
（Cowling and Rezig 2000）
 整数計画型ロットスケジューリングモデル
→まるめ計画、列生成アプローチ（Chang et
al. 2000）

 SPスケジューリングに広く用いられていた。
 目的関数であるメイクスパンの最小化につ
いての問題が、NP完全問題であることを指
摘。（Vignier et al. 1998）
1. SPはジョブグループや優先度のような多数
の制約条件を要し、HFSでは定義できない。
2. SPのスケジューリング基準には、待ち時間
や納期期日などの複雑な要素があり、HFS
ではメイクスパンの最小化しか定義できな
い。
いつ、どの装置で、制御するかを決めること
がSPスケジューリング
 HFSで実行可能な問題
 前提

1.
2.
3.
4.
製鉄、製鋼、連続鋳造、それぞれの段階におい
て、制御は一つの装置で処理し、並行して行う
装置は同一のものとする。
装置は一度に一つの作業しか処理しない。
作業はどんな時でも、一度に一台の装置で処理
される。
作業処理に先買権はない。
1.
2.
3.
4.
5.
6.
スケジューリングされた管理工程は多くない。しか
し、100t以上の高温の熔鉄を管理する必要がある。
鋳造は同じ機械で処理し、鋳造段階ではグループ管
理に予め制約がある。
鋳造前後に、セットアップや移動が必要。その時間
は処理時間と区別する。（セットアップは処理前に、
移動は処理後に行う。）
鋳造機の中断などによるアイドル時間はコストが別
途必要で望ましくない。
異なる段階の処理をしている間の待ち時間は、温度
の低下を招き、加熱にはコストがかかる。
作業終了の遅速はコストを招く。（ex.在庫、顧客へ
の賠償）
 目的：生産プロセスを継続的に行うこと、
流れ作業から成るコスト要素を最小化し
最終製品のJITを図ること。
1. 鋳造の中断による損失は、同じ鋳造時間
内における損失とみなす。
2. 熔鉄の温度低下によるコストは作業間の
待ち時間によるものとする。
3. 遅速による損失は、スラブをできる限り
納期に間に合わせる、という形で保証す
る。
計画期間は小単位時間に分割し、整数の時間
というパラメータを用いる。(例えば、処理、
セットアップ、移動、移送は整数時間で表
す。)
 製鉄、製鋼、連続鋳造は、段階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における納期(単位時間の終了地点)










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:計画期間の単位時間総数
 σijk
=
1:管理iが単位時間kの段階jで処理する場合
0:その他
 Cij:作業j内の管理i完了時間
j=1,2,3
i∈Ω
連続鋳造における
中断損失
製鉄、製鋼における
待ち時間損失
納期の遅速による損失
•計画期間においての、鋳造中断、待ち時間、遅速における総コストの最小化
•製鉄、製鋼管理段階における作業の先行、同じ時間に二つ以上の段階の作業は行わない。
段階jから段階j+1
までの移動時間
(tj,j+1)
段階jにおける管理i
の完了地点（Cij）
段階j+1における管理i
の処理時間(Ti,j+1)
段階jにおける管理
iの完了地点
(Ci,j+1)
•鋳造において(g,p)期間の管理の先行。
鋳造における管理
(g,p+1)の処理時間
（TSg,p+1,3）
鋳造における管理(g,p)
の完了地点（CSgp3）
鋳造における管理
(g,p+1)の完了地点
（CSg,p+1,3）
•各段階で機械が作業するために必要とされる総時間
全体のセットアップ時間
全体の処理時間
全体の移動時間
•ある段階で管理によって機械に必要とされる間隔
•機械の容量制約
•利用可能な領域
 論文の続きを読む。（解法：①ラグラン
ジュ緩和、②ダイナミックプログラミン
グ、③オリジナル解法、④ラグランジュ
乗数の応用）
 要所に出てきた数学的アルゴリズムを勉
強できれば…
（ex. integer programming, dynamic
programming etc…）

Download Report