データセンタの持続可能な運用のための多目的最適化手法の開発
代表研究者

鮫島 正樹

大阪大学 大学院情報科学研究科 マルチメディア工学専攻 助教

1 はじめにクラウドコンピューティングの普及に伴い，科学計算のための High-Performance Computing (HPC)のクラウドへの移行が進んでいる[1,2]．ユーザがクラウド上の HPC にジョブを送信すると，データセ
ンタの HPC サーバによってジョブは処理される．クラウド上の HPC を利用する利点として，ユーザはサーバを購入することなく利用できるため，一般的にコストを低く抑えることができる．また，HPC サー
ビスの提供者にとっては，サーバをデータセンタに集約できるため，空調や電力といったランニングコ
ストを抑えることができるという利点がある．しかし，データセンタにおけるサーバの収容能力には限りがあるため，複数のデータセンタに分散し，それらを高速のネットワークで接続することが行われている．本研究では，このような分散データセンタを研究対象とする．
分散データセンタは，分散に伴って追加の電力を必要とするため，その電力を安価に確保することが重要となる．近年のデータセンタは，屋根に太陽光発電システムを搭載するなど，データセンタ自体に発電の機能が備えられている．得られた電力をデータセンタの運用に利用することで，外部から調達する電力を低減することができる[3]．データセンタにおいては，ジョブを処理する際に HPC サーバが稼働し，より多くの電力を消費することから，発電量が多い時間帯(一般的に昼間)にジョブを処理することが，調達電力量の低減に有効である．一方，ユーザはジョブに対して，ジョブの処理が完了すべき時
刻(完了希望時刻)を与えており，なるべく完了希望時刻内に処理を終えることが望ましい．調達電力量の低減のみを考慮して，すべてのジョブを昼間に処理するようなジョブスケジュールでは，完了希望時
刻以内にジョブを完了できず，完了希望時刻からの遅延時間を生じてしまう．従って，調達電力量と遅延時間の双方を最小化する多目的ジョブスケジューリング問題を解くことが求められている[4]．
調達電力量と遅延時間の双方を最小化するジョブスケジューリング問題について，様々なアルゴリズ
ムが提案されている．ヒューリスティックな方法として，完了希望時刻までの猶予時間が短いジョブから順に，調達電力量を最小化するようにジョブスケジュールを作成する GreenSlot[5]とよばれるアル
ゴリズムが提案されている．また，より良いジョブスケジュールを決定するため，多目的整数計画問題に定式化して解く方法も提案されている．多目的整数計画問題を解くためには膨大な計算時間が必要であり，近似解法として進化的アルゴリズム等のメタヒューリスティクス[6,7,8]が用いられている．これらのアルゴリズムでは，データセンタにおける発電量の予測誤差を考慮せず，スケジューリングを行っている．
本研究では，調達電力量と遅延時間の双方を最小化するジョブスケジューリング問題において，発電量の予測誤差を考慮した定式化を行い，多目的最適化のための効率的なアルゴリズムを提案する．具体
的には，発電量を確率変数で表現し，機会制約条件を定式化に導入する．さらに，多目的最適化問題の厳密解法である Epsilon-constraint 法[9]にもとづいて，効率的な最適化手法を提案する．

2 関連研究データセンタにおける調達電力を最小化するジョブスケジューリング手法に関して，これまで多くの研究が行われている．その一つのアプローチとして，利用しないサーバを停止することにより，消費電力を低減する方法がある[10,11]．サーバを停止すると，その間の消費電力を大幅に低減できる代わりに，ジョブを処理することができなくなってしまう．多数のジョブを処理するために，停止したサーバを再度起動すると，起動時に多くの消費電力を必要とする．従って，再起動の回数をなるべく抑え，サーバの停止期間を長期化するようなスケジュールを作成することが，消費電力の低減に有効である．もう一つのアプローチとして，データセンタにおける再生可能エネルギーを利用することで，外部に調達する電力を削減する手法があり，本研究ではこちらに着目する．
再生可能エネルギーの利用を考慮した初期のスケジューリング手法として，GreenSlot[5]とよばれるヒューリスティックな手法が提案されている．GreenSlot では以下のようにジョブのスケジューリング
を行う．

1（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

1.

