処理時間が調整可能かつ分割処理可能なジョブのスケジューリング問題に対する分割統治アプローチ
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,処理時間が調整可能かつ分割処理可能なジョブのスケジューリング問題を扱う.ここでは,処理機械は1機械,同一並列機械,一様並列機械という場合を考え,各ジョブの処理時間圧縮にかかる費用の総和の最小化を目的とする.本論文の目的はこれらのスケジューリング問題に対する分割統治アルゴリズムを提案することである.我々のアプローチであるが,本論文で扱うスケジューリング問題はポリマトロイド最適化問題として定式化できる,という観察に基づくものである.本論文では,一般のポリマトロイド最適化問題に対する新しい分割統治技法を開発し,それを各スケジューリング問題に適用する.提案する分割統治技法を用いたとき,各スケジューリング問題はO(T_<feas>(n)×log n)時間で解けることを示す.ここで,nはジョブの総数を,T_<feas>(n)はジョブの処理時間が固定されている状況で実行可能なスケジュールを求めるのに必要な時間を表す.このアプローチにより,本論文で扱うほとんどのスケジューリング問題に対してこれまでより高速なアルゴリズムを得ることができる.
- 社団法人電子情報通信学会の論文
- 2008-10-03
著者
-
塩浦 昭義
東北大学大学院情報科学研究科
-
塩浦 昭義
東北大学情報科学研究科
-
SHAKHLEVICH Natalia
School of Computing, University of Leeds
-
STRUSEVICH Vitaly
Department of Mathematical Sciences, University of Greenwich, Old Royal Naval College
-
Strusevich Vitaly
Department Of Mathematical Sciences University Of Greenwich Old Royal Naval College
-
Shakhlevich Natalia
School Of Computing University Of Leeds
関連論文
- 2次の効用関数に関する不可分財の最適配分問題の計算量について
- ヨーロピアンアジアンオプションの効率的な価格付けの手法 : AMOアルゴリズムの実装と解析の改良
- 2-A-10 処理時間が制御可能なジョブをもつスケジューリング問題に対する効率的なアルゴリズム(計算と最適化(2))
- 凸費用ネットワークフロー問題の双対に対する効率的なアルゴリズムとそのコンピュータビジョンへの応用
- アメリカン・アジアンオプションの価格の近似に対する計算幾何手法的アプローチ
- アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
- ヨーロピアン・アジアンオプションの価格付けに関する近似的解法
- Efficient Algorithms for Location Problems on Tree Networks
- Scaling Algorithms for M-convex Function Minimization (Mathematical Optimization Theory and its Algorithm)
- 近傍システム : アルゴリズムおよびジャンプシステムと双劣モジュラ多面体との関係
- 第14回RAMPシンポジウムルポ(情報の窓)
- A-019 2次の効用関数に関する不可分財の最適配分問題 : 計算複雑度とアルゴリズム(モデル・アルゴリズム・プログラミング,一般論文)
- 処理時間が調整可能かつ分割処理可能なジョブのスケジューリング問題に対する分割統治アプローチ
- 第1回 離散凸関数はどのような性質を満たすべきか : 離散最適化の視点から(離散最適化とその応用)
- M凸関数最小化に対する高速スケーリング算法と資源配分問題への応用
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- 多重グラフにおける均等辺彩色を求める高速アルゴリズム
- 2次の効用関数を持つ不可分財の最適配分問題に対する近似解法の研究 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 2次の効用関数に関する組合せオークションにおける最適配分問題のアルゴリズム
- 2-E-8 最小費用テンション問題に対する算法と画像処理への応用(離散最適化)
- 粗代替性をもつ効用関数の費用制約の下での最大化
- グラフの頂点価格付け問題に対する実用的近似解法 (アルゴリズムと計算理論の新展開)
- 離散凸解析から見たDijkstra法
- アドホックネットワークにおける貪欲幾何ルーティングアルゴリズムに対する統一的な手法