論文の概要: On Preemption and Learning in Stochastic Scheduling

• arxiv url: http://arxiv.org/abs/2205.15695v3
• Date: Thu, 1 Jun 2023 14:58:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-02 11:18:32.952483
• Title: On Preemption and Learning in Stochastic Scheduling
• Title（参考訳）: 確率スケジューリングにおけるプリエンプションと学習について
• Authors: Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, Vianney Perchet
• Abstract要約: 本研究では,その時間分布を決定するジョブタイプに属するジョブの単一マシンスケジューリングについて検討する。 我々は,既知型の性能と比較して,サブ線形超過コストを実現するアルゴリズムを設計し,非プリエンプティブの場合の限界を低くする。
• 参考スコア（独自算出の注目度）: 22.32180964593702
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.
• Abstract（参考訳）: 本研究では,ジョブの時間分布を決定するジョブタイプに属するジョブの単一マシンスケジューリングについて検討する。 まず、型特性が分かっているシナリオを分析して、タイプが不明な2つの学習シナリオに移行します。非プリエンプティブ問題、別のジョブに移行する前に各開始ジョブを完了しなければならない場合、そして、別のジョブに移行するためにジョブの実行を一時停止できるプリエンプティブ問題です。 いずれの場合も、既知型の性能と比較して、サブ線形超過コストを実現するアルゴリズムを設計し、非プリエンプティブケースの下位境界を証明する。 特に, 理論上およびシミュレーションにより, 異なるジョブタイプの持続時間が互いに遠くなると, プリエンプティブアルゴリズムが非プリエンプティブアルゴリズムを大きく上回ることを示す。

関連論文リスト

• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Multi-task Bias-Variance Trade-off Through Functional Constraints [102.64082402388192]
  マルチタスク学習は、多様なタスクによく機能する関数の集合を取得することを目的としている。 本稿では,2つの極端な学習シナリオ,すなわちすべてのタスクに対する単一関数と,他のタスクを無視するタスク固有関数から直感を抽出する。 本稿では,集中関数に対するドメイン固有解を強制する制約付き学習定式化を導入する。
  論文  参考訳（メタデータ） (2022-10-27T16:06:47Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Metalearning Linear Bandits by Prior Update [7.519872646378836]
  完全なベイズ的アプローチは、問題のパラメータは既知の事前から生成されると仮定するが、実際にはそのような情報は欠落することが多い。 この問題は、ある部分的な情報を持つ意思決定設定において悪化し、不特定事前の使用は、探索の質が悪く、性能が劣る可能性がある。 この研究において、線形帯域幅とガウス事前の文脈において、事前推定が真の事前に十分近い限り、不特定事前を用いたアルゴリズムの性能は真の先行を用いたアルゴリズムのそれに近いことを証明した。
  論文  参考訳（メタデータ） (2021-07-12T11:17:01Z)
• Learning to Schedule [3.5408022972081685]
  本稿では,ジョブが生み出す累積保持コストを最小限に抑えるための学習・スケジューリングアルゴリズムを提案する。 各タイムスロットにおいて、サーバはシステムに残されているジョブのランダム保持コストを受信しながらジョブを処理できる。
  論文  参考訳（メタデータ） (2021-05-28T08:04:06Z)
• Discriminative, Generative and Self-Supervised Approaches for Target-Agnostic Learning [8.666667951130892]
  生成的および自己教師型学習モデルは、そのタスクでうまく機能することが示されている。 擬似相似理論の導出した定理は、結合分布モデルの推定に関係があることも示している。
  論文  参考訳（メタデータ） (2020-11-12T15:03:40Z)
• Temporally Correlated Task Scheduling for Sequence Learning [143.70523777803723]
  多くのアプリケーションにおいて、シーケンス学習タスクは通常、複数の時間的に相関した補助タスクと関連付けられている。 シーケンス学習に学習可能なスケジューラを導入し、トレーニングのための補助的なタスクを適応的に選択できる。 本手法は,同時翻訳とストックトレンド予測の性能を著しく向上させる。
  論文  参考訳（メタデータ） (2020-07-10T10:28:54Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Sequence-to-sequence models for workload interference [1.988145627448243]
  データセンターでのジョブのスケジューリングは難しいシナリオであり、ジョブは厳しいスローダウンや実行の失敗につながるリソースを競うことができる。 現在のテクニックは、多くが機械学習とジョブモデリングを含むもので、時間にわたってワークロードの振る舞いを要約に基づいている。 本稿では,リソースや実行時間に対する行動に基づいて,データセンタ上でのジョブの協調スケジューリングをモデル化する手法を提案する。
  論文  参考訳（メタデータ） (2020-06-25T14:11:46Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  逐次データによる曖昧な予測を扱うために,Multiple hypothesis Prediction(MHP)モデルの拡張を提案する。 また、不確実性を考慮するのに適した曖昧な問題に対する新しい尺度も導入する。
  論文  参考訳（メタデータ） (2020-03-10T09:15:42Z)

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

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