論文の概要: Solving large flexible job shop scheduling instances by generating a
diverse set of scheduling policies with deep reinforcement learning
- arxiv url: http://arxiv.org/abs/2310.15706v1
- Date: Tue, 24 Oct 2023 10:35:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 19:21:52.073774
- Title: Solving large flexible job shop scheduling instances by generating a
diverse set of scheduling policies with deep reinforcement learning
- Title（参考訳）: 深層強化学習を用いた多種多様なスケジューリングポリシーの作成による大規模フレキシブルジョブショップスケジューリングインスタンスの解法
- Authors: Imanol Echeverria, Maialen Murua, Roberto Santana
- Abstract要約: フレキシブルジョブショップスケジューリング問題(FJSSP)は文献で広く研究されている。
グラフニューラルネットワークを用いたMDPとしてFJSSPをモデリングする新しい手法を提案する。
また、推論をより堅牢にする方法として、並列化可能なスケジューリングポリシーの多様なセットを生成し、DRを使って制限する2つの方法を提案する。
- 参考スコア（独自算出の注目度）: 1.565361244756411
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Flexible Job Shop Scheduling Problem (FJSSP) has been extensively studied
in the literature, and multiple approaches have been proposed within the
heuristic, exact, and metaheuristic methods. However, the industry's demand to
be able to respond in real-time to disruptive events has generated the
necessity to be able to generate new schedules within a few seconds. Among
these methods, under this constraint, only dispatching rules (DRs) are capable
of generating schedules, even though their quality can be improved. To improve
the results, recent methods have been proposed for modeling the FJSSP as a
Markov Decision Process (MDP) and employing reinforcement learning to create a
policy that generates an optimal solution assigning operations to machines.
Nonetheless, there is still room for improvement, particularly in the larger
FJSSP instances which are common in real-world scenarios. Therefore, the
objective of this paper is to propose a method capable of robustly solving
large instances of the FJSSP. To achieve this, we propose a novel way of
modeling the FJSSP as an MDP using graph neural networks. We also present two
methods to make inference more robust: generating a diverse set of scheduling
policies that can be parallelized and limiting them using DRs. We have tested
our approach on synthetically generated instances and various public benchmarks
and found that our approach outperforms dispatching rules and achieves better
results than three other recent deep reinforcement learning methods on larger
FJSSP instances.
- Abstract（参考訳）: フレキシブルなジョブショップスケジューリング問題(fjssp)は文献で広く研究されており、ヒューリスティック、精密、メタヒューリスティックな手法で複数のアプローチが提案されている。
しかし、業界がリアルタイムでディスラプティブなイベントに応答できるという要求は、数秒以内に新しいスケジュールを生成する必要性を生んでいる。
この制約の下では、品質が向上してもスケジュールを生成することができるのはディスパッチルール(DR)のみである。
この結果を改善するため、fjsspをマルコフ決定プロセス(mdp)としてモデル化し、強化学習を用いて機械に操作を割り当てる最適解を生成するポリシーを作成するための最近の手法が提案されている。
それでも、特に現実のシナリオで一般的な大きなJSSPインスタンスでは、改善の余地は残っている。
そこで本研究では,FJSSPの大規模インスタンスを堅牢に解決する手法を提案する。
そこで本稿では,グラフニューラルネットワークを用いてFJSSPをMDPとしてモデル化する手法を提案する。
また、推論をより堅牢にする方法として、並列化可能なスケジューリングポリシーの多様なセットを生成し、DRを使って制限する2つの方法を提案する。
提案手法は,より大規模なFJSSPインスタンス上での他の3つの深層強化学習手法よりも,分散ルールよりも優れ,より優れた結果が得られることがわかった。
関連論文リスト
- Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
本稿では,複雑な制約を伴う最適化問題に対して,新しいオフラインRL法を提案する。
我々のアプローチは、エッジ属性のアクションを符号化し、専門家ソリューションの模倣と期待される報酬のバランスをとる。
本手法がジョブショップスケジューリングおよびフレキシブルジョブショップスケジューリングベンチマークに与える影響を実証する。
論文 参考訳（メタデータ） (2024-10-21T07:33:42Z) - 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) - Bridging Distributionally Robust Learning and Offline RL: An Approach to
Mitigate Distribution Shift and Partial Data Coverage [32.578787778183546]
オフライン強化学習(RL)アルゴリズムは、過去の(オフライン)データを用いて最適な警察を学習する。
オフラインRLの主な課題の1つは、分散シフトである。
分散ロバスト学習(DRL)フレームワークを用いた2つのオフラインRLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-27T19:19:30Z) - Flexible Job Shop Scheduling via Dual Attention Network Based
Reinforcement Learning [73.19312285906891]
フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。
近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。
本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
論文 参考訳（メタデータ） (2023-05-09T01:35:48Z) - Offline Policy Optimization in RL with Variance Regularizaton [142.87345258222942]
定常分布補正を用いたオフラインRLアルゴリズムの分散正則化を提案する。
Fenchel双対性を用いることで、分散正規化器の勾配を計算するための二重サンプリング問題を回避することができることを示す。
オフライン分散正規化アルゴリズム(OVAR)は,既存のオフラインポリシー最適化アルゴリズムを拡張できる。
論文 参考訳（メタデータ） (2022-12-29T18:25:01Z) - Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop
Scheduling [30.45126420996238]
本稿では,完全解の符号化にグラフ表現を用いる JSSP を解くための DRL 誘導型改良法を提案する。
本研究では,2つのモジュールからなるグラフニューラルネットワークに基づく表現スキームを設計し,改良プロセス中に遭遇したグラフ内の動的トポロジと異なるタイプのノードの情報を自動的に取得する。
古典的なベンチマーク実験により,本手法が学んだ改善方針は,最先端のDRL法よりも大きなマージンで優れていることが示された。
論文 参考訳（メタデータ） (2022-11-20T10:20:13Z) - Diffusion Policies as an Expressive Policy Class for Offline
Reinforcement Learning [70.20191211010847]
オフライン強化学習(RL)は、以前に収集した静的データセットを使って最適なポリシーを学ぶことを目的としている。
本稿では,条件付き拡散モデルを用いたディフュージョンQ-ラーニング(Diffusion-QL)を提案する。
本手法はD4RLベンチマークタスクの大部分において最先端の性能を実現することができることを示す。
論文 参考訳（メタデータ） (2022-08-12T09:54:11Z) - DL-DRL: A double-level deep reinforcement learning approach for
large-scale task scheduling of multi-UAV [65.07776277630228]
分割・征服フレームワーク(DCF)に基づく二重レベル深層強化学習(DL-DRL)手法を提案する。
特に,上層部DRLモデルにおけるエンコーダ・デコーダ構成ポリシネットワークを設計し,タスクを異なるUAVに割り当てる。
また、低レベルDRLモデルにおける別の注意に基づくポリシーネットワークを利用して、各UAVの経路を構築し、実行されたタスク数を最大化する。
論文 参考訳（メタデータ） (2022-08-04T04:35:53Z) - Jump-Start Reinforcement Learning [68.82380421479675]
本稿では、オフラインデータやデモ、あるいは既存のポリシーを使ってRLポリシーを初期化するメタアルゴリズムを提案する。
特に,タスク解決に2つのポリシーを利用するアルゴリズムであるJump-Start Reinforcement Learning (JSRL)を提案する。
実験により、JSRLは既存の模倣と強化学習アルゴリズムを大幅に上回っていることを示す。
論文 参考訳（メタデータ） (2022-04-05T17:25:22Z) - Improving Generalization of Deep Reinforcement Learning-based TSP
Solvers [19.29028564568974]
本稿では,ディープラーニングアーキテクチャとDRL学習方法を含むMAGICという新しいアプローチを提案する。
マルチレイヤパーセプトロン,グラフニューラルネットワーク,アテンションモデルを統合したアーキテクチャでは,旅行セールスマンソリューションを逐次生成するポリシを定義している。
1) DRLポリシー更新をローカル検索とインターリーブし(新しいローカル検索技術を用いて)、(2) 新たなシンプルなベースラインを使用し、(3) 勾配学習を適用した。
論文 参考訳（メタデータ） (2021-10-06T15:16:19Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳（メタデータ） (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。