論文の概要: Genetic-based Constraint Programming for Resource Constrained Job Scheduling

• arxiv url: http://arxiv.org/abs/2402.00459v1
• Date: Thu, 1 Feb 2024 09:57:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-02 15:50:49.794010
• Title: Genetic-based Constraint Programming for Resource Constrained Job Scheduling
• Title（参考訳）: 資源制約付きジョブスケジューリングのための遺伝的制約プログラミング
• Authors: Su Nguyen and Dhananjay Thiruvady and Yuan Sun and Mengjie Zhang
• Abstract要約: 資源制約されたジョブスケジューリングは、鉱業に起源を持つ計算の最適化問題である。 既成のソリューションはこの問題を合理的な時間枠で十分解決できない。 本稿では,制約プログラミングの効率的な探索手法を探索する遺伝的プログラミングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.068093754585243
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Resource constrained job scheduling is a hard combinatorial optimisation problem that originates in the mining industry. Off-the-shelf solvers cannot solve this problem satisfactorily in reasonable timeframes, while other solution methods such as many evolutionary computation methods and matheuristics cannot guarantee optimality and require low-level customisation and specialised heuristics to be effective. This paper addresses this gap by proposing a genetic programming algorithm to discover efficient search strategies of constraint programming for resource-constrained job scheduling. In the proposed algorithm, evolved programs represent variable selectors to be used in the search process of constraint programming, and their fitness is determined by the quality of solutions obtained for training instances. The novelties of this algorithm are (1) a new representation of variable selectors, (2) a new fitness evaluation scheme, and (3) a pre-selection mechanism. Tests with a large set of random and benchmark instances, the evolved variable selectors can significantly improve the efficiency of constraining programming. Compared to highly customised metaheuristics and hybrid algorithms, evolved variable selectors can help constraint programming identify quality solutions faster and proving optimality is possible if sufficiently large run-times are allowed. The evolved variable selectors are especially helpful when solving instances with large numbers of machines.
• Abstract（参考訳）: 資源制約付きジョブスケジューリングは、鉱業を起源とするハードコンビネート最適化問題である。 既製の解法はこの問題を合理的な時間枠では十分解決できないが、多くの進化的計算法や数理学のような他の解法は最適性を保証することができず、低レベルのカスタマイズと特殊なヒューリスティックが有効である。 本稿では、資源制約のあるジョブスケジューリングのための制約プログラミングの効率的な探索戦略を見つけるために、遺伝的プログラミングアルゴリズムを提案する。 提案アルゴリズムでは,制約プログラミングの探索プロセスで使用する可変セレクタを進化プログラムで表現し,それらの適合性は,トレーニングインスタンスで得られるソリューションの品質によって決定される。 本アルゴリズムの新規性は, (1) 可変セレクタの新しい表現, (2) 適合性評価スキーム, (3) 事前選択機構である。 多数のランダムおよびベンチマークインスタンスを持つテストでは、進化した変数セレクタは、制約プログラミングの効率を大幅に改善することができる。 高度にカスタマイズされたメタヒューリスティックとハイブリッドアルゴリズムと比較して、進化した変数セレクタは、制約プログラミングによって品質ソリューションをより早く識別し、十分な大きな実行時間が可能であれば最適性を証明することができる。 進化した変数セレクタは、多数のマシンでインスタンスを解決するのに特に役立ちます。

関連論文リスト

• Differentiable Combinatorial Scheduling at Scale [18.09256072039255]
  本稿では,Gumbel-Softmax微分可能なサンプリング手法を用いて,微分可能なスケジューリングフレームワークを提案する。 スケジューリングタスクの不等式制約をエンコードするために,任意の不等式制約を積極的にエンコードするテキスト制約付きGumbel Trickを導入する。 本手法は, トレーニングデータを必要とせずに, 勾配降下による効率よく, スケーラブルなスケジューリングを容易にする。
  論文  参考訳（メタデータ） (2024-06-06T02:09:39Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver [2.8425837800129696]
  本稿では,制約型プログラミング解法内での値選択に利用できる汎用的な学習手法を提案する。 これは、深いQ-ラーニングアルゴリズム、カスタマイズされた報酬信号、異種グラフニューラルネットワークアーキテクチャの組み合わせによって実現されている。
  論文  参考訳（メタデータ） (2023-01-05T05:13:48Z)
• A Hybrid Evolutionary Approach to Solve University Course Allocation Problem [0.0]
  本稿では,大学授業割当問題に関わる課題を克服するための様々な制約,難易度,解決策について論じる。 局所補修アルゴリズムと修正遺伝的アルゴリズムを組み合わせたハイブリッド進化アルゴリズムが定義されている。
  論文  参考訳（メタデータ） (2022-11-15T09:43:02Z)
• An Efficient Merge Search Matheuristic for Maximising the Net Present Value of Project Schedules [5.10800491975164]
  リソース制約のあるプロジェクトスケジューリングは多くの実用的なアプリケーションにおいて重要な最適化問題である。 本稿では,資源制約のあるプロジェクトスケジューリングを解くために,マージ探索と並列計算に基づく新しい数学ヒューリスティックアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-20T13:30:23Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。 本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
  論文  参考訳（メタデータ） (2021-07-20T11:23:21Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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