近似アルゴリズム 第１０章 終了時刻最小化スケジューリング 徳山研究室 Ｂ４　鈴木晶子

終了時刻最小化スケジューリング 入力 ジョブを 個の同一なマシーンに割り当てる 最小の終了時刻を実現するスケジュールを求める 処理時間　　　　　　　　の　　個のジョブ 整数 ジョブを　　個の同一なマシーンに割り当てる 終了時刻 最小の終了時刻を実現するスケジュールを求める

発表の流れ ２近似アルゴリズム 終了時刻最小化スケジューリング問題に対するPTAS 定理10.8 ビンパッキング問題へのリダクション 制限されたビンパッキング問題 コアアルゴリズム 定理10.8 終了時刻最小化スケジューリング問題に対するアルゴ リズムは、終了時刻が高々　　　　　　　　　　　　　 の正しいスケジュールを求める。

２近似アルゴリズム （アルゴリズム10.2） ジョブを勝手に順番付ける。 この順番でジョブをマシンにスケジュールする。 　　 このとき、それまでに割り当てたジョブの負荷が 　　 最も少ないマシンに次のジョブを割り当てる。

定理10.3 アルゴリズム10.2は、終了時刻最小化スケジューリング問題に対して、近似保証２を達成する。 [証明] 　　最適終了時刻OPTに対する２つの下界 　　を用いる。 平均終了時刻 最大処理時間

定理10.3の証明 アルゴリズムで作られたスケジュールで、 ：最後にジョブが終了するマシーン ： の最後のジョブのインデックス 　　　：最後にジョブが終了するマシーン 　　　：　　の最後のジョブのインデックス 　　　　 ：ジョブ　の処理が開始された時間 とする。

定理10.3の証明 の時刻まではどのマシーンも稼動中なので、 また、 したがって、このスケジュールの終了時刻は

例題10.4 アルゴリズム10.2のタイトな例 処理時間1の　　個のジョブと、 　 処理時間　　の1個のジョブ 個 個 終了時刻は 最適解

最小終了時刻の上界と下界 最小終了時刻の下界 最小終了時刻の上界 定理10.3より、 最小終了時刻は、区間[LB, 2・LB]内に存在する

ビンパッキング問題へのリダクション 終了時刻 t のスケジューリングが存在するための必要十分条件 ビンパッキング問題へのリダクション n 個のサイズ　　　　　　　　 の品物を 　 容量 t の m 個のビンにパッキングできること ビンパッキング問題へのリダクション 　　個の品物のサイズ　　　　　　　　を I と表す サイズ t のビンに、 n 個の品物をパッキングする このとき、使用するビンの最小個数を　　　　　　とする 　　最小終了時刻は

ビンパッキング問題へのリダクション 最小終了時刻 を どのようにして求めるか 最小終了時刻の下界と上界はLBと2・LB 最小終了時刻　　　　　　　　　　　　　　を どのようにして求めるか 最小終了時刻の下界と上界はLBと2・LB 区間[LB, 2・LB]を２分探索することにより、 　　　　　　　　　 を満たす最小の t を求める 　bins( I, t ) を求める必要があるが、 　　ビンパッキング問題はNP-困難 　異なる品物のサイズが定数個のとき、 ビンパッキング問題は多項式時間で解ける

制限されたビンパッキング問題 異なる品物のサイズが定数個のときのパッキングを求める 例： k ：異なる品物のサイズ（定数） ビンの容量は１とする 例： 0.8 ビン 容量１ 0.5 0.4 0.4 0.2

動的計画法に基づくアルゴリズム 準備 品物のサイズを順番に並べる。 各サイズの品物の個数をならべた k 組の数 　 　　　　　　 をビンパッキング問題のインスタンスとする。 インスタンス　　　　　　　　　の品物をパッキングするのに必要な最小ビン数を　　　　　　　　　　　とする。 0.8 0.5 0.4 0.4 0.2

動的計画アルゴリズム 与えられたインスタンス に対して、 を計算する。 容量１のビン１個の中に入る品物の個数 与えられたインスタンス　　　　　　　　　に対して、 　　 を計算する。 容量１のビン１個の中に入る品物の個数 　　　　　　　　　　　の組を全て求め、その集合を　　とする。 0.8 0.5 0.4 0.4 0.2