余裕時間が小さいジョブから順に高い優先度を与える．余裕時間は，完了希望時刻までの時間
から処理時間を引いた時間である．
2.
優先度の高いジョブから順に選択し，そのジョブを処理するのに十分な CPU コアを有するデータセンタを列挙する．調達電力が最小となるような時間とデータセンタを選択して，ジョブを割り当てる．
また，同様のスケジューリング問題を混合整数計画問題に定式化し，最適解を求める研究もなされている[12]．これらの研究では，ジョブの処理時間は十分に短く，遅延時間が生じないということを仮定
し，調達電力量のみを最小化することを目的としている．この仮定によって，スケジューリング問題を各時間におけるジョブの割り当て問題に分解することができ，短時間で最適解が求まることを示している．また，発電量の不確実性を考慮して，発電量を確率変数で表現し，定式化に組み込む研究も報告されている．発電量の期待値を最小化するように定式化し，Lyapunov 最適化を用いた解法が提案されている[13,14]．
上記の問題は単一目的の最適化問題として定式化されているが，調達電力量や遅延時間等を目的関数
として，多目的最適化問題として解く研究も報告されている．多目的最適化問題は，単一目的の最適化問題よりも，求解に多くの時間を要する．そのため，進化計算等のメタヒューリスティクスを利用した近似アルゴリズムが提案されている[6,7,8]．
上述したように，再生可能エネルギーを利用したジョブスケジューリング問題に関して，確率的最適化もしくは多目的最適化を行う研究はすでに行われている．本研究では，これらを同時に扱う確率的多目的最適化問題として定式化し，解くことを目的とする．加えて，既存の定式化では確率変数を含む式
を期待値で評価していたが，実際の運用においては悲観的なスケジュールを採用することが多いことに着目する．例えば，スケジュールで利用予定の電力量が実際の発電量を超えると再スケジューリングが必要となることから，このような状況を平均的に回避するというより，むしろ高い確率で回避したい．
このような制約条件は機会制約条件と呼ばれ，その評価に多くの計算時間を要する．本研究では，多目的であり機会制約条件を含むジョブスケジューリング問題に対して，効率的なアルゴリズムを提案する．
3 調達電力量と遅延時間に関する多目的ジョブスケジューリング問題
3-1 問題の定式化
本研究で対象とする分散データセンタのモデルについて図 1 に示す．各データセンタは，太陽光発電
システムによる発電が可能であり，また，地理的に離れた場所に設置されている．データセンタには，
複数のサーバが設置されており，ジョブの処理に利用される CPU コアの数はサーバによって異なってい
る．図１の下部に示すように，ユーザが送信したジョブは各データセンタに割り振られ，CPU コアによって処理するスケジュールが作成される．ジョブを処理するためには，ジョブが要求する CPU コア数以上の CPU コアが，データセンタにおいて利用可能でなければならない．また，ユーザに指定された完了
希望時刻以内にジョブを処理する必要があり，完了希望時刻を超えた遅延時間を最小にする必要がある．
さらに，太陽光発電によって得られた電力を，ジョブの処理に活用することで，調達電力量を最小にすることも必要となる．

図 1 分散データセンタモデル

2（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

そこで，遅延時間と調達電力量を最小にするためのジョブスケジューリング問題を，多目的最適化問
題として定式化する．表１に示す決定変数ならびに表 2 に示すパラメータを用いた，本問題の定式化について以下に示す．
𝐽𝐽

min. 𝑓𝑓1 = � 𝑣𝑣𝑗𝑗
𝑗𝑗=1
𝐽𝐽 𝐾𝐾

(1)

𝑇𝑇

min. 𝑓𝑓2 = � � ��𝑝𝑝𝑗𝑗 − 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 �𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗
s. t.

𝐽𝐽

𝑗𝑗=1 𝑘𝑘=1 𝑡𝑡=1

� 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 ≤ 𝐺𝐺𝑘𝑘𝑘𝑘

(3)

𝑗𝑗=1

𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 ≤ 𝑃𝑃𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗

(4)

𝐽𝐽

� 𝑅𝑅𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 ≤ 𝐹𝐹𝑘𝑘𝑘𝑘

(5)

𝑗𝑗=1
𝐾𝐾 𝑇𝑇

� � 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 𝐿𝐿𝑗𝑗

(6)

𝑘𝑘=1 𝑡𝑡=1
𝜏𝜏+𝐿𝐿𝑗𝑗

� 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 ≥ 𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗 𝐿𝐿𝑗𝑗 ,1 ≤ 𝜏𝜏 ≤ 𝑇𝑇 − 𝐿𝐿𝑗𝑗

𝑡𝑡=𝜏𝜏

𝑣𝑣𝑗𝑗 ≥ 𝑡𝑡𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗 + 𝐿𝐿𝑗𝑗 − 1 − 𝑑𝑑𝑗𝑗
𝑣𝑣𝑗𝑗 ≥ 0, 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 ≥ 0
𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗 ∈ {0,1}記号
𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗
𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗
𝑣𝑣𝑗𝑗
𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗
記号𝑝𝑝𝑗𝑗
𝐺𝐺𝑘𝑘𝑘𝑘𝑅𝑅𝑗𝑗
𝐹𝐹𝑘𝑘𝑘𝑘
𝐿𝐿𝑗𝑗
𝑑𝑑𝑗𝑗

