論文の概要: Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem

• arxiv url: http://arxiv.org/abs/2309.15517v1
• Date: Wed, 27 Sep 2023 09:33:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-28 14:34:56.310534
• Title: Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem
• Title（参考訳）: 残留スケジューリング: ジョブショップスケジューリング問題を解決するための新しい強化学習アプローチ
• Authors: Kuo-Hao Ho, Ruei-Yu Jheng, Ji-Han Wu, Fan Chiang, Yen-Chi Chen, Yuan-Yu Wu, I-Chen Wu
• Abstract要約: ジョブショップスケジューリング問題(Job-shop scheduling problem、JSP)は、製造業などで広く使われている数学最適化問題である。 本稿では,FJSPの解法に対する残差スケジューリングという新しい手法を提案する。 20台のマシンで150以上のジョブ数を持つ50のインスタンスで49のギャップに到達しています。
• 参考スコア（独自算出の注目度）: 8.398387430247201
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Job-shop scheduling problem (JSP) is a mathematical optimization problem widely used in industries like manufacturing, and flexible JSP (FJSP) is also a common variant. Since they are NP-hard, it is intractable to find the optimal solution for all cases within reasonable times. Thus, it becomes important to develop efficient heuristics to solve JSP/FJSP. A kind of method of solving scheduling problems is construction heuristics, which constructs scheduling solutions via heuristics. Recently, many methods for construction heuristics leverage deep reinforcement learning (DRL) with graph neural networks (GNN). In this paper, we propose a new approach, named residual scheduling, to solving JSP/FJSP. In this new approach, we remove irrelevant machines and jobs such as those finished, such that the states include the remaining (or relevant) machines and jobs only. Our experiments show that our approach reaches state-of-the-art (SOTA) among all known construction heuristics on most well-known open JSP and FJSP benchmarks. In addition, we also observe that even though our model is trained for scheduling problems of smaller sizes, our method still performs well for scheduling problems of large sizes. Interestingly in our experiments, our approach even reaches zero gap for 49 among 50 JSP instances whose job numbers are more than 150 on 20 machines.
• Abstract（参考訳）: ジョブショップスケジューリング問題(JSP)は製造業などで広く用いられている数学最適化問題であり、フレキシブルJSP(FJSP)も一般的な変種である。 NPハードであるため、すべてのケースに対して妥当な時間内に最適解を見つけることは困難である。 したがって、JSP/FJSPを解くための効率的なヒューリスティックを開発することが重要である。 スケジューリング問題の解法の一種は、ヒューリスティックスによってスケジューリングソリューションを構築する構成ヒューリスティックスである。 近年,グラフニューラルネットワーク (gnn) を用いた深層強化学習 (drl) の活用方法が数多く提案されている。 本稿では,JSP/FJSPを解くための残差スケジューリング手法を提案する。 この新しいアプローチでは、状態が残りの(または関連する)マシンとジョブのみを含むように、完了したマシンのような無関係なマシンとジョブを削除する。 我々の実験は、最もよく知られたオープンJSPおよびFJSPベンチマークにおけるすべての建設ヒューリスティックの中で、我々のアプローチが最先端(SOTA)に達することを示している。 また,本手法は小型のスケジューリング問題に対して訓練されているものの,大規模のスケジューリング問題においても有効であることも確認した。 興味深いことに、私たちの実験では、20台のマシンで150以上のジョブ番号を持つ50のjspインスタンスのうち49のギャップに到達しました。

関連論文リスト

• Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
  ジョブショップスケジューリング問題(JSSP、Job-Shop Scheduling Problem)は、タスクをマシン上でスケジュールする必要がある最適化問題である。 本稿では,Dreep Reinforcement Learning (DRL) 技術を利用してロバストなソリューションを探索する手法を提案する。
  論文  参考訳（メタデータ） (2024-03-04T08:38:55Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。 近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。 本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-09T01:35:48Z)
• 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)
• 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)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• 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)
• Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method [44.4747903763245]
  ジョブショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準最適化問題である。 問題はNPハードであり、中規模のインスタンスでも計算が困難である。 本稿では,問題に対する効率的かつ正確な近似を提供するためのディープラーニングアプローチについて検討する。
  論文  参考訳（メタデータ） (2021-10-12T21:15:19Z)
• Solving the Extended Job Shop Scheduling Problem with AGVs -- Classical and Quantum Approaches [0.0]
  本稿では、ジョブショップスケジューリング問題(JSSP)であるJSOのサブアスペクトを扱うユースケースを提供する。 ユースケースの目標は、柔軟な組織化された機械で、特定のプロジェクトのために最適化されたデューティルースターを作成する方法を示すことである。 CPとアナリングモデルに基づく古典解の結果を提示し、議論する。
  論文  参考訳（メタデータ） (2021-09-10T12:28:51Z)
• 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)

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

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