第1回輪講 2011.5.10 (火)

慶應義塾大学理工学部
管理工学科４年曹研究室
60803571
遠藤健司
 「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

の続きを読む
・ i( ) :
チャージ
・ j ({1(銑鉄),（製鋼）
2
,（鋳造）
3
}) : ステージ
・ k ({1,2,.., K }) : 単位時間
・ 　(  {1,2,..., N }) : 全てのチャージセット（Nは製造チャージの総数）
・ g ( g , h  {1,2,...,M },  h   g  0, h  g , 1   2  ...   M  )
: 鋳造機gにおける全てのチャージセット（Mは鋳造の総数）
・ S g , p ( p  1,2,..,|  g |) : 鋳造gにおけるチャージp（チャージの順序はロット計
・ di :
画によって定義される。）
チャージiの期日（単位時間の終了地点）
・ C1g : 鋳造gの鋳造中断による損失コスト率
・ C 2ij : ステージjの終了後、チャージiの待ち時間による損失コスト率
・ C 3i : 期日前の完了によって生じた製造チャージiに対する損失コスト率
・ C 4i : 期日遅延よって生じた製造チャージiに対する損失コスト率

鋳造機１
鋳造機２
1
2
・・・
鋳造機g
・・・
g
鋳造機M
M
M個の鋳造機
S g ,1
S g ,2
・・・
Sg , p
鋳造gには|Ωg|個のチャージがある
・・・
S g ,|g |

1　2　・・・　i　・・・　N
・ Ti , j :
ステージjにおけるチャージiの処理時間
・ t j , j 1 :
・ Sij :
ステージjからステージj+1に移るまでの輸送時間
ステージjの機械でチャージiをするためのセットアップ時間
（iが最初のチャージで鋳造時のみセットアップタイムを有する。）
・ Rij : ステージjの機械でチャージi処理後のリムーバル時間
（iが最初のチャージで鋳造時のみセットアップタイムを有する。）
・ M jk :
・ K:
単位時間kにステージjで利用できる機械の数
計画期間における単位時間の総数
決定変数
1　: チャージiが単位時間kにステージjで処理されている場合
・  ijk  
0　: その他
・ Ci , j ( {1,2,...,K }) :
ステージjでチャージiが完了する時間
（ Cij  k : 処理がちょうど単位時間kで完了した
）
M | g |1
Minim ize　Z  
 C1 (C
g 1 p 1
N
g
S g , p 1 , 3
 TS g , p1 ,3  CS g , p ,3 )
2
  C 2ij (Ci , j 1  Ti , j 1  Ci , j  t j , j 1 )
i 1 j 1
N
N
i 1
i 1
  C 3i max(0, d i  Ci 3 )   C 4i max(0, Ci 3  d i )
s.t.　Ci , j  t j , j 1  Ci , j 1  Ti , j 1　, i  ; j  {1,2}
 t j , j 1  Ti , j 1  Ci , j 1  Ci , j ①
ステージjからス
テージj+1までの
輸送時間
ステージjにおける
チャージiが完了した
時間
ステージjにおける
チャージiが完了した
時間
ステージj+1における
チャージiの処理時間
CS g , p 3　 CS g , p1 3　 TS g , p1 3　, p {1,2,...,|  g | 1}; g {1,2,...,M }
 TS g , p1 3　 CS g , p1 3　 CS g , p 3　②
鋳造gにおけるp+1番目
のチャージの処理時間
鋳造gにおけるp番目の
チャージが完了した時間
鋳造gにおけるp+1番目の
チャージが完了した時間
K
  ijk  Tij  Sij  Rij , i  ; j {1,2,3}　③
k 1
k ijk  Cij  Rij , i  ; j {1,2,3}; k {1,2,...,K }　④
Cij  Tij  Sij  1  k  K (1   ijk ), i  ; j {1,2,3}; k {1,2,...,K }
 Cij  1  k  Tij  Sij  K (1   ijk ) ⑤
ステージjにお
けるチャージi
のためのセット
アップ時間
ステージjにお
けるチャージi
の処理時間
ステージjにお
けるチャージi
が完了した時間
  ijk  M jk , j {1,2,3}; k {1,...,K }　⑥
i
 ijk  {0,1}, i  ; j  {1,2,3}; k  {1,...,K }　⑦
Cij  {1,2,...,K }, i  ; j  {1,2,3}; ⑧

制約式②と⑥は異なるジョブ→結合制約（coupling constraints）
この２つの式をラグランジュ緩和させることで、いくつかの部分問題
に分解でき、一つのジョブとして扱える。
→”i”と”Sg,p”を”＝”で結びつけることができる！チャージiのみを考え
るだけでよい！
 この２つの緩和した制約式にラグランジュ乗数 {ui }, {v jk } をかけ、目
的関数に組み込むことで、単なる制約の除去よりもよい下界値が得ら
れる。→残りの制約によって整数解を簡単に得ることができる。

M | g |1
Minim ize Z LR  
 C1 (C
g
g 1 p 1
N
S g , p1 , 3
 TS g , p1 ,3  CS g , p ,3 )
