文献

J-GLOBAL ID：202002236889114063   整理番号：20A1891010

オンラインスループット最大化におけるコミットメント処理のための一般的フレームワーク【JST・京大機械翻訳】

A general framework for handling commitment in online throughput maximization

著者 (5件)： Chen Lin (Department of Computer Science, Texas Tech University, Lubbock, TX, USA) ,  Eberle Franziska (Department for Mathematics and Computer Science, University of Bremen, Bremen, Germany) ,  Megow Nicole (Department for Mathematics and Computer Science, University of Bremen, Bremen, Germany) ,  Schewior Kevin (Department of Mathematics and Computer Science, Universitaet zu Koln, Cologne, Germany) ,  Stein Cliff (Department of Industrial Engineering and Operations Research, Columbia University, New York, USA)
資料名： Mathematical Programming  (Mathematical Programming)
巻： 183  号： 1-2  ページ： 215-247  発行年： 2020年 
JST資料番号： B0847B  ISSN： 0025-5610  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 著者らは,デッドラインを有するジョブが,それらのリリース日にオンラインでオンラインに到着する基本的なオンラインジョブ入院問題を研究し,タスクは,時間的に完了するジョブの数を最大化する先制的単一サーバスケジュールを決定する事である。既知の不可能性結果を回避するため,いくつかの[数式:原文を参照]に対して,ジョブをスケジューリングするための実行可能な時間ウィンドウが少なくとも[数式:原文を参照]時間である標準的なスラックネス仮定を行った。著者らは,異なるプロバイダコミットメント要求がオンラインアルゴリズムの性能に及ぼす影響を定量化した。著者らの主な貢献は,コミットメント有りと無しのオンラインジョブ受付のための1つの普遍的なアルゴリズムフレームワークである。コミットメントなしで,[数式:原文を参照]の競合比率を有する著者らのアルゴリズムは,この問題のための最良の可能性(決定論的)である。コミットメントモデルに対して,最初の非自明な性能限界を与えた。ジョブのスラックがそのサイズの[数式:原文を参照]画分以下になる前に,コミットメント決定を行う必要があるならば,[数式:原文を参照]の競合比率を[数式:原文を参照]に対して証明した。プロバイダがジョブを始動するとき,この境界は[数式:原文を参照]である。最後に,コミットメントによるスケジューリングのために,「非加重」スループットモデルへの制限が必須であることを観察する。ジョブが個々の重みを持つならば,競合決定論的アルゴリズムを除外する。Copyright The Author(s) 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *スケジューリング ,  時間制限
準シソーラス用語： *コミットメント ,  オンラインアルゴリズム ,  競合比 ,  ISP【インターネット】 ,  決定論 ,  *オンライン , 【Automatic Indexing@JST】

著者キーワード (4件)： 90B35 ,  68M20 ,  68W25 ,  68W40

分類 (2件)： オペレーティングシステム  (JD03020J) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (4件)： オンライン ,  スループット最大化 ,  コミットメント ,  フレームワーク