論文の概要: Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem

• arxiv url: http://arxiv.org/abs/2212.11478v1
• Date: Thu, 22 Dec 2022 04:31:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-23 14:09:45.913955
• Title: Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem
• Title（参考訳）: チャンス制約型Makespanスケジューリング問題に対する進化的アルゴリズムの実行性能
• Authors: Feng Shi, Xiankun Yan, and Frank Neumann
• Abstract要約: 本稿では,Makespan Scheduling問題の確率制約版を提案する。 古典的ランダム化局所探索と (1+1) EAの理論的性能について検討する。 具体的には、Chance-Constrained Makespan Scheduling問題の2つの変種とその計算複雑性について検討する。
• 参考スコア（独自算出の注目度）: 12.791789710379057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influence of external factors, and the actual processing times of these jobs may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities, then separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the two variants. In addition, we investigate the experimental performance of the two algorithms for the two variants.
• Abstract（参考訳）: Makespan Scheduling問題(英語版)は広く研究されているNP-hard問題であり、最も単純なバージョンは、決定論的処理時間を持つジョブを2つの同一マシンに割り当てるアプローチを探究する。 しかし、実際のシナリオでは、各ジョブの実際の処理時間は、外部要因の影響下、ばらつきを伴う期待値の周りに確率的であり、これらのジョブの実際の処理時間は共分散と相関する可能性がある。 そこで本稿では,Makespan スケジューリング問題の確率制約版を提案し,古典的ランダム化局所探索と (1+1) EA の理論的性能について検討する。 より具体的には、まず確率制約されたmakepanスケジューリング問題とその計算複雑性の2つの変種を調査し、次に2つのアルゴリズムの期待実行時間を分析して、その2つの変種について最適な解またはほぼ最適解を得る。 さらに,2つの変種に対する2つのアルゴリズムの実験性能について検討した。

関連論文リスト

• Genetic-based Constraint Programming for Resource Constrained Job Scheduling [5.068093754585243]
  資源制約されたジョブスケジューリングは、鉱業に起源を持つ計算の最適化問題である。 既成のソリューションはこの問題を合理的な時間枠で十分解決できない。 本稿では,制約プログラミングの効率的な探索手法を探索する遺伝的プログラミングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-01T09:57:38Z)
• Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
  多くの実世界の設計問題は、大規模で異質な観測ノイズのため、複数の実験条件を並列に評価し、各条件を複数回再現する。 本稿では,3つのアルゴリズムを含むReplicable Experimental Designフレームワークのバッチトンプソンサンプリングを提案する。 我々は,アルゴリズムの有効性を,精密農業とAutoMLの2つの実世界の応用例で示す。
  論文  参考訳（メタデータ） (2023-11-02T12:46:03Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。 具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。 二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
  論文  参考訳（メタデータ） (2023-04-05T14:36:48Z)
• A Sequential Deep Learning Algorithm for Sampled Mixed-integer Optimisation Problems [0.3867363075280544]
  混合整数最適化問題に対する2つの効率的なアルゴリズムを導入,解析する。 両アルゴリズムが最適解に対して有限時間収束を示すことを示す。 3つの数値実験により,これらのアルゴリズムの有効性を定量的に確立する。
  論文  参考訳（メタデータ） (2023-01-25T17:10:52Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  ジョブショップスケジューリング問題(JSP、Job-shop Scheduling Problem)は、ジョブを含むタスクをできるだけ早く完了するように、マシンを共有するタスクをシーケンスに配置する、よく知られた、困難な最適化問題である。 本稿では,ASP(Multi-shot Answer Set Programming)の解法を用いて,操作を逐次スケジュールし,最適化可能な時間窓への問題分解について検討する。
  論文  参考訳（メタデータ） (2022-05-16T09:33:00Z)
• Data-driven Prediction of Relevant Scenarios for Robust Optimization [0.0]
  離散的な不確実性集合を持つロバストな1段階と2段階の問題について検討する。 本稿では,一連の開始シナリオで反復解法をシード化するデータ駆動型計算を提案する。 実験の結果,提案手法によって少数の優れたスタートシナリオを予測しても,反復的手法の時間を大幅に短縮できることがわかった。
  論文  参考訳（メタデータ） (2022-03-30T19:52:29Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。 ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
  論文  参考訳（メタデータ） (2020-12-24T16:33:17Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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