(2)

(7)
(8)
(9)

(10)

表 1 決定変数
説明
ジョブ𝑗𝑗を時刻𝑡𝑡においてデータセンタ𝑘𝑘で処理するとき𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 1
時刻𝑡𝑡，データセンタ𝑘𝑘におけるジョブ𝑗𝑗の処理に割り当てる電力量
ジョブ𝑗𝑗の完了希望時刻からの遅延時間
ジョブ𝑗𝑗の処理が，時刻𝑡𝑡，データセンタ𝑘𝑘ではじまるとき𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗 = 1
表 2 パラメータ
説明
ジョブ𝑗𝑗が単位時間に消費する電力量
時刻𝑡𝑡，データセンタ𝑘𝑘において，太陽光発電で得られた電力量
ジョブ𝑗𝑗に必要な CPU コア数
時刻𝑡𝑡，データセンタ𝑘𝑘において利用可能な CPU コア数
ジョブ𝑗𝑗の処理時間
ジョブ𝑗𝑗の完了希望時刻

式(1)はジョブ𝑗𝑗の遅延時間𝑣𝑣𝑗𝑗 の総和を最小化する一つ目の目的関数であり，式(2)は各ジョブに必要な調達電力量(𝑝𝑝𝑗𝑗 − 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 )の総和を最小化する二つ目の目的関数である．遅延時間𝑣𝑣𝑗𝑗 は，式(8)において，ジョブの開始を表す𝑧𝑧𝑗𝑗𝑗𝑗𝑗𝑗 ，処理時間𝐿𝐿𝑗𝑗 ，完了希望時刻𝑑𝑑𝑗𝑗 によって定まる．式(3)は，割り当てられる電力量𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 の総量が発電量𝐺𝐺𝑘𝑘𝑘𝑘 以下であること表す．式(4)は，ジョブ𝑗𝑗が必要とする以上の電力量を割り当てることができないことを表す．式(5)は，ジョブが使用する CPU コア数が利用可能な CPU コア数以下であることを表す．式(6), (7)は，CPU コアに割り当てられたジョブは中断できないことを表す．
3-2 パレート最適化
本問題は多目的最適化問題であるが，トレードオフの関係にある二つの目的関数を同時に最小化する解は存在しない可能性が高い．このため，二つの目的関数の値が他のいずれの解にも劣らないような解3（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

(パレート解)を発見することを本研究の目的とする．最小化問題において，解𝑋𝑋1がパレート最適であるということは，任意の解𝑋𝑋2と以下に示す関係が成り立つ必要がある．
𝑓𝑓 (𝑋𝑋 ) ≤ 𝑓𝑓𝑢𝑢 (𝑋𝑋2 ) ∀𝑢𝑢 (∈ {1, … , 𝑈𝑈})
X1 ≼ X 2 ⟺ � 𝑢𝑢 1
∃𝑣𝑣 (∈ {1, … , 𝑈𝑈}) 𝑓𝑓𝑣𝑣 (𝑋𝑋1 ) < 𝑓𝑓𝑣𝑣 (𝑋𝑋2 )多目的最適化問題を直接的に解くことは困難であるため，これまでヒューリスティクスにもとづく近似
解法や，単一目的最適化問題に分解して解く方法が提案されている．本研究では，単一目的最適化問題に分解することで厳密解を求める Epsilon-constraint 法を適用する．
Epsilon-constraint 法では，ある目的関数以外を制約条件に置き換えることで単一目的最適化問題に変換し，これを繰り返し解くことによってパレート最適解を得る．本問題においては，式(2)の目的関数を以下の制約条件に置き換える．
𝐽𝐽

𝐾𝐾

𝑇𝑇

𝑓𝑓2 = � � ��𝑝𝑝𝑗𝑗 − 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 �𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 < 𝜖𝜖𝑗𝑗=1 𝑘𝑘=1 𝑡𝑡=1(2)′

