近似アルゴリズム第10章

近似アルゴリズム
第１０章
終了時刻最小化スケジューリング
徳山研究室
Ｂ４鈴木晶子
終了時刻最小化スケジューリング
• 入力
– 処理時間 p1 , p2 ,, pn の n 個のジョブ
p1
p3
p2
p7
p4
p8
p6
p5
p9
p10
– 整数 m
• ジョブを m 個の同一なマシーンに割り当てる
M1
p10
p9
M2
p8
p6
M3
M4
p5
p7
p3
p1
p2
p4
終了時刻
最小の終了時刻を実現するスケジュールを求める
発表の流れ
• ２近似アルゴリズム
• 終了時刻最小化スケジューリング問題に対する
PTAS
– ビンパッキング問題へのリダクション
– 制限されたビンパッキング問題
– コアアルゴリズム
• 定理10.8
終了時刻最小化スケジューリング問題に対するアルゴ
リズムは、終了時刻が高々 (1   )2  OPT  (1  3 )  OPT
の正しいスケジュールを求める。
２近似アルゴリズム
（アルゴリズム10.2）
1. ジョブを勝手に順番付ける。
1
3
2
8
7
5
4
9
6
10
2. この順番でジョブをマシンにスケジュールする。
このとき、それまでに割り当てたジョブの負荷が
最も少ないマシンに次のジョブを割り当てる。
M1
M2
M3
M4
8
1
6
2
9
3
4
7
5
10
定理10.3
アルゴリズム10.2は、終了時刻最小化スケ
ジューリング問題に対して、近似保証２を達成す
る。
[証明]
最適終了時刻OPTに対する２つの下界
1
1. 平均終了時刻
 pi
m
2. 最大処理時間
i
max { pi }
i
を用いる。
定理10.3の証明
start j
M1

Mi


1
 pi
m i
pj
Mm
アルゴリズムで作られたスケジュールで、
• M i ：最後にジョブが終了するマシーン
• j ： M i の最後のジョブのインデックス
• start j ：ジョブ j の処理が開始された時間
とする。
定理10.3の証明
start j
M1

Mi


1
 pi
m i
pj
Mm
•
start j の時刻まではどのマシーンも稼動中なので、
1
start j   pi  OPT
m i
• また、 p j  OPT
したがって、このスケジュールの終了時刻は
start j  p j  2 OPT
例題10.4
• アルゴリズム10.2のタイトな例
2
m
– 処理時間1の個のジョブと、
処理時間 m の1個のジョブ
m
M1 1
M1
M2
M2 1
M3
M3


Mm
Mm
m個
終了時刻は 2 m
m
m個
最適解 m  1
最小終了時刻の上界と下界
• 最小終了時刻の下界
1

LB  max i pi , max{ pi }
i
m

• 最小終了時刻の上界
定理10.3より、 start j  p j  2 LB
最小終了時刻
最小終了時刻は、区間[LB, 2・LB]内に存在する
ビンパッキング問題へのリダクション
• 終了時刻 t のスケジューリングが存在するため
の必要十分条件
– n 個のサイズ p1 , p2 ,, pn の品物を
容量 t の m 個のビンにパッキングできること
• ビンパッキング問題へのリダクション
– n 個の品物のサイズ p1 , p2 ,, pn を I と表す
– サイズ t のビンに、 n 個の品物をパッキングする
– このとき、使用するビンの最小個数を bins( I, t ) とする
最小終了時刻は
min{ t | bins ( I , t )  m}
ビンパッキング問題へのリダクション
最小終了時刻 min{t | bins( I , t )  m} を
どのようにして求めるか
最小終了時刻の下界と上界はLBと2・LB
区間[LB, 2・LB]を２分探索することにより、
bins( I , t )  m を満たす最小の t を求める

bins( I, t ) を求める必要があるが、
ビンパッキング問題はNP-困難

