任意の優先順位の下での関連機械スケジューリングの近似可能性について【JST・京大機械翻訳】

Aggarwal Vaneet; Lan Tian; Subramaniam Suresh; Xu Maotong

プレプリント

J-GLOBAL ID：202202219466420332 整理番号：21P0005594

任意の優先順位の下での関連機械スケジューリングの近似可能性について【JST・京大機械翻訳】

On the Approximability of Related Machine Scheduling under Arbitrary Precedence

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2017年11月27日プレプリントサーバーでの情報更新日： 2021年04月07日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

分散コンピューティングシステムは,ミッションクリティカルな目的を達成するために協調して作業しなければならない高度依存データ処理タスクの収集を含むスケジューリング問題を考慮する必要がある。本論文は,任意の先行制約の下で加重和完了時間を最小にするための無関係な機械スケジューリング問題と,異なる処理速度を有する不均一機械に関して考察した。この問題は,単一機械設定でも強いNP困難であることが知られている。Queyranneの制約集合を利用して,任意の先行制約の下でスケジューリング問題のために新しい線形プログラミング緩和を構築することによって,本論文における結果は,最先端技術を前進させた。ゼロ放出時間(および任意の放出時間)を有するスケジューリング問題のために,2(1+(m-1)/D)近似アルゴリズム(および2(1+(m-1)/D)+1近似)を開発し,そこでは,mはサーバの数であり,そして,Dはタスクスキューネス製品である。アルゴリズムは,Ellipsoid法を用いて多項式時間で効率的に計算でき,ジョブあたりのタスクの数が利用可能なマシンの数よりも十分に大きいとき,D>O(m)として実際に最適性能を達成した。不均一テストベッドと実世界ベンチマークを用いた実装と評価は,依存計算タスクに対する加重和完了時間の大幅な改善を確認した。【JST・京大機械翻訳】

, , , , , , , ,
, , , , 【Automatic Indexing@JST】

オペレーティングシステム , ディジタル計算機方式一般

, , ,

前のページに戻る