パラメータ𝜖𝜖の初期値は非常に大きな値とすることで，最初の単一目的最適化問題の解として，遅延時間を最小化するような解を得ることができる．その解に対する調達電力量𝑓𝑓2 を次の𝜖𝜖として，再度，単一目的最適化問題を解くと，初期解と比較して，調達電力量が小さく遅延時間の大きい解を得ることができる．この手順を実行可能解が得られなくなるまで繰り返し，実行可能解からパレート最適解を得ることができる．
3-3 研究課題
前節で述べた Epsilon-constraint 法によるパレート最適化を適用する際の課題について述べる．
(1) 発電量に不確実性が存在する．
本問題における発電量𝐺𝐺𝑘𝑘𝑘𝑘 は計画段階の予測値であり不確実性を伴う．そこで，𝐺𝐺𝑘𝑘𝑘𝑘 の予測値が正規分布に従う確率変数として扱う．𝐺𝐺𝑘𝑘𝑘𝑘 が確率変数であるとき，解を一意に定めることができないた
め，𝐺𝐺𝑘𝑘𝑘𝑘 を含む式(3)を以下のような機会制約条件に変換して解く．
𝐽𝐽

Pr �� 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 ≤ 𝐺𝐺𝑘𝑘𝑘𝑘 � ≥ α
𝑗𝑗=1

(3)′

Pr[⋅]は不等式を満たす確率を示す関数であり，𝛼𝛼はその確率の下限値である．しかし，上記の制約条件を評価するためには，𝐺𝐺𝑘𝑘𝑘𝑘 からのサンプリングを伴うため，計算時間を要する．
(2) 整数計画問題に整数条件以外の非凸項が含まれる．
整数計画問題自体は非凸な整数条件を含むため，整数条件を連続条件に緩和した凸計画問題から下界値を得て，Branch-and-Cut 法を適用することが主要な解法となっている．しかし，本問題では非凸項𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 を含んでいるため，整数条件を緩和しても非凸な計画問題であり，解くことが困難である．
(3) パレート最適解の探索効率が低い．
Epsilon-constraint 法は多目的最適化問題の効率的なアルゴリズムとして知られているが，パレート最適解ではなく，弱パレート最適解を導く問題を解いてしまうことがある． 弱パレート最適解とは，パレート最適解と比較して，ある目的関数において劣る解を指す．2 目的最適化問題に
Epsilon-constraint 法を適用した場合の，解の評価値の分布を図 2 に示す．
図 2 に示すように，Epsilon-constraint 法では，パレート最適解を得るまでに，弱パレート最適解を導く問題を多数解いているため非効率である．そこで，パレート最適解のみを導く問題を解く
ようにすることでアルゴリズムを効率化する．

4（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

62

消費電力

61

パレート最適解60

弱パレート最適解

59
58
57
56
55
54

0

2

4

6

8

10

12

遅延時間

図 2 Epsilon-constraint 法によって得られた解の評価値分布

4 機会制約条件つき多目的最適化アルゴリズム
4-1 アプローチ
前節で述べた課題に対して以下の方法を提案する．
(1) 機会制約条件の緩和
機会制約条件については，決定性の制約条件に緩和する方法が知られており，本研究では Sample
Average Approximation 法(SAA)[15]を適用する．SAA によって機会制約条件(3)’は以下の制約条件に置き換えられる．
𝐽𝐽� 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 − 𝐺𝐺𝑘𝑘𝑘𝑘 ≤ 𝑤𝑤𝑠𝑠 𝜋𝜋 (∀𝑠𝑠 ∈ {1, … , 𝑆𝑆})
𝑗𝑗=1

𝑆𝑆

� 𝑤𝑤𝑠𝑠 ≤ 𝑆𝑆(1 − 𝛼𝛼)
𝑠𝑠=1

𝑤𝑤𝑠𝑠 ∈ {0,1}𝜋𝜋は非常に大きな値とする．𝑤𝑤𝑠𝑠 は元の制約条件(3)を満足するかどうかを 0 または 1 で表す決定変数である．𝑤𝑤𝑠𝑠 = 0であれば元の制約条件を満たすが，𝑤𝑤𝑠𝑠 = 1であれば満たさない．𝑤𝑤𝑠𝑠 の総和，すなわち制約条件を満たさない回数が𝑆𝑆(1 − 𝛼𝛼)以下になるような𝑤𝑤𝑠𝑠 を決定する．𝑆𝑆は緩和した制約条件の評価回数であり，大きいほど元の機会制約条件の良い近似となる．
決定変数𝑤𝑤𝑠𝑠 の導入により問題の規模が拡大するものの，この制約条件は整数条件を除けば線形であり，主要な整数計画法である Branch-and-Cut 法[16]の適用対象となる．
(2) 非凸項の置換
非凸項である𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 に対して𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 とおくと
𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 = �

𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗
0(𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 1)
(𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 0)となり𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 は離散変数となる．離散条件を緩和して，𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 を0 ≤ 𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 ≤ 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 を満たす連続変数に変換すると，線形緩和問題を得られるため，Branch-and-Cut 法によって元の整数計画問題を解くことができる．得られた𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 にもとづいて𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 を以下のように決定する．
5（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