異なる品物のサイズが定数個のとき、
ビンパッキング問題は多項式時間で解ける
制限されたビンパッキング問題
• 異なる品物のサイズが定数個のときのパッキン
グを求める
– k ：異なる品物のサイズ（定数）
– ビンの容量は１とする
• 例： k  4
ビン
容量１
0.8
0.4
0.5
0.2
0.4
動的計画法に基づくアルゴリズム
準備
• 品物のサイズを順番に並べる。
• 各サイズの品物の個数をならべた k 組の数
(i1 , i2 ,, ik ) をビンパッキング問題のインスタンス
とする。
0.2
0.4 0.4
0.5
0.8
インスタンス (1, 2, 1, 1)
• インスタンス (i1 , i2 ,, ik ) の品物をパッキング
するのに必要な最小ビン数を BINS(i1 , i2 ,, ik ) と
する。
動的計画アルゴリズム
1.
与えられたインスタンス (n1 , n2 ,, nk ) に対して、
Q  {(q1, q2 ,, qk ) | BINS(q1, q2 ,, qk )  1, 0  qi  ni , 1  i  k}
を計算する。
容量１のビン１個の中に入る品物の個数
(q1 , q2 ,, qk ) の組を全て求め、その集合を Q とする。
0.2
0.4 0.4
0.5
0.8
Q  {(0,0,0,1), (0,0,1,0), (0,1,0,0), (0,1,1,0), (0,2,0,0),
(1,0,0,0), (1,0,0,1), (1,0,1,0), (1,1,0,0), (1,2,0,0)}
動的計画アルゴリズム
2.
各 (i1 , i2 ,, ik ) {0,n1}{0,n2}{0,nk } に
対して、各 BINS(i1 , i2 ,, ik ) の値の表を作成する。
初期値 a. BINS(0, 0,0)  0
b. q  Q に対して、
BINS(q)  1
i1 i2
i3 i4
00
10
01
11
02
12
00
0
1
1
1
1
1
10
1
1
1
01
1
1
11
動的計画アルゴリズム
2.
各 (i1 , i2 ,, ik ) {0,n1}{0,n2}{0,nk } に
対して、各 BINS(i1 , i2 ,, ik ) の値の表を作成する。
表の残りの要素の値を、
BINS (i1 , i2 ,, ik )  1  min BINS (i1  q1 ,, ik  qk )
qQ
から計算する。
i1 i2
i3 i4
00
10
01
11
02
12
00
0
1
1
1
1
1
10
1
1
1
01
1
1
11
2. 表の残りの要素の値を、
BINS (i1 , i2 ,, ik )  1  min BINS (i1  q1 ,, ik  qk )
qQ
から計算する。
i1 i2
i3 i4
00
10
01
11
02
12
00
0
1
1
1
1
1
10
1
1
1
2
2
2
01
1
1
2
2
2
2
11
2
2
2
2
3
3
BINS(1,1,1,0)  1  BINS(1  1, 1  1, 1  0, 0  0)
 1  BINS(0,0,1,0)
(1,1,0,0)  Q
2
動的計画アルゴリズムの計算時間
パッキングする品物の数の合計を n とする。 (i 1 ni  n)
k
1.
与えられたインスタンス (n1 , n2 ,, nk ) に対して
BINS(q1 , q2 ,, qk )  1 を満たす集合 Q を計算する
全ての場合について当てはめてみればよいので、
Q の要素は高々 O(n k )個
2.
各 (i1 , i2 ,, ik ) {0,n1}{0,n2}{0,nk }に対し
て BINS(i1 , i2 ,, ik ) の値の表を作成する
各要素の計算時間は
k
O( n )
時間
BINS(i1 , i2 ,, ik ) の表全体は O(n 2k ) 時間で計算できる
ビンパッキング問題へのリダクション
品物のサイズが定数個ならば、
最適なパッキングを求めることが可能
品物のサイズが定数個になるように補正すれば、
サイズが定数個でなくても
最適パッキングを求めることが可能
最小終了時刻の計算に誤差をある程度認めれば、
最小終了時刻スケジューリング問題は
ビンパッキング問題にリダクションできる
コアアルゴリズム
• 最小終了時刻を計算するPTASの中核となるア
ルゴリズム
• 入力
– インスタンス I
– ビンの容量 t
– 誤差パラメータε
• インスタンス I に対する、容量 t(1+ε) のビンへの
パッキングと、パッキングに必要なビンの数
 (I , t,  )
