論文の概要: Learning to schedule job-shop problems: Representation and policy
learning using graph neural network and reinforcement learning
- arxiv url: http://arxiv.org/abs/2106.01086v1
- Date: Wed, 2 Jun 2021 11:40:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-03 14:24:59.682991
- Title: Learning to schedule job-shop problems: Representation and policy
learning using graph neural network and reinforcement learning
- Title(参考訳): 求職者の問題をスケジューリングする学習:グラフニューラルネットワークと強化学習を用いた表現と政策学習
- Authors: Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo
Park
- Abstract要約: グラフニューラルネットワーク(GNN)と強化学習(RL)を用いて,ジョブショップ問題(JSSP)のスケジューリングを学習するフレームワークを提案する。
我々は、GNNスケジューラが、その超一般化能力により、様々なベンチマークJSSP上で、現実的に好まれるルールやRLベースのスケジューラよりも優れていることを実証的に示す。
- 参考スコア(独自算出の注目度): 9.379652654427959
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a framework to learn to schedule a job-shop problem (JSSP) using a
graph neural network (GNN) and reinforcement learning (RL). We formulate the
scheduling process of JSSP as a sequential decision-making problem with graph
representation of the state to consider the structure of JSSP. In solving the
formulated problem, the proposed framework employs a GNN to learn that node
features that embed the spatial structure of the JSSP represented as a graph
(representation learning) and derive the optimum scheduling policy that maps
the embedded node features to the best scheduling action (policy learning). We
employ Proximal Policy Optimization (PPO) based RL strategy to train these two
modules in an end-to-end fashion. We empirically demonstrate that the GNN
scheduler, due to its superb generalization capability, outperforms practically
favored dispatching rules and RL-based schedulers on various benchmark JSSP. We
also confirmed that the proposed framework learns a transferable scheduling
policy that can be employed to schedule a completely new JSSP (in terms of size
and parameters) without further training.
- Abstract(参考訳): 本稿では,グラフニューラルネットワーク(GNN)と強化学習(RL)を用いて,ジョブショップ問題(JSSP)のスケジューリングを学習するフレームワークを提案する。
本研究では,JSSPのスケジューリング過程を,JSSPの構造を考慮した状態のグラフ表現を用いた逐次決定問題として定式化する。
定式化問題の解決にあたり,提案フレームワークはGNNを用いて,JSSPの空間構造をグラフ(表現学習)として埋め込んだノード特徴を学習し,組込みノード特徴を最適なスケジューリング動作(政治学習)にマッピングする最適なスケジューリングポリシを導出する。
我々は、PPO(Proximal Policy Optimization)に基づくRL戦略を用いて、これらの2つのモジュールをエンドツーエンドでトレーニングする。
我々は、GNNスケジューラが、超一般化能力のため、様々なベンチマークJSSP上で、事実上好まれるディスパッチルールやRLベースのスケジューラよりも優れていることを実証的に示す。
また,提案フレームワークが(サイズやパラメータの面で)完全に新しいjsspのスケジュールに利用できる転送可能なスケジューリングポリシーを,さらなるトレーニングなしで学習できることを確認した。
関連論文リスト
- Learning-enabled Flexible Job-shop Scheduling for Scalable Smart
Manufacturing [11.509669981978874]
スマートマニュファクチャリングシステムでは、生産性を最大化するためのソリューションを最適化するために、輸送制約付きフレキシブルなジョブショップスケジューリングが不可欠である。
近年, 深部強化学習(DRL)に基づくFJSPT法の開発が, 大規模一般化の課題に直面している。
Heterogeneous Graph Scheduler (HGS) と呼ばれる新しいグラフベースのDRL法を導入する。
論文 参考訳(メタデータ) (2024-02-14T06:49:23Z) - Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。
適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。
我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
論文 参考訳(メタデータ) (2023-07-07T15:03:42Z) - Scheduling Inference Workloads on Distributed Edge Clusters with
Reinforcement Learning [11.007816552466952]
本稿では,エッジネットワークにおける予測クエリを短時間でスケジューリングする問題に焦点をあてる。
シミュレーションにより,大規模ISPの現実的なネットワーク設定とワークロードにおけるいくつかのポリシーを解析する。
我々は、強化学習に基づくスケジューリングアルゴリズムASETを設計し、システム条件に応じてその決定を適応させることができる。
論文 参考訳(メタデータ) (2023-01-31T13:23:34Z) - Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop
Scheduling [30.45126420996238]
本稿では,完全解の符号化にグラフ表現を用いる JSSP を解くための DRL 誘導型改良法を提案する。
本研究では,2つのモジュールからなるグラフニューラルネットワークに基づく表現スキームを設計し,改良プロセス中に遭遇したグラフ内の動的トポロジと異なるタイプのノードの情報を自動的に取得する。
古典的なベンチマーク実験により,本手法が学んだ改善方針は,最先端のDRL法よりも大きなマージンで優れていることが示された。
論文 参考訳(メタデータ) (2022-11-20T10:20:13Z) - Hybrid intelligence for dynamic job-shop scheduling with deep
reinforcement learning and attention mechanism [28.28095225164155]
我々は、DJSPをマルコフ決定過程(MDP)として定式化し、強化学習(RL)に対処する。
本稿では,分割グラフを状態とするフレキシブルなハイブリッドフレームワークを提案する。
我々は、有名なOR-Libraryに基づく公開ベンチマークであるGymjspを紹介し、RLおよびDJSP研究コミュニティのための標準化されたオフザシェルフ施設を提供する。
論文 参考訳(メタデータ) (2022-01-03T09:38:13Z) - Compositional Reinforcement Learning from Logical Specifications [21.193231846438895]
最近のアプローチでは、与えられた仕様から報酬関数を自動的に生成し、適切な強化学習アルゴリズムを用いてポリシーを学習する。
我々は、高レベルの計画と強化学習をインターリーブする、DiRLと呼ばれる構成学習手法を開発した。
提案手法では,各エッジ(サブタスク)のニューラルネットワークポリシをDijkstraスタイルの計画アルゴリズムで学習し,グラフの高レベルプランを計算する。
論文 参考訳(メタデータ) (2021-06-25T22:54:28Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳(メタデータ) (2021-05-01T10:18:34Z) - Learning to Execute Programs with Instruction Pointer Attention Graph
Neural Networks [55.98291376393561]
グラフニューラルネットワーク(GNN)は、ソフトウェアエンジニアリングタスクを学習するための強力なツールとして登場した。
リカレントニューラルネットワーク(RNN)は、長いシーケンシャルな推論の連鎖に適しているが、プログラム構造を自然に組み込んでいるわけではない。
本稿では,新しいGNNアーキテクチャ,IPA-GNN(Instruction Pointer Attention Graph Neural Networks)を導入する。
論文 参考訳(メタデータ) (2020-10-23T19:12:30Z) - Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
グラフニューラルネットワーク(GNN)は、局所的なグラフ構造をモデル化し、隣人からの情報を集約することで階層的なパターンを捉えることを目的としている。
複雑なグラフとスパースな特徴を与えられた各ノードに対して効果的なアグリゲーション戦略を開発することは難しい課題である。
本稿では,GNNのサンプリング手順とメッセージパッシングを複合学習プロセスにモデル化するメタ政治フレームワークであるPolicy-GNNを提案する。
論文 参考訳(メタデータ) (2020-06-26T17:03:06Z) - Resource Allocation via Graph Neural Networks in Free Space Optical
Fronthaul Networks [119.81868223344173]
本稿では,自由空間光(FSO)フロントホールネットワークにおける最適資源割り当てについて検討する。
我々は、FSOネットワーク構造を利用するために、ポリシーパラメータ化のためのグラフニューラルネットワーク(GNN)を検討する。
本アルゴリズムは,システムモデルに関する知識が不要なモデルフリーでGNNを訓練するために開発された。
論文 参考訳(メタデータ) (2020-06-26T14:20:48Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳(メタデータ) (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。