論文の概要: Scheduling Servers with Stochastic Bilinear Rewards
- arxiv url: http://arxiv.org/abs/2112.06362v1
- Date: Mon, 13 Dec 2021 00:37:20 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-14 19:30:53.635460
- Title: Scheduling Servers with Stochastic Bilinear Rewards
- Title(参考訳): 確率的バイリニア報酬を用いたスケジューリングサーバ
- Authors: Jung-hun Kim and Milan Vojnovic
- Abstract要約: 本稿では,ジョブやサーバを表す特徴ベクトルの双線形モデルに従って,ジョブサーバの割り当てを報奨するマルチクラスマルチサーバキューシステムについて検討する。
本稿では,サーバへのジョブの動的割り当てとともに線形帯域幅アルゴリズムを用いたスケジューリングアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 3.5408022972081685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study a multi-class, multi-server queueing system with
stochastic rewards of job-server assignments following a bilinear model in
feature vectors representing jobs and servers. Our goal is regret minimization
against an oracle policy that has a complete information about system
parameters. We propose a scheduling algorithm that uses a linear bandit
algorithm along with dynamic allocation of jobs to servers. For the baseline
setting, in which mean job service times are identical for all jobs, we show
that our algorithm has a sub-linear regret, as well as a sub-linear bound on
the mean queue length, in the horizon time. We further show that similar bounds
hold under more general assumptions, allowing for non-identical mean job
service times for different job classes and a time-varying set of server
classes. We also show that better regret and mean queue length bounds can be
guaranteed by an algorithm having access to traffic intensities of job classes.
We present results of numerical experiments demonstrating how regret and mean
queue length of our algorithms depend on various system parameters and compare
their performance against a previously proposed algorithm using synthetic
randomly generated data and a real-world cluster computing data trace.
- Abstract(参考訳): 本稿では,ジョブとサーバを表わす特徴ベクトルの双線形モデルに従って,ジョブサーバ割り当ての確率的報奨を伴うマルチクラスマルチサーバキューシステムについて検討する。
私たちの目標は、システムパラメータに関する完全な情報を持つoracleポリシーに対する後悔の最小化です。
本稿では,サーバへのジョブの動的割り当てとともに線形帯域幅アルゴリズムを用いたスケジューリングアルゴリズムを提案する。
平均ジョブサービス時間が全ジョブに対して同一であるベースライン設定に対して,本アルゴリズムでは,平均待ち行列長に対して水平時間内にバウンドするサブリニアリットと,サブリニアリットを持つことを示す。
さらに、同様の境界がより一般的な仮定の下で保持されていることも示しており、異なるジョブクラスやサーバクラスの時間的変動に対して、非identical平均ジョブサービス時間を可能にする。
また,ジョブクラスのトラフィック強度にアルゴリズムがアクセスすることで,後悔や平均キュー長の境界が保証されることを示した。
本稿では,アルゴリズムの残差と平均待ち時間長が様々なシステムパラメータに依存することを示す数値実験の結果を,合成ランダムに生成されたデータと実世界のクラスタ計算データトレースを用いて提案したアルゴリズムと比較した。
関連論文リスト
- Efficient Reinforcement Learning for Routing Jobs in Heterogeneous
Queueing Systems [23.973033446355167]
我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。
均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。
本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
論文 参考訳(メタデータ) (2024-02-02T05:22:41Z) - Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
我々は,過去の経験から学習することで環境に適応するアルゴリズムであるLIBOを開発した。
カーネルが未知だが、すべてのタスク間で共有されるカーネル構造を仮定する。
我々のアルゴリズムは、任意のカーネル化または線形バンディットアルゴリズムと組み合わせて、最適な性能を保証できる。
論文 参考訳(メタデータ) (2022-10-27T14:48:49Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-02T15:37:02Z) - Scheduling in Parallel Finite Buffer Systems: Optimal Decisions under
Delayed Feedback [29.177402567437206]
本稿では,遅延認識の限られた情報の下で並列キューシステムにおけるスケジューリング決定をキャプチャする部分観測可能(PO)モデルを提案する。
得られたポリシーが他の限られた情報スケジューリング戦略より優れていることを数値的に示す。
本稿では,Kaggleが提供するネットワークデータを用いてリアルタイム並列処理を最適化する方法を示す。
論文 参考訳(メタデータ) (2021-09-17T13:45:02Z) - Learning to Schedule [3.5408022972081685]
本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。
各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
論文 参考訳(メタデータ) (2021-05-28T08:04:06Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳(メタデータ) (2021-05-01T10:18:34Z) - Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud
System [54.588242387136376]
エッジクラウドシステムのための学習ベースのスケジューリングフレームワークkaisを紹介する。
まず,分散した要求ディスパッチに対応するために,協調型マルチエージェントアクタ-クリティックアルゴリズムを設計する。
次に,多種多様なシステムスケールと構造について,グラフニューラルネットワークを用いてシステム状態情報を埋め込む。
第3に、リクエストディスパッチとサービスオーケストレーションを調和させる2段階のスケジューリングメカニズムを採用します。
論文 参考訳(メタデータ) (2021-01-17T03:45:25Z) - Rosella: A Self-Driving Distributed Scheduler for Heterogeneous Clusters [7.206919625027208]
異種クラスタにおけるタスクスケジューリングのための,新たな自律分散アプローチであるRosellaを紹介する。
Rosellaは自動的に計算環境を学習し、スケジューリングポリシーをリアルタイムで調整する。
32ノードのAWSクラスタ上で、さまざまなワークロードでRosellaを評価します。
論文 参考訳(メタデータ) (2020-10-28T20:12:29Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z) - Meta-learning with Stochastic Linear Bandits [120.43000970418939]
我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。
我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
論文 参考訳(メタデータ) (2020-05-18T08:41:39Z) - Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of
Partitioned Edge Learning [73.82875010696849]
機械学習アルゴリズムは、人工知能(AI)モデルをトレーニングするために、ネットワークエッジにデプロイされる。
本稿では,パラメータ(計算負荷)割り当てと帯域幅割り当ての新しい共同設計に焦点を当てる。
論文 参考訳(メタデータ) (2020-03-10T05:52:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。