を求める
• 終了時刻 t(1+ε) のスケジュールと、それを実現
するために必要なマシンの数を求める
コアアルゴリズム
1. サイズ tε未満の品物を除く
2. サイズが定数個になるように、品物のサイズを補正する
3. 動的計画アルゴリズムを用いて、
補正した品物を容量 t のビンにパッキングする
4. ビンの容量を t(1+ε) とし、残りの小さい品物を
パッキングする
コアアルゴリズム
1.
2.
3.
4.
サイズtε未満の品物を除く
サイズが定数個になるように、品物のサイズを補正する
補正した品物を容量 t のビンにパッキングする
ビンの容量を t(1+ε) とし、残りの小さい品物をパッキングする
• εを誤差パラメータとする
• t は区間[LB, 2・LB]内にあるとする
t
最初、サイズ tε未満の品物は無視する
コアアルゴリズム
1.
2.
3.
4.
サイズtε未満の品物を除く
サイズが定数個になるように、品物のサイズを補正する
補正した品物を容量 t のビンにパッキングする
ビンの容量を t(1+ε) とし、残りの小さい品物をパッキングする
各 i  0 に対して、区間 [t (1   )i , t (1   )i 1 ) に
属するサイズ p j を、 pj  t (1   )i で置き換える。
もとのサイズ p j
t  p j  t (1   )
t (1   )  p j  t (1   )2

t (1   )i  p j  t (1   )i 1

補正後のサイズ pj
t
t (1   )

t (1   )i

コアアルゴリズム
1.
2.
3.
4.
サイズtε未満の品物を除く
サイズが定数個になるように、品物のサイズを補正する
補正した品物を容量 t のビンにパッキングする
ビンの容量を t(1+ε) とし、残りの小さい品物をパッキングする
補正後のサイズ pj
もとのサイズ p j
t
t  p j  t (1   )

t (1   )  p j  t (1   )
i

t (1   )i
i 1




各品物は、高々1   の割合でサイズを縮小されている
異なる品物のサイズの個数 k は
t (1  )k  p j  t  t (1   )k 1 より
 (1   )k  1
k  log1
1


コアアルゴリズム
1.
2.
3.
4.
サイズtε未満の品物を除く
サイズが定数個になるように、品物のサイズを補正する
補正した品物を容量 t のビンにパッキングする
ビンの容量を t(1+ε) とし、残りの小さい品物をパッキングする
• 異なるサイズが k 個の品物について、サイズ t のビン
に対する最適パッキングを決定する。
• 動的計画アルゴリズムを用いる


各品物は、高々1   の割合でサイズを縮小されている
ビンの容量を t (1   ) とすれば、サイズをもとに戻しても
正しいパッキングになる
コアアルゴリズム
サイズtε未満の品物を除く
サイズが定数個になるように、品物のサイズを補正する
補正した品物を容量 t のビンにパッキングする
ビンの容量を t(1+ε) とし、残りの小さい品物をパッキングする
1.
2.
3.
4.
•
•
ビンのサイズを t (1   )として、最初に除いた小さい品物
をグリーディーにビンの隙間へ入れていく。
必要ならば新しいビンを開けて用いる。
t
t
補題10.5
コアアルゴリズムで使用されるビンの個数を
 (とおく。このとき、
I , t,  )
 ( I , t ,  )  bins( I , t )
