論文の概要: Job Dispatching Policies for Queueing Systems with Unknown Service Rates

• arxiv url: http://arxiv.org/abs/2106.04707v2
• Date: Thu, 10 Jun 2021 17:39:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-13 05:35:11.545955
• Title: Job Dispatching Policies for Queueing Systems with Unknown Service Rates
• Title（参考訳）: 未知のサービスレートを有する待ち行列システムのためのジョブディスパッチポリシー
• Authors: Tuhinangshu Choudhury, Gauri Joshi, Weina Wang, Sanjay Shakkottai
• Abstract要約: サービスレートや待ち行列の長さの知識のないジョブディスパッチの問題に対処する。 この問題は、ジョブをすべてのサーバに送信してサービスレートを見積もる、という、新たな探索と探索のトレードオフを提示する。 本稿では,離職者からサービス率を学習するバンディットに基づく調査政策を提案する。
• 参考スコア（独自算出の注目度）: 27.06636332290768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy.
• Abstract（参考訳）: すべてのジョブを保持する中央キューが存在しないマルチサーバキューシステムでは、ジョブディスパッチポリシを使用して、ひとつのサーバのキューにジョブを割り当てる。 join-the-shortest-queue や shortest expected delay のような古典的なジョブディスパッチポリシーは、サーバのサービスレートとキューの長さがディスパッチタに知られていると仮定している。 そこで本研究では,サービスレートや待ち行列の長さの知識を必要とせず,ジョブのディスパッチの問題に取り組む。 この問題は、ジョブをすべてのサーバに送信してサービスレートを見積もることと、現在知られている最速のサーバを活用して、待ち行列の遅延を最小化する、という、新たなエクスプロイテーショントレードオフを提示する。 我々は,監視職の退社からサービス率を学習するバンディットに基づく探索政策を提案する。 有限のアクションセットのうち1つだけが最適である標準的なマルチアームバンディット問題とは異なり、最適なポリシーでは各サーバに送信されるジョブの最適な割合を特定する必要がある。 提案手法の有効性を実証するために,後悔の分析とシミュレーションを行った。

関連論文リスト

• Queueing Matching Bandits with Preference Feedback [10.988222071035198]
  我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。 各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。 我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
  論文  参考訳（メタデータ） (2024-10-14T02:29:06Z)
• WorkArena: How Capable Are Web Agents at Solving Common Knowledge Work Tasks? [83.19032025950986]
  本稿では,Webブラウザを介してソフトウェアと対話する大規模言語モデルベースエージェントについて検討する。 WorkArenaは、広く使用されているServiceNowプラットフォームに基づく33のタスクのベンチマークである。 BrowserGymは、そのようなエージェントの設計と評価のための環境である。
  論文  参考訳（メタデータ） (2024-03-12T14:58:45Z)
• Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
  我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。 均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。 本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
  論文  参考訳（メタデータ） (2024-02-02T05:22:41Z)
• A Survey on Service Route and Time Prediction in Instant Delivery: Taxonomy, Progress, and Prospects [58.746820564288846]
  Route&Time Prediction (RTP) は、労働者の到着時間だけでなく、将来のサービス経路を推定することを目的としている。 これまで多くのアルゴリズムが開発されてきたが、この領域の研究者を導くための体系的で包括的な調査は行われていない。 提案手法は,2つの基準に基づいて分類される: (i) タスクのタイプ, (i) 時間のみの予測, (ii) シーケンスベースモデルとグラフベースモデルを含むモデルアーキテクチャ, (iii) 教師付き学習(SL) とDeep Reinforcementを含む学習パラダイム。
  論文  参考訳（メタデータ） (2023-09-03T14:43:33Z)
• Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints [0.610240618821149]
  簡単な通信網における最適オンラインリソース予約問題について検討する。 そこで我々は,オンラインサドルポイントアルゴリズムを提案し,関連するK-ベンチマークの後悔に対する上限を提示する。
  論文  参考訳（メタデータ） (2023-05-24T20:47:17Z)
• Optimization of Image Transmission in a Cooperative Semantic Communication Networks [68.2233384648671]
  画像伝送のためのセマンティック通信フレームワークを開発した。 サーバは、セマンティックコミュニケーション技術を用いて、画像の集合を協調的にユーザへ送信する。 抽出した意味情報と原画像との相関関係を測定するために,マルチモーダル・メトリックを提案する。
  論文  参考訳（メタデータ） (2023-01-01T15:59:13Z)
• Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB [18.898514227870926]
  本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。 目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。 我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-02T15:37:02Z)
• Predicting batch queue job wait times for informed scheduling of urgent HPC workloads [0.0]
  本研究では,待ち時間予測のための新しい機械学習手法について検討する。 我々はこれらの予測をSlurmが生成した推定値と比較する。 我々の手法は、実際の開始時間の10分以内に、すべてのジョブの4分の3の開始時間を正確に予測できる。
  論文  参考訳（メタデータ） (2022-04-28T14:51:58Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。