論文の概要: Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem

• arxiv url: http://arxiv.org/abs/2501.17991v1
• Date: Wed, 29 Jan 2025 20:55:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:14:22.199722
• Title: Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
• Title（参考訳）: ジョブショップスケジューリング問題に対するモンテカルロ木探索手法の検討
• Authors: Laurie Boveroux, Damien Ernst, Quentin Louveaux,
• Abstract要約: ジョブショップスケジューリング問題(JSSP、Job Shop Scheduling Problem)は製造業における最適化問題であり、目的は、与えられた目的を最小化するために、異なるマシンにわたるジョブの最適なシーケンスを決定することである。 重み付き強化学習技術であるモンテカルロ木探索 (MCTS) の大規模JSSP, 特に循環障害の解決の可能性について検討する。 MCTSアルゴリズムのJSSPをモデル化するためのマルコフ決定過程 (MDP) の定式化を提案する。 さらに我々は,大規模で非矩形なインスタンスの複雑さをしばしばキャプチャする,実生産データから得られた新しい合成ベンチマークを導入する。
• 参考スコア（独自算出の注目度）: 1.9171404264679484
• License:
• Abstract: The Job Shop Scheduling Problem (JSSP) is a well-known optimization problem in manufacturing, where the goal is to determine the optimal sequence of jobs across different machines to minimize a given objective. In this work, we focus on minimising the weighted sum of job completion times. We explore the potential of Monte Carlo Tree Search (MCTS), a heuristic-based reinforcement learning technique, to solve large-scale JSSPs, especially those with recirculation. We propose several Markov Decision Process (MDP) formulations to model the JSSP for the MCTS algorithm. In addition, we introduce a new synthetic benchmark derived from real manufacturing data, which captures the complexity of large, non-rectangular instances often encountered in practice. Our experimental results show that MCTS effectively produces good-quality solutions for large-scale JSSP instances, outperforming our constraint programming approach.
• Abstract（参考訳）: ジョブショップスケジューリング問題(JSSP、Job Shop Scheduling Problem)は製造業においてよく知られた最適化問題である。 本研究では,仕事完了時間の重み付けを最小化することに集中する。 我々は, 大規模JSSP, 特に循環障害のある人を対象に, ヒューリスティックな強化学習手法であるモンテカルロ木探索(MCTS)の可能性を探る。 MCTSアルゴリズムのJSSPをモデル化するためのマルコフ決定過程 (MDP) の定式化を提案する。 さらに,実際の製造データから得られた新しい合成ベンチマークを導入し,実際にしばしば発生する大規模で非矩形なインスタンスの複雑さを捉えた。 実験の結果,MCTSは大規模JSSPインスタンスの良質なソリューションを効果的に生成し,制約プログラミング手法よりも優れていることがわかった。

関連論文リスト

• Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
  ジョブショップスケジューリング問題(JSSP、Job-Shop Scheduling Problem)は、タスクをマシン上でスケジュールする必要がある最適化問題である。 本稿では,Dreep Reinforcement Learning (DRL) 技術を利用してロバストなソリューションを探索する手法を提案する。
  論文  参考訳（メタデータ） (2024-03-04T08:38:55Z)
• Let's reward step by step: Step-Level reward model as the Navigators for Reasoning [64.27898739929734]
  Process-Supervised Reward Model (PRM)は、トレーニングフェーズ中にステップバイステップのフィードバックをLLMに提供する。 LLMの探索経路を最適化するために,PRMからのステップレベルのフィードバックを応用した欲求探索アルゴリズムを提案する。 提案手法の汎用性を探るため,コーディングタスクのステップレベル報酬データセットを自動生成する手法を開発し,コード生成タスクにおける同様の性能向上を観察する。
  論文  参考訳（メタデータ） (2023-10-16T05:21:50Z)
• 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)
• Monte-Carlo Tree-Search for Leveraging Performance of Blackbox Job-Shop Scheduling Heuristics [1.3764085113103217]
  製造では、しばしば既製の製造ラインで生産される。 我々は、ブラックボックスのジョブショップシステムと、ブラックボックスのジョブショップのジョブを所定の順にスケジュールする未知のスケジューリングシステムによる、そのような設定について検討する。 ここでは、ジョブは、置換の所定の順序でジョブショップに入る必要があるが、ブラックボックスに依存するジョブショップ内で異なる経路を取る可能性がある。
  論文  参考訳（メタデータ） (2022-12-14T23:01:53Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。 最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。 本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-30T17:59:16Z)
• 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)
• Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
  我々は、専門家ベースのシミュレータを使用し、MCTSのデフォルトポリシーを適用して製造プロセスに対処する。 一般的な理由は、プロセスの効率的なシミュレータが存在しないことや、MCTSをプロセスの複雑な規則に適用する際の問題があることである。
  論文  参考訳（メタデータ） (2021-07-28T14:56:17Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  マルコフ決定過程における計画のための新しいトラジェクトリに基づくモンテカルロ木探索アルゴリズム MDP-GapE を提案する。 我々は, MDP-GapE に要求される生成モデルに対する呼び出し回数の上限を証明し, 確率の高い準最適動作を同定する。
  論文  参考訳（メタデータ） (2020-06-10T15:05:51Z)

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

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