@techreport{oai:ipsj.ixsq.nii.ac.jp:02007442,
 author = {于,賢洋 and 森田,俊平 and 古谷,太一 and 後藤,義貴 and 加藤,淳也 and 金丸,朗},
 issue = {65},
 month = {Feb},
 note = {近年，ストリーム処理アプリケーションのクラウド集約が進んでいる．各ジョブをクラウド上の物理ノードへ割り当てる際には，CPUやメモリなどの資源に関する制約を満たしつつ収容アプリケーション数を最大化する必要があり，これは組合せ最適化問題として定式化される．焼きなまし法（Simulated Annealing; SA）はそのような組合せ最適化に対する代表的なメタヒューリスティックであり，問題規模が大きく厳密解の探索が実用的でない場合に広く用いられる．SAは，制約条件を満たさない（実行不可能な）解に対してペナルティを課して目的関数を最小化する「ペナルティ型SA」として，単独実行により探索を開始できるが大規模な問題では収束しにくい．一方，実運用では貪欲法などのヒューリスティック解法で得た制約を満たす割当を初期解としてSAで改善する枠組みも一般的であり，この場合は短時間で高品質な解を得やすい．しかし，初期解が実行不可能である場合には探索を開始できないことで実行可能解の獲得に至らず，SAを活用した割当効率（収容可能量）の改善につながらない．本研究では，他のヒューリスティック手法で得た実行不可能な初期解に対しても実行可能な解の探索を開始できる手法として，やり直し焼きなまし法（Redo-SA）を提案する．Redo-SAは，（i）問題を縮約してヒューリスティック解法とその後のSAにより実行可能解を求めることで土台を構成し，（ii）除外要素を貪欲法および強制的に挿入して一時的に容量違反を許容した上で，（iii）ペナルティ型SAを用いて割当を再度おこなうことで容量違反を優先的に解消し，実行可能な解を獲得する手法である．提案手法の実験に際し，クラウド環境を想定した1000台の物理ノードからなるジョブ配置問題を対象に，貪欲法を初期解としたRedo-SAを，貪欲法のみ，および初期解なしのペナルティ型SAと比較した．その結果，貪欲法やその後のSAで得られる収容可能アプリケーション数を100%としたとき，初期解なしのペナルティ型SAは約85%に留まった一方で，Redo-SAは115-120%まで収容可能であることを確認した．これは，Redo-SAなしで同一条件の割当を行った場合と比べて，収容に必要なノード数を150台以上削減できることを意味し，実運用では無視できない差となり得る．},
 title = {クラウドジョブ配置の資源超過を解消するやり直し焼きなまし法},
 year = {2026}
}