1 (𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 > 0)
𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = �
0 (𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 = 0)

(3) 弱パレート最適解の排除
制約条件(2)’から弱パレート最適解を導いてしまう原因として，微小な𝜖𝜖の更新を許してしまうことが挙げられる．そこで，𝜖𝜖の更新をなるべく大きくするような Augmented Epsilon-constraint
法[17]を適用する．Augmented Epsilon-constraint 法では，原問題の𝑓𝑓1 , 𝑓𝑓2 に関する目的関数ならびに制約条件(2)’を以下のように変形する．
min 𝑓𝑓1 − 𝜌𝜌𝜌𝜌s. t. 𝑓𝑓2 + 𝑠𝑠 = 𝜀𝜀

決定変数𝑠𝑠(> 0)は𝑓𝑓2 の改善度を表すスラック変数であり，これを目的関数に含めることで，なるべ
く大きな𝑠𝑠を決定することができる．𝑠𝑠が大きくなるにつれて，𝜀𝜀の更新幅を大きくすることができる．また，𝜌𝜌𝜌𝜌が𝑓𝑓1 に対して十分に小さくなるように𝜌𝜌(> 0)を設定すれば，パレート最適解を求める
ことができる．
4-2 アルゴリズム
アルゴリズムの疑似コードを Algorithm 1 に示す．また疑似コード中の各関数について以下で述べる．
Algorithm 1 多目的最適化の疑似コード
Input: パラメータ集合 𝒫𝒫 ← �𝑝𝑝𝑗𝑗 , 𝐺𝐺𝑘𝑘𝑘𝑘 , 𝑅𝑅𝑗𝑗 𝐹𝐹𝑘𝑘𝑘𝑘 , 𝐿𝐿𝑗𝑗 , 𝑑𝑑𝑗𝑗 �, ∀𝑗𝑗, 𝑘𝑘, 𝑡𝑡 ∈ ℕ
Output: パレート最適解の集合𝛬𝛬 ∋ �𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 �, ∀i ∈ ℕ
1: Initialize: 𝑖𝑖 = 1, 𝛬𝛬 = {∅}, 𝜖𝜖 ← +∞2: while true do3:𝑃𝑃𝜖𝜖 ←Generate_P(𝒫𝒫, ϵ)4:
if 𝑃𝑃𝜖𝜖 is feasible then5:
𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 ←Branch_and_Cut(𝑃𝑃𝜖𝜖 )6:
if 𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 >0 then
7:
𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 1
8:
else
9:
𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 0
10:
end if11:
𝛬𝛬 ← 𝛬𝛬 ∪ �𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 �12:𝜖𝜖 ← 𝑓𝑓2 (𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 )
13:
else
14:
break
15:
end if
16: end while
17: return 𝛬𝛬Generate_P(𝒫𝒫, ϵ)
パラメータ𝒫𝒫とϵから Augmented Epsilon-constraint 法と SAA 法を適用した問題𝑃𝑃𝜖𝜖 を生成する．
Branch_and_Cut(𝑃𝑃𝜖𝜖 )問題𝑃𝑃𝜖𝜖 に対して Branch-and-Cut 法を適用し，解𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 , 𝑔𝑔𝑗𝑗𝑗𝑗𝑗𝑗 を出力する．
Algorithm 1 に示すように，本アルゴリズムではϵを更新しながら問題𝑃𝑃𝜖𝜖 を生成し，𝑃𝑃𝜖𝜖 が実行不可能となるまで𝑃𝑃𝜖𝜖 を解いて，パレート最適解を集合𝛬𝛬に保存する．𝑦𝑦𝑗𝑗𝑗𝑗𝑗𝑗 から𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 を求めたのち𝑓𝑓2 の値を求め，𝜖𝜖を新しい𝑓𝑓2 で更新する．
6（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

5 評価実験
5-1 実験の概要
日本の 5 地点(札幌，東京，長野，大阪，福岡)にデータセンタが分散していると想定し，実際に HPC
サーバへ送信されたジョブを対象として実験を行った．各地点の 2016 年 8 月 4 日の 0 時から 8 時までの日照量𝐼𝐼𝑘𝑘𝑘𝑘 [0.01MJ/m2]を用いて[18]，各データセンタの発電量𝐺𝐺𝑘𝑘𝑘𝑘 [kWh]の予測値𝐺𝐺�𝑘𝑘𝑘𝑘 を以下の式で計算した．予測値𝐺𝐺�𝑘𝑘𝑘𝑘 を図 3 に示す．
𝐺𝐺�𝑘𝑘𝑘𝑘 = 0.7 × 0.002778 × 5 × 𝐼𝐼𝑘𝑘𝑘𝑘