2
  C 2ij (Ci , j !  Ti , j 1  Ci , j  t j , j 1 )
i 1 j 1
N
N
i 1
i 1
  C 3i max(0, d i  Ci 3 )   C 4i max(0, Ci 3  d i )
M | g |1

u
g 1 p 1
K
(CS g , p1 ,3  TS g , p1 ,3  CS g , p ,3 )
3
  v jk (  ijk  M jk )
k 1 j 1
s.t　①
Sg ,p
i
, ③, ④, ⑤, ⑦, ⑧, and
u S g , p  0, p  {1,2,...,|  g | 1}; g  {1,2,...,M }
v jk  0, j  {1,2,3}; k  {1,2,...,K }
2
Minim ize　Z LR (i )   C 2ij (Ci , j 1  Ti , j 1  Ci , j  t j , j 1 )
j 1
 C 3i max(0, d i  Ci 3 )  C 4i max(0, Ci 3  d i )
K
3
  v jk ijk   (i )
k 1 j 1
s.t　①
, ③, ④, ⑤, ⑦, ⑧, and
 (i )  (u S
g ,p
 C1g )CS g , p ,3 , for　S g , p  {i}, p  {1}
 (i )  (u S
g ,p
 C1g )CS g , p ,3  (C1g  u S g , p )(CS g , p ,3  TS g , p ,3 ),
※
for　S g , p  {i}, p  {2,3,...,|  g | 1}　 (i )  (C1g  u S
g , p 1
)(C S g , p ,3  TS g , p ,3 ),
for　S g , p  {i}, p  {|  g |}
| g |1
| g |1
 C1g (CS g , p1 ,3  TS g , p1 ,3  CS g , p ,3 )
 uS g , p (CS g , p1 ,3  TS g , p1 ,3  CS g , p ,3 )
 C1g (CS g , 2 ,3  TS g , 2 ,3  CS g ,1 ,3 )
 uS g ,1 (CS g , 2 ,3  TS g , 2 ,3  CS g ,1 ,3 )
 C1g (CS g , 3 ,3  TS g , 3 ,3  CS g , 2 ,3 )
 uS g , 2 (CS g , 3 ,3  TS g , 3 ,3  CS g , 2 ,3 )
 
 C1g (CS g ,| | ,3  TS g ,| | ,3  CS g ,| |1 ,3 )
 
 uS g ,| |1 (CS g ,| | ,3  TS g ,| | ,3  CS g ,| |1 ,3 )
p 1
g
g
g
p 1
g
g
g
g
e.x.) 次のようにチャージを決定すると…
  {1,2,...,10}
1  {2,3,7}
 2  {1,4,5,10}
 3  {6,8,9}
i  S g , p 1　2 3　4 5　6 7 8　9 10
g 2 1　1　2 2 3　1　3　3　2
p 1　1　2 2 3　1　3　2 3　4
e.x.)　g  2, p  4
i  Sg, p  ?
C Sg , p ,3  Ci ,3  C?,3

鋳造機１
鋳造機２
1
2
・・・
鋳造機g
・・・
g
鋳造機M
M
M個の鋳造機
S g ,1
S g ,2
・・・
Sg , p
鋳造gには|Ωg|個のチャージがある
・・・
S g ,|g |


チャージiの部分問題を解くには、動的計画法(Dynamic
Programming,DP)を用いる。→最後のステージから最初のステージ
へと向かう、ボトムアップ的な手法
j=3(最後のステージ；鋳造）の場合のチャージiによるコスト
Vi 3 (Ci 3 , i 3k)  C 2i 2 (Ci ,3  Ti ,3 )  C 3i max(0, d i  Ci 3 )
K
 C 4i max(0, Ci 3  d i )   v3k  i 3k   (i )
k 1
 (i )  (u S
g,p
 C1g )CS g , p ,3 , for　S g , p  {i}, p  {1}
 (i )  (u S
g,p
 C1g )CS g , p ,3  (C1g  u S g , p )(CS g , p ,3  TS g , p ,3 ),
for　S g , p  {i}, p  {2,3,...,|  g | 1}　 (i )  (C1g  u S
g , p 1
)(CS g , p ,3  TS g , p ,3 ),
for　S g , p  {i}, p  {|  g |}

j=2(二番目のステージ；製鋼）の場合のチャージiによる累積コスト
Vi 2 (Ci 2 , i 2 k)  C 2i1 (Ci , 2  Ti , 2 )  C 2i 2 (Ci , 2  t2,3 ) K
  v2 k i 2 k  min {Vi 3 (Ci ,3 , i 3k)}
k 1

{Ci , 3 , i 3 k}
j=1(最初のステージ；製鉄）の場合のチャージiによる総コス
→最適部分問題のコスト
Vi1 (Ci1 , i1k)  C 2i1 (Ci ,1  t1, 2 ) K
  v1k i1k  min {Vi 2 (Ci , 2 , i 2 k)}
k 1
{Ci , 2 , i 2 k}

Download Report