論文の概要: Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem
- arxiv url: http://arxiv.org/abs/2409.02697v1
- Date: Wed, 4 Sep 2024 13:33:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-05 18:06:50.014623
- Title: Decision Transformer for Enhancing Neural Local Search on the Job Shop Scheduling Problem
- Title(参考訳): ジョブショップスケジューリング問題におけるニューラルローカル検索の高速化のための決定変換器
- Authors: Constantin Waubert de Puiseau, Fabian Wolz, Merlin Montag, Jannik Peters, Hasan Tercan, Tobias Meisen,
- Abstract要約: ジョブショップスケジューリング問題(JSSP)とその解法アルゴリズムは、何十年もの間、アカデミックと産業の両方に永続的な関心を集めてきた。
近年、機械学習(ML)は、JSSPのための既存のソリューションと新しいソリューションの構築において、より短い時間でより良いソリューションを見つけることを目的として、ますます重要な役割を担っている。
我々は、JSSP上の大規模局所探索を効率よく効果的に制御できる、Neural Local Search(NLS)と呼ばれる最先端の深層強化学習(DRL)エージェントの上に構築する。
- 参考スコア(独自算出の注目度): 10.316443594063173
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The job shop scheduling problem (JSSP) and its solution algorithms have been of enduring interest in both academia and industry for decades. In recent years, machine learning (ML) is playing an increasingly important role in advancing existing and building new heuristic solutions for the JSSP, aiming to find better solutions in shorter computation times. In this paper we build on top of a state-of-the-art deep reinforcement learning (DRL) agent, called Neural Local Search (NLS), which can efficiently and effectively control a large local neighborhood search on the JSSP. In particular, we develop a method for training the decision transformer (DT) algorithm on search trajectories taken by a trained NLS agent to further improve upon the learned decision-making sequences. Our experiments show that the DT successfully learns local search strategies that are different and, in many cases, more effective than those of the NLS agent itself. In terms of the tradeoff between solution quality and acceptable computational time needed for the search, the DT is particularly superior in application scenarios where longer computational times are acceptable. In this case, it makes up for the longer inference times required per search step, which are caused by the larger neural network architecture, through better quality decisions per step. Thereby, the DT achieves state-of-the-art results for solving the JSSP with ML-enhanced search.
- Abstract(参考訳): ジョブショップスケジューリング問題(JSSP)とその解法アルゴリズムは、何十年にもわたってアカデミックと産業の両方に永続的な関心を集めてきた。
近年、機械学習(ML)はJSSPの既存ソリューションと新しいヒューリスティックソリューションの構築において、より短い計算時間でより良いソリューションを見つけることを目的として、ますます重要な役割を担っている。
本稿では,最新の深部強化学習(DRL)エージェントであるNeural Local Search(NLS)上に構築し,JSSP上の大規模局所探索を効率的に効果的に制御する。
特に、訓練されたNLSエージェントが取得した探索軌跡に基づいて、決定変換器(DT)アルゴリズムを訓練し、学習された意思決定シーケンスをさらに改善する手法を開発した。
実験の結果,DT は NLS エージェントと異なる局所探索戦略を学習し,多くの場合,NLS エージェント自体よりも効果的であることがわかった。
解の質と検索に必要な計算時間とのトレードオフに関して、DTはより長い計算時間が許容されるアプリケーションシナリオにおいて特に優れている。
この場合、より大規模なニューラルネットワークアーキテクチャによって引き起こされる検索ステップ毎の推論時間の長さを、ステップ毎のより良い品質決定によって補うことができる。
これにより、DTは、ML強化探索を用いてJSSPを解くための最先端の結果を得る。
関連論文リスト
- Beyond Training: Optimizing Reinforcement Learning Based Job Shop Scheduling Through Adaptive Action Sampling [10.931466852026663]
推論における訓練深部強化学習(DRL)エージェントの最適利用について検討した。
我々の研究は、探索アルゴリズムと同様に、訓練されたDRLエージェントの利用は許容できる計算予算に依存するべきであるという仮説に基づいている。
そこで本稿では, 与えられた多数の解と任意の訓練されたエージェントに対して最適なパラメータ化を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-11T14:59:18Z) - Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
ジョブショップスケジューリング問題(JSSP、Job-Shop Scheduling Problem)は、タスクをマシン上でスケジュールする必要がある最適化問題である。
本稿では,Dreep Reinforcement Learning (DRL) 技術を利用してロバストなソリューションを探索する手法を提案する。
論文 参考訳(メタデータ) (2024-03-04T08:38:55Z) - Age-Based Scheduling for Mobile Edge Computing: A Deep Reinforcement
Learning Approach [58.911515417156174]
我々は情報時代(AoI)の新たな定義を提案し、再定義されたAoIに基づいて、MECシステムにおけるオンラインAoI問題を定式化する。
本稿では,システム力学の部分的知識を活用するために,PDS(Post-Decision State)を導入する。
また、PSDと深いRLを組み合わせることで、アルゴリズムの適用性、スケーラビリティ、堅牢性をさらに向上します。
論文 参考訳(メタデータ) (2023-12-01T01:30:49Z) - A Reinforcement Learning Approach for Scheduling Problems With Improved
Generalization Through Order Swapping [0.0]
JSSP は NP-hard COP のカテゴリに分類される。
近年,COPの解法にDRLを用いる研究が注目され,解の質や計算効率の面で有望な結果が示されている。
特に、制約されたジョブのディスパッチにおいてよく機能すると考えられるポリシ・グラディエントパラダイムを採用するPPOアルゴリズムを採用する。
論文 参考訳(メタデータ) (2023-02-27T16:45:04Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。
我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。
我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
論文 参考訳(メタデータ) (2023-02-02T18:27:20Z) - HARL: Hierarchical Adaptive Reinforcement Learning Based Auto Scheduler
for Neural Networks [51.71682428015139]
効率的なテンソルプログラム探索のための強化学習に基づく自動スケジューリングシステムであるHARLを提案する。
HarLは、最先端のオートスケジューラと比較して、テンソル演算子の性能を22%改善し、探索速度を4.3倍改善する。
また、エンドツーエンドのニューラルネットワークでは、推論性能と探索速度も大幅に向上する。
論文 参考訳(メタデータ) (2022-11-21T04:15:27Z) - 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) - Semantic-Aware Collaborative Deep Reinforcement Learning Over Wireless
Cellular Networks [82.02891936174221]
複数のエージェントが無線ネットワーク上で協調できるコラボレーティブディープ強化学習(CDRL)アルゴリズムは有望なアプローチである。
本稿では,リソース制約のある無線セルネットワーク上で,意味的にリンクされたDRLタスクを持つ未学習エージェントのグループを効率的に協調させる,新しい意味認識型CDRL手法を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:24:47Z) - An actor-critic algorithm with policy gradients to solve the job shop
scheduling problem using deep double recurrent agents [1.3812010983144802]
ジョブショップスケジューリング問題(JSSP)に対する深層強化学習手法を提案する。
目的は、ジョブやマシンの数によって異なるJSSPインスタンスのディストリビューションについて学べるgreedyのようなものを構築することである。
予想通り、モデルはある程度は、トレーニングで使用されるものと異なる分布から生じるより大きな問題やインスタンスに一般化することができる。
論文 参考訳(メタデータ) (2021-10-18T07:55:39Z) - Learning Enhanced Optimisation for Routing Problems [3.747361228408185]
L2GLS(Learning to Guide Local Search)は、ルーティング問題に対する学習ベースのアプローチである。
L2GLSは、局所探索(LS)演算子の強度とペナルティ項を組み合わせ、局所最適から逃れる。
L2GLSは、他の機械学習手法よりも大きなTSPとCVRPに対して、最先端の新たな結果が得られることを示す。
論文 参考訳(メタデータ) (2021-09-17T04:47:26Z) - CATCH: Context-based Meta Reinforcement Learning for Transferrable
Architecture Search [102.67142711824748]
CATCHは、転送可能なarChitecture searcHのための、Context-bAsed meTa強化学習アルゴリズムである。
メタラーニングとRLの組み合わせにより、CATCHは検索空間に依存しないまま、新しいタスクに効率的に適応できる。
また、ImageNet、COCO、Cityscapesの競合ネットワークとしてクロスドメインアーキテクチャサーチを扱うこともできる。
論文 参考訳(メタデータ) (2020-07-18T09:35:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。