上式において，変換ロスを考慮した係数を 0.7，MJ から kWh への変換係数を 0.002778，太陽光パネルの出力が 5kW(=250W を 20 枚)と想定している．図 3 に示すように，4 時ごろより一部の地域で発電がみられ，曇天であった大阪や福岡の発電量は晴天の他地域に比べて少なくなっている．スケジュール作成時には，予測値𝐺𝐺�𝑘𝑘𝑘𝑘 のみがわかっているとし，実測値𝐺𝐺𝑘𝑘𝑘𝑘 は以下の正規分布に従うと仮定した．ただし，正規分布からのサンプリング値が負になるときは 0 として扱っている．
𝐺𝐺𝑘𝑘𝑘𝑘 ~𝑁𝑁(𝐺𝐺�𝑘𝑘𝑘𝑘 , 0.1)

発電量[kWh]
2.0

札幌

東京

長野

大阪

福岡

5

6

1.5
1.0
0.5
0.0

0

1

2

3

4

7

時刻

図 3 各地点の発電量の予測値
また，実際のデータセンタにおいて，8 時間に要求されるジョブ数の分布を調査し，平均数 15 と 90 パ
ーセンタイル値 20 をジョブ数として，スケジューリングを行った．表 3 に実験に用いたジョブの必要
コア数，処理時間を示す．なお，各ジョブの完了希望時刻は処理時間と同じ値に設定した．データセン
タには，これらのジョブを処理するのに十分な CPU コアが備えられているものの，CPU コアにはすでにジョブの処理が割り当てられており，全ての CPU コアを利用できるわけではない．本実験では，各デー
タセンタにおいて利用可能な CPU コア数を表 4 に示すとおりとした．また，CPU コアがジョブを処理する際の電力は 20[W]とした．
提案手法ならびに比較手法としての Epsilon-constraint 法を，最適化ソフトウェアの Gurobi を用いて python で実装した．実験に利用した計算機の仕様は，OS が CentOS 7.2，CPU が 2×Intel Xeon CPU
E5-2650 V4@2.20GHz，メモリが 8×8GB である．Epsilon 制約である𝑓𝑓2 < 𝜀𝜀を計算機で評価することは困難なので，近似的に𝑓𝑓2 ≤ 𝜀𝜀 − 𝜎𝜎と置き換える．パラメータ𝜎𝜎に設定する値が小さいほど，精度よくパレート最適解を求めることができるが，ε −制約法による𝑓𝑓2 の改善が小さくなり，より多くの計算時間を必要とする．本実験では𝜎𝜎 = 0.01を用い，その他のパラメータについては，α = 0.9, S = 50, ρ = 0.01を用いた．
5-2 実験結果
各手法を適用した際の遅延時間と調達電力量の分布について，ジョブ数が 15 の場合の結果を図 4 に，ジョブ数が 20 の場合の結果を図 5 に示す．また，各手法による計算時間の比較を表 5 に示す．

7（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

表 3 スケジューリング対象のジョブ(a) ジョブ数 15(b)ジョブ数 20
CPU コア数 処理時間
CPU コア数 処理時間
8
8
4
#1
4
#1
128
128
4
#2
4
#2
8
8
8
#3
8
#3
16
16
4
#4
4
#4
16
16
6
#5
6
#5
16
16
6
#6
6
#6
16
16
4
#7
4
#7
16
16
4
#8
4
#8
16
16
4
#9
4
#9
16
16
4
#10
4
#10
16
16
6
#11
6
#11
64
64
4
#12
4
#12
8
8
4
#13
4
#13
256
256
6
#14
6
#14
8
8
4
#15
4
#15
8
4
#16
8
4
#17
8
4
#18
8
4
#19
8
6
#20

表 4 各データセンタの利用可能な CPU コア数
札幌
東京
長野
大阪
利用可能な CPU コア数 128
256
128
64

Epsilon-constraint法
62

福岡
64

Augmented Epsilon-constraint法

調達電力量[kWh]62

調達電力量[kWh]61

パレート最適解61

パレート最適解60

弱パレート最適解60

弱パレート最適解

59

59

58

58

57

57

56

56

55

55

54

0

1

2

3

4

5

6

7

8

9

10

54

11

遅延時間

0

1

2

3

4

5

6

遅延時間

7

8

9

10

11

図 4 解の評価値分布(ジョブ数 15)8（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

Epsilon-constraint法
66

Augmented Epsilon-constraint法

調達電力量[kWh]

66

65
64

パレート最適解65

パレート最適解

