- 著者
-
齋藤 忠志
大谷 純
上土井 陽子
吉田 典可
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.99, no.724, pp.25-32, 2000-03-22
- 被引用文献数
-
2
オンラインに逐次発生するジョブをネットワーク上のどの資源に割り当てると効率良い処理が行えるかを考える負荷分散問題であるオンラインスケジューリング問題について考察する。Aspnesらにより8-competitive ratioをもつオンラインアルゴリズムSLOWFITが提案されている。理論的にはSLOWFITは効率の良い手法であるが、実験的には貪欲法GREEDYが良質な解を得ている。本稿ではSLOWFITに導入されているステージの概念とダブリング・トリックに注目して、新しい2つのオンラインスケジューリングアルゴリズムを提案する。シミュレーション実験により、提案手法の有効性を検証する。