オンライン負荷均衡問題における競合比の実験的考察

橋本 英樹

（指導教員：牧野　和久 准教授／数理情報第2研究室）

研究概要

複数のマシンに複数のジョブを割り当て，マシンの負荷を均衡させる負荷均衡問題を，ジョブが一つずつ与えられた都度割り当てるオンライン問題として考え，知られるアルゴリズムを実装して実験し，最適解とアルゴリズムの性能比である競合比の限界を考察した．

負べき数列マシン―負べき数列ジョブに対する各アルゴリズムの競合比

卒論の感想

よく似ているアルゴリズムが異なる性質を示したことに驚きました．似たような処理を何度も記述したり，計算量が予想外に多かったりと，計算を工夫する必要を感じました．