弱パレート最適解64

弱パレート最適解

63

63

62

62

61

61

60

60

59

59

58

58
0

1

2

3

4

5

調達電力量[kWh]

6

7

8

9

10

11

0

1

2

3

遅延時間

4

5

6

7

8

9

10

11

遅延時間

図 5 解の評価値分布(ジョブ数 20)
表 5 各手法の計算時間
Epsilon-constraint 法
Augmented Epsilon-constraint 法

15 ジョブ3 時間 56 分 48 秒
2 時間 36 分 55 秒

20 ジョブ
8 日 1 時間 7 分 7 秒
15 時間 36 分 8 秒

図 4，図 5 に示す結果から，Augmented Epsilon-constraint 法を用いることによって，弱パレート最適解を求めることなく，パレート最適解を求めることができている．結果として，表 5 に示すように計算時間が短縮されている．特に 20 ジョブを対象としたスケジューリング問題の場合，Epsilonconstraint 法では 8 日以上必要であるが，Augmented Epsilon-constraint 法では 15 時間まで短縮できている．
ジョブ数 15 と 20 の場合をそれぞれ比較すると，ジョブ数が 20 の方がより多くの CPU コアを利用することから，調達電力量ならびに遅延時間が大きくなっている．またジョブ数が 15 の場合，遅延時間
が 10 のスケジュールの調達電力量は，遅延時間が 0 のスケジュールと比較して約 4kWh 小さい．一方，
ジョブ数が 20 の場合，遅延時間が 10 のスケジュールの調達電力量は，遅延時間が 3 のスケジュールと比較して約 3kWh 小さい．従って，ジョブ数が多い場合，仮に遅延時間の増加を許したとしても，調達
電力量を十分に低減できない可能性がある．また，ジョブ数 15 と 20 の問題の双方において，遅延時間
を 10 より大きくしても，調達電力量の小さいスケジュールを得ることはできなかった．これらの原因として，データセンタにおける発電量に限りがあるため，発電量をほとんど使い切ってしまうことが挙げられる．
提案方式によって，遅延時間や調達電力量のいずれかを最小化するスケジュールだけではなく，双方を考慮したスケジュールを求めることができた．データセンタの管理者は，提案方式を用いて得られたパレート最適解を閲覧し，現状に適したパレート最適解を選択できる．いずれのジョブ数の問題においてもパレート最適解の数は 10 であり，データセンタの管理者が個々の解を評価可能な数であることを
確認した．

6 結論
本研究では，再生可能エネルギーを活用して，調達電力量と遅延時間を最小化するジョブスケジューリング問題を対象とした．不確実な発電量を確率変数で表現し，機会制約条件を含む多目的最適化問題
として，ジョブスケジューリング問題を定式化した．大規模な問題であるため，既存の多目的最適化手

9（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

法である Epsilon-constraint 法をそのまま適用した場合，スケジューリングに多大な計算時間を要してしまう課題があった．そこで，機会制約条件に対する SAA 法による近似，非凸項の変数変換，Augmented
Epsilon-constraint 法による効率化を図り，スケジューリングに要する時間を削減する方法を提案した．データセンタにおける実際の発電量を想定して，ジョブ数 15 ならびに 20 のスケジューリング問題を作成し，既存の Epsilon-constraint 法と Augmented Epsilon-constraint 法を適用した．実験の結果，Augmented Epsilon-constraint 法によってパレート最適解を正しく求めつつ，計算時間を削減できることを確認した．特に，ジョブ数が多い場合において，計算時間を大きく削減できていた．パレート
最適解を求めることで，遅延時間や調達電力量のいずれかを最小化するスケジュールだけではなく，双方を考慮したスケジュールを，データセンタの管理者に選択肢として提示することができた．
今後の課題として，多目的最適化手法のさらなる高速化を図る必要がある．本研究では，機会制約条件を SAA 法によって近似したが，正規分布のパーセンタイル値を用いることで，よりコンパクトな近似が可能となり計算時間をさらに削減できると考えている．また，発電量が昼間にピークを迎えるといった時系列的な傾向をアルゴリズムに反映させることで，高速化できると考えられる．例えば，ピークを過ぎると発電量が減少するだけでなく，遅い時間にジョブを割り当てることで遅延時間も増加してしまう．このため，時間帯によっては遅い時間にジョブを処理する利点が失われ，そのような割り当てを行うスケジュールを解の候補から除外できる可能性がある．このような性質を踏まえたヒューリスティッ
クな解法を作成し，その解を暫定解とすることで，Branch-and-Cut 法の性能を向上できると考えられる．

【参考文献】[1] J. J. Rehr, F. D. Vila, J. P. Gardner, L. Svec, M. Prange. Scientific computing in the cloud.
Computing in Science Engineering, Vol.12, No.3, pp.34-43, 2010.
[2] S. Srirama, O. Batrashev, E. Vainikko. SciCloud: Scientific computing on the cloud. In

Proceedings of the IEEE/ACM International Conference on Cluster, Cloud and Grid
Computing, pp.579–580, 2010.

[3] K. K. Nguyen, M. Cheriet, M. Lemay, M. Savoie, B. Ho. Powering a Data Center Network via
Renewable Energy: A Green Testbed. IEEE Internet Computing, Vol.17, No.1, pp.40-49, 2013.
[4] X. Tang, C. Chen, B. He. Green-aware Workload Scheduling in Geographically Distributed
Data Centers. In Proceedings of IEEE 4th International Conference on Cloud Computing
Technology and Science, pp.82-89, 2012.
[5] I. Goiri, R. Beauchea, K. Le, T. D. Nguyen, M. E. Haque, J. Guitart, J. Torres, R. Bianchini.
Greenslot: Scheduling energy consumption in green datacenters. In Proceedings ofInternational Conference for High Performance Computing, Networking, Storage andAnalysis, pp.1-11, 2011.

[6] S. Iturriaga, S. Nesmachnow. Scheduling energy efficient data centers using renewableenergy. Electronics, Vol.5, No.4. Article No.71, 2016.
[7] H. Lei, R. Wang, T. Zhang, Y. Liu, Y. Zha. A multi-objective co-evolutionary algorithm forenergy-efficient scheduling on a green data center. Computers & Operations Research, Vol.75,
pp.103-117, 2016.
[8] A.-A. Tantar, G. Danoy, P. Bouvry, S. U. Khan. Energy-Efficient Computing Using AgentBased Multi-objective Dynamic Optimization. Green IT: Technologies and Applications,pp.267–287, 2011.
[9] D. T. Luc, S. Schaible. Efficiency and Generalized Concavity. Journal of Optimization Theory
and Applications, Vol.94, No.1, pp.147-153, 1997.
[10] O. Mämmelä, M. Majanen, R. Basmadjian, H. De Meer, A. Giesler, W. Homberg. Energyaware job scheduler for high-performance computing, Computer Science - Research andDevelopment, Vol.27, No.4, pp.265-275, 2012.
[11] K. Sato, M. Samejima, N. Komoda. Dynamic optimization of virtual machine placement by
resource usage prediction. In Proceedings of IEEE International Conference on Industrial
Informatics, pp. 86–91, 2013.

10（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

[12] C. Gu, Z. Li, C. Liu, H. Huang. Planning for green cloud data centers using sustainableenergy. In Proceedings of IEEE Symposium on Computers and Communication, pp. 804–809,
2016.
[13] L. Yu, T. Jiang, Y. Cao, Q. Qi. Joint workload and battery scheduling with heterogeneous
service delay guarantees for data center energy cost minimization. IEEE Transactions on
Parallel and Distributed Systems. Vol.26, No.7, pp.1937–1947, 2015.
[14] Y. Guo, Y. Gong, Y. Fang, P. P. Khargonekar, X. Geng. Energy and network aware workload
management for sustainable data centers with thermal storage. IEEE Transactions on
Parallel and Distributed Systems. Vol.25, No.8, pp.2030–2042, 2014.
[15] B.K. Pagnoncelli, S Ahmed, A Shapiro. Sample average approximation method for chanceconstrained programming: theory and applications. Journal of optimization theory andapplications, Vol.142, No.2, pp.399-416, 2009.
[16] B. Korte, J. Vygen. Combinatorial Optimization Theory and Algorithms. Springer, 2012.
[17] G. Mavrotas. Effective implementation of the 𝜀𝜀 −constraint method in multi-objective
mathematical programming problems, Applied Mathematics and Computation, Vol.213, No.2,
pp.455–465, 2009.
[18] NEDO 日照量データベース, http://app0.infoc.nedo.go.jp/metpv/metpv.html (Accessed on
2017/6/30).

〈発 表 資 料〉
題

名掲載誌・学会名等

Epsilon Constraint 法を用いた
電気学会 情報システム研
分散データセンタにおけるジョブ 究会, IS-16-008, pp. 41スケジューリング
46
IIAI
International
ModelingGreen-aware
Job
CongressonAdvanced
Scheduling
ProbleminAppliedInformatics,
Decentralized Data Centers
pp.1093-1096

発表年月2016 年 5 月 17 日

2016 年 7 月 11 日

11（公財）電気通信普及財団 研究調査助成報告書 No.32 2017