動的計画アルゴリズム 各　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　に対して、各　　　　　　　　　　　の値の表を作成する。 初期値 0 0 1 0 0 1 1 1 0 2 1 2 1

動的計画アルゴリズム 各 に対して、各 の値の表を作成する。 表の残りの要素の値を、 から計算する。 0 0 1 0 0 1 1 1 0 2 各　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　に対して、各　　　　　　　　　　　の値の表を作成する。 表の残りの要素の値を、 から計算する。 0 0 1 0 0 1 1 1 0 2 1 2 1

表の残りの要素の値を、 から計算する。 0 0 1 0 0 1 1 1 0 2 1 2 1 2 3 2

動的計画アルゴリズムの計算時間 パッキングする品物の数の合計を とする。 与えられたインスタンス に対して を満たす集合 を計算する パッキングする品物の数の合計を　　とする。 与えられたインスタンス　　　　　　　　に対して 　　　　　　　　　 　　　　　　　　を満たす集合　　を計算する 各　　　　　　　　　　　　　　　　　　　　　　　　　　　　　に対し て　　　　　　　　　　　の値の表を作成する 全ての場合について当てはめてみればよいので、 　　の要素は高々　　　　　個 各要素の計算時間は　　　　　　時間 の表全体は　　　　　　時間で計算できる

ビンパッキング問題へのリダクション 品物のサイズが定数個ならば、 最適なパッキングを求めることが可能 品物のサイズが定数個になるように補正すれば、 サイズが定数個でなくても 最適パッキングを求めることが可能 最小終了時刻の計算に誤差をある程度認めれば、 最小終了時刻スケジューリング問題は ビンパッキング問題にリダクションできる

コアアルゴリズム 最小終了時刻を計算するPTASの中核となるアルゴリズム 入力 インスタンス I ビンの容量 t 誤差パラメータε インスタンス I に対する、容量 t(1+ε) のビンへのパッキングと、パッキングに必要なビンの数　　　　　　　　　を求める 終了時刻 t(1+ε) のスケジュールと、それを実現するために必要なマシンの数を求める

コアアルゴリズム サイズ tε未満の品物を除く サイズが定数個になるように、品物のサイズを補正する 動的計画アルゴリズムを用いて、 　　 パッキングする

コアアルゴリズム εを誤差パラメータとする t は区間[LB, 2・LB]内にあるとする サイズtε未満の品物を除く サイズが定数個になるように、品物のサイズを補正する 補正した品物を容量 t のビンにパッキングする ビンの容量を t(1+ε) とし、残りの小さい品物を パッキングする 　εを誤差パラメータとする 　 t は区間[LB, 2・LB]内にあるとする 最初、サイズ tε未満の品物は無視する

コアアルゴリズム 各 に対して、区間 に 属するサイズ を、 で置き換える。 サイズtε未満の品物を除く サイズが定数個になるように、品物のサイズを補正する 補正した品物を容量 t のビンにパッキングする ビンの容量を t(1+ε) とし、残りの小さい品物を パッキングする 各　　　　に対して、区間　　　　　　　　　　　　　　に 属するサイズ　　を、　　　　　　　　　で置き換える。 もとのサイズ　　 補正後のサイズ　　

コアアルゴリズム 各品物は、高々 の割合でサイズを縮小されている 異なる品物のサイズの個数 k は より サイズtε未満の品物を除く サイズが定数個になるように、品物のサイズを補正する 補正した品物を容量 t のビンにパッキングする ビンの容量を t(1+ε) とし、残りの小さい品物を パッキングする もとのサイズ　　 補正後のサイズ　　 　各品物は、高々　　　の割合でサイズを縮小されている 　異なる品物のサイズの個数 k は 　　　　　　　　　　　　　　　　　　　　　より

コアアルゴリズム 異なるサイズが k 個の品物について、サイズ t のビン に対する最適パッキングを決定する。 動的計画アルゴリズムを用いる サイズが定数個になるように、品物のサイズを補正する 補正した品物を容量 t のビンにパッキングする ビンの容量を t(1+ε) とし、残りの小さい品物を パッキングする 異なるサイズが k 個の品物について、サイズ t のビン に対する最適パッキングを決定する。 動的計画アルゴリズムを用いる 　各品物は、高々　　　の割合でサイズを縮小されている 　ビンの容量を　　　　　とすれば、サイズをもとに戻しても 正しいパッキングになる

