論文の概要: An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming
- arxiv url: http://arxiv.org/abs/2306.05747v1
- Date: Fri, 9 Jun 2023 08:24:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 14:07:38.949163
- Title: An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming
- Title（参考訳）: 制約プログラミングに基づくジョブショップスケジューリング問題に対するエンドツーエンド強化学習手法
- Authors: Pierre Tassel, Martin Gebser, Konstantin Schekotihin
- Abstract要約: 本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。
当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
- 参考スコア（独自算出の注目度）: 5.070542698701157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constraint Programming (CP) is a declarative programming paradigm that allows
for modeling and solving combinatorial optimization problems, such as the
Job-Shop Scheduling Problem (JSSP). While CP solvers manage to find optimal or
near-optimal solutions for small instances, they do not scale well to large
ones, i.e., they require long computation times or yield low-quality solutions.
Therefore, real-world scheduling applications often resort to fast,
handcrafted, priority-based dispatching heuristics to find a good initial
solution and then refine it using optimization methods.
This paper proposes a novel end-to-end approach to solving scheduling
problems by means of CP and Reinforcement Learning (RL). In contrast to
previous RL methods, tailored for a given problem by including procedural
simulation algorithms, complex feature engineering, or handcrafted reward
functions, our neural-network architecture and training algorithm merely
require a generic CP encoding of some scheduling problem along with a set of
small instances. Our approach leverages existing CP solvers to train an agent
learning a Priority Dispatching Rule (PDR) that generalizes well to large
instances, even from separate datasets. We evaluate our method on seven JSSP
datasets from the literature, showing its ability to find higher-quality
solutions for very large instances than obtained by static PDRs and by a CP
solver within the same time limit.
- Abstract（参考訳）: 制約プログラミング(CP)は、ジョブショップスケジューリング問題(JSSP)のような組合せ最適化問題のモデル化と解決を可能にする宣言型プログラミングパラダイムである。
cpソルバは、小さなインスタンスに対して最適あるいはほぼ最適のソリューションを見つけることはできるが、大きなインスタンス、すなわち、長い計算時間や低品質のソリューションにはスケールしない。
したがって、実世界のスケジューリングアプリケーションは、しばしば、高速で手作りの優先度に基づくディスパッチヒューリスティックを用いて、優れた初期解を見つけ、最適化手法を用いてそれを洗練する。
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する手法を提案する。
手続き的シミュレーションアルゴリズム、複雑な特徴工学、手作りの報酬関数を含む従来のRL法とは対照的に、我々のニューラルネットワークアーキテクチャとトレーニングアルゴリズムは、いくつかのスケジューリング問題の一般的なCPエンコーディングと、一連の小さなインスタンスを必要とするだけである。
提案手法では,既存のcpソルバを利用して,個別のデータセットからであっても,大規模インスタンスによく一般化する優先度ディスパッチルール(pdr)を学習するエージェントを訓練する。
本手法を文献から7つのjsspデータセット上で評価し,静的なpdrとcpソルバによって得られるものよりも,非常に大きなインスタンスに対して高品質な解を見つける能力を示した。
関連論文リスト
- Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem [1.3927943269211593]
本稿では,制約プログラミング(CP)をディープラーニング(DL)ベースの方法論に統合し,両者の利点を活用することを目的とする。
本稿では,CP が生成する最適解を用いて DL モデルを訓練し,高品質なデータからモデルを学習する手法を提案する。
我々のハイブリッドアプローチは3つの公開FJSSPベンチマークで広範囲にテストされ、5つの最先端DRLアプローチよりも優れた性能を示している。
論文 参考訳（メタデータ） (2024-03-14T10:16:57Z) - Accelerating Exact Combinatorial Optimization via RL-based
Initialization -- A Case Study in Scheduling [1.3053649021965603]
本研究の目的は、最適化問題に対処する機械学習(ML)を用いた革新的なアプローチを開発することである。
1) 粗粒スケジューラとしての解法, 2) 解緩和, 3) ILPによる正確な解法の3つのステップを含む新しい2段階のRL-to-ILPスケジューリングフレームワークを導入する。
提案フレームワークは, 正確なスケジューリング手法と比較して, 最大128ドルの高速化を実現しつつ, 同一のスケジューリング性能を示す。
論文 参考訳（メタデータ） (2023-08-19T15:52:43Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳（メタデータ） (2021-05-01T10:18:34Z) - Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。
正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。
最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文 参考訳（メタデータ） (2021-03-18T14:49:52Z) - 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) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。
提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。
本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
論文 参考訳（メタデータ） (2020-04-20T14:04:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。