インスタンス I をサイズ t のビンにパッキング
する時に使用する、ビンの最小個数
[証明]
アルゴリズムで小さい品物を入れるとき
• 新しいビンが使用されない場合
• 新しいビンが使用された場合
に分けて証明する。
補題10.5の証明
• 新しいビンが使用されない場合
– 小さく補正された品物は、サイズ t のビンに最適に
パッキングされている
– もとのインスタンスには、アルゴリズムでパッキングさ
れた品物よりも大きな品物が含まれている
– もとのインスタンスをサイズ t のビンにパッキングする
には、少なくとも  ( I , t ,  ) 個のビンが必要
補題10.5の証明
• 新しいビンが使用される場合
– 最後のビンを除いて、どのビンにも t を越えて品物が
入れられている
t
……
– これらの品物をサイズ t のビンに入れようとすると、少
なくとも  ( I , t ,  ) 個のビンが必要となる
したがって、
サイズtのビンへのIの品物の最適パッキングは、
ビンを少なくとも  ( I , t ,  ) 個用いる
系10.6
• 補題10.5より、 ( I , t ,  )  bins( I , t )
• OPT  min{t | bins( I , t )  m}
これらより、
min{ t |  ( I , t ,  )  m}  OPT
min{ t |  ( I , t ,  )  m} を決定することができると…
コアアルゴリズムの出力より、容量 t(1+ε) のビンへの
パッキングを求めることができる
終了時刻 t(1+ε) のスケジュールを求めることができる
終了時刻 (1+ε)OPT 以内のスケジュールを求めることが
できる
２分探索
min{t |  ( I , t ,  )  m} を求める
• 区間[LB, 2・LB]を２分探索することにより求める
• 一度２分探索が行われるごとに、探索区間の範
囲は半分になる
ε・LB以下→探索終了
LB
min{ t |  ( I , t ,  )  m}
2・LB
• 探索を多項式時間内で終了するために、探索区間
の範囲が   LB 以下になったら探索を終了する
探索の回数は log2 1  回
補題10.7
２分探索において、終了時点での区間の右側の点をTと
する。
T
LB
2・LB
終了時点での探索区間
このとき、 T  (1   )  OPT が成り立つ。
[証明]
• min{ t |  ( I , t ,  )  m} は区間[LB, 2・LB]に含まれるので、
T  min{t |  ( I , t ,  )  m}    LB
•
min{t |  ( I , t ,  )  m}  OPT
•
LB  OPT
（OPTの下界）
これらより、 T  (1   )  OPT
（系10.6）
終了時刻最小化スケジューリング問題
に対するアルゴリズム
T
LB
min{ t |  ( I , t ,  )  m}
2・LB
• 区間[LB, 2・LB]を２分探索
• 探索区間の中点 t について、コアアルゴリズムを
用いて  ( I , t ,  ) を求める
 ( I , t ,  )  m なら t の右側を探索
 ( I , t ,  )  m なら t の左側を探索
• 探索区間の範囲が   LB になったら探索を終了
–
–
– 終了時点での区間の右側の点を T とする
• t = T に対するコアアルゴリズムの出力から、スケ
ジュールを得る
定理10.8
このアルゴリズムは、終了時刻が高々
(1   )  OPT  (1  3 )  OPT
2
の正しいスケジュールを求める。
[証明]
• t = T に対するコアアルゴリズムの出力は、終了
時刻が高々 T  (1   ) のスケジュール
• T  (1   )  OPT
（補題10.7）
よって終了時刻は高々 (1  3 )  OPT
アルゴリズムの計算時間
• 制限されたビンパッキング問題に対する動的計
画アルゴリズムの計算時間： O(n 2k )
• コアアルゴリズムの計算時間： O(n 2k )
• 異なる品物のサイズの数 k ： k  log1
1


• ２分探索の回数： log2 1  回
これらを合わせると、計算時間は
O(n2k log2 1 )
ただし、
k  log1
1


おわり

Download Report