コアアルゴリズム ビンのサイズを として、最初に除いた小さい品物をグリーディーにビンの隙間へ入れていく。 サイズtε未満の品物を除く サイズが定数個になるように、品物のサイズを補正する 補正した品物を容量 t のビンにパッキングする ビンの容量を t(1+ε) とし、残りの小さい品物を パッキングする ビンのサイズを　　　　 として、最初に除いた小さい品物をグリーディーにビンの隙間へ入れていく。 必要ならば新しいビンを開けて用いる。

補題10.5 コアアルゴリズムで使用されるビンの個数を とおく。このとき、 [証明] アルゴリズムで小さい品物を入れるとき コアアルゴリズムで使用されるビンの個数を　　　　　　　　　とおく。このとき、 [証明] アルゴリズムで小さい品物を入れるとき 新しいビンが使用されない場合 新しいビンが使用された場合 に分けて証明する。 インスタンス I をサイズ t のビンにパッキング する時に使用する、ビンの最小個数

補題10.5の証明 新しいビンが使用されない場合 小さく補正された品物は、サイズ t のビンに最適にパッキングされている もとのインスタンスには、アルゴリズムでパッキングされた品物よりも大きな品物が含まれている もとのインスタンスをサイズ t のビンにパッキングするには、少なくとも　　　　　　個のビンが必要

サイズtのビンへのIの品物の最適パッキングは、 補題10.5の証明 新しいビンが使用される場合 最後のビンを除いて、どのビンにも t を越えて品物が入れられている これらの品物をサイズ t のビンに入れようとすると、少なくとも　　　　　　　個のビンが必要となる …… したがって、 サイズtのビンへのIの品物の最適パッキングは、 ビンを少なくとも　　　　　　個用いる

系10.6 補題10.5より、 これらより、 を決定することができると… コアアルゴリズムの出力より、容量 t(1+ε) のビンへの これらより、　 を決定することができると… コアアルゴリズムの出力より、容量 t(1+ε) のビンへの パッキングを求めることができる 終了時刻 t(1+ε) のスケジュールを求めることができる 終了時刻 (1+ε)OPT 以内のスケジュールを求めることが できる

２分探索 を求める 区間[LB, 2・LB]を２分探索することにより求める 一度２分探索が行われるごとに、探索区間の範囲は半分になる 　　　　　　　　　　　　　　を求める 区間[LB, 2・LB]を２分探索することにより求める 一度２分探索が行われるごとに、探索区間の範囲は半分になる ε・LB以下→探索終了 LB 2・LB 探索を多項式時間内で終了するために、探索区間 の範囲が　　　　以下になったら探索を終了する 探索の回数は　　　　　回

補題10.7 ２分探索において、終了時点での区間の右側の点をTとする。 このとき、 が成り立つ。 [証明] このとき、 　　　　　　　　　　が成り立つ。 [証明] 　　　　　　　　　　　　　は区間[LB, 2・LB]に含まれるので、 　　　　　　　　　　　　　　　　　　　　（系10.6） 　 　　　　　（OPTの下界） これらより、 LB 2・LB 終了時点での探索区間

終了時刻最小化スケジューリング問題に対するアルゴリズム 区間[LB, 2・LB]を２分探索 探索区間の中点 t について、コアアルゴリズムを用いて　　　　　　を求める 　　　　　　　　　　なら t の右側を探索 　　　　　　　　　　なら t の左側を探索 探索区間の範囲が　　　　になったら探索を終了 終了時点での区間の右側の点を T とする　 t = T に対するコアアルゴリズムの出力から、スケジュールを得る LB 2・LB

定理10.8 このアルゴリズムは、終了時刻が高々 の正しいスケジュールを求める。 [証明] 　このアルゴリズムは、終了時刻が高々 　の正しいスケジュールを求める。 [証明] t = T に対するコアアルゴリズムの出力は、終了時刻が高々　　　　　　のスケジュール 　　　　　　　　　　　　　（補題10.7） よって終了時刻は高々

アルゴリズムの計算時間 制限されたビンパッキング問題に対する動的計画アルゴリズムの計算時間： コアアルゴリズムの計算時間： 異なる品物のサイズの数 k ： ２分探索の回数：　　　　　　回 これらを合わせると、計算時間は ただし、

おわり