論文の概要: Monte-Carlo Tree-Search for Leveraging Performance of Blackbox Job-Shop Scheduling Heuristics

• arxiv url: http://arxiv.org/abs/2212.07543v1
• Date: Wed, 14 Dec 2022 23:01:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-16 17:37:33.159253
• Title: Monte-Carlo Tree-Search for Leveraging Performance of Blackbox Job-Shop Scheduling Heuristics
• Title（参考訳）: ブラックボックスジョブショップスケジューリングヒューリスティックスの性能向上のためのモンテカルロ木探索
• Authors: Florian Wimmenauer, Mat\'u\v{s} Mihal\'ak, Mark H. M. Winands
• Abstract要約: 製造では、しばしば既製の製造ラインで生産される。 我々は、ブラックボックスのジョブショップシステムと、ブラックボックスのジョブショップのジョブを所定の順にスケジュールする未知のスケジューリングシステムによる、そのような設定について検討する。 ここでは、ジョブは、置換の所定の順序でジョブショップに入る必要があるが、ブラックボックスに依存するジョブショップ内で異なる経路を取る可能性がある。
• 参考スコア（独自算出の注目度）: 1.3764085113103217
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In manufacturing, the production is often done on out-of-the-shelf manufacturing lines, whose underlying scheduling heuristics are not known due to the intellectual property. We consider such a setting with a black-box job-shop system and an unknown scheduling heuristic that, for a given permutation of jobs, schedules the jobs for the black-box job-shop with the goal of minimizing the makespan. Here, the jobs need to enter the job-shop in the given order of the permutation, but may take different paths within the job shop, which depends on the black-box heuristic. The performance of the black-box heuristic depends on the order of the jobs, and the natural problem for the manufacturer is to find an optimum ordering of the jobs. Facing a real-world scenario as described above, we engineer the Monte-Carlo tree-search for finding a close-to-optimum ordering of jobs. To cope with a large solutions-space in planning scenarios, a hierarchical Monte-Carlo tree search (H-MCTS) is proposed based on abstraction of jobs. On synthetic and real-life problems, H-MCTS with integrated abstraction significantly outperforms pure heuristic-based techniques as well as other Monte-Carlo search variants. We furthermore show that, by modifying the evaluation metric in H-MCTS, it is possible to achieve other optimization objectives than what the scheduling heuristics are designed for -- e.g., minimizing the total completion time instead of the makespan. Our experimental observations have been also validated in real-life cases, and our H-MCTS approach has been implemented in a production plant's controller.
• Abstract（参考訳）: 製造では、しばしば既製の製造ラインで生産されるが、その基礎となるスケジューリングのヒューリスティックは知的財産のために分かっていない。 ブラックボックスのジョブショップシステムと未知のスケジューリングヒューリスティックを用いて、所定のジョブの順応に対して、ブラックボックスのジョブショップのジョブを、メースパンの最小化を目標としてスケジュールする。 ここでは、ジョブは置換の所定の順序でジョブショップに入る必要があるが、ブラックボックスのヒューリスティックに依存するジョブショップ内で異なる経路を取る可能性がある。 ブラックボックスヒューリスティックのパフォーマンスは、ジョブの順序に依存し、製造業者にとっての自然な問題は、ジョブの最適な順序を見つけることである。 先述したような現実のシナリオに直面して,ジョブのクローズ・トゥ・オプティマイムの順序を求めるモンテカルロ木探索を考案した。 計画シナリオにおける大規模解空間に対処するために,ジョブの抽象化に基づく階層的モンテカルロ木探索(h-mcts)を提案する。 合成問題と実生活問題において、H-MCTSと統合された抽象化は、純粋ヒューリスティックに基づく技術とモンテカルロ探索の変種を著しく上回る。 さらに、H-MCTSの評価基準を変更することで、スケジューリングヒューリスティックが設計したもの(例えば、メースパンの代わりに総完了時間を最小化するなど)よりも、他の最適化目標を達成することができることを示す。 実例においても実験結果が検証され,H-MCTS方式が生産プラントの制御装置に実装されている。

関連論文リスト

• Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization [7.755152930120769]
  ヒューリスティックス計画(英: Planning of Heuristics、PoH)は、LCMの自己反射とモンテカルロ木探索(MCTS)を統合する最適化手法である。 PoHは、そのパフォーマンスを評価し、即効的な提案を提供することによって、生成された計画を反復的に洗練します。
  論文  参考訳（メタデータ） (2025-02-17T04:35:01Z)
• Monte Carlo Tree Diffusion for System 2 Planning [57.50512800900167]
  モンテカルロ木探索(MCTS)の適応探索機能と拡散モデルの生成強度を統合する新しいフレームワークであるモンテカルロ木拡散(MCTD)を紹介する。 MCTDは拡散フレームワーク内での探索・探索トレードオフの制御などのMCTSの利点を享受する。
  論文  参考訳（メタデータ） (2025-02-11T02:51:42Z)
• Lipschitz Lifelong Monte Carlo Tree Search for Mastering Non-Stationary Tasks [19.42056439537988]
  モンテカルロ木探索(MCTS)を用いたLipschitz生涯計画のためのLiZeroについて述べる。 本稿では,ソースタスクから新しいタスクの探索・探索へ知識を伝達するための適応UCT(aUCT)の概念を提案する。 実験の結果,LiZeroは既存のMCTSや生涯学習ベースラインよりはるかに優れており,最適報酬への収束がはるかに速いことがわかった。
  論文  参考訳（メタデータ） (2025-02-02T02:45:20Z)
• Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem [1.9171404264679484]
  ジョブショップスケジューリング問題(JSSP、Job Shop Scheduling Problem)は製造業における最適化問題であり、目的は、与えられた目的を最小化するために、異なるマシンにわたるジョブの最適なシーケンスを決定することである。 重み付き強化学習技術であるモンテカルロ木探索 (MCTS) の大規模JSSP, 特に循環障害の解決の可能性について検討する。 MCTSアルゴリズムのJSSPをモデル化するためのマルコフ決定過程 (MDP) の定式化を提案する。 さらに我々は,大規模で非矩形なインスタンスの複雑さをしばしばキャプチャする,実生産データから得られた新しい合成ベンチマークを導入する。
  論文  参考訳（メタデータ） (2025-01-29T20:55:53Z)
• Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design [33.58608225370497]
  大規模言語モデル (LLM) に基づく自動設計 (AHD) 手法は、手作業による介入なしに高品質な設計を作成することを約束している。 本稿では,進化進化にモンテカルロ木探索(MCTS)を用いることを提案する。
  論文  参考訳（メタデータ） (2025-01-15T06:00:50Z)
• Benchmarking Agentic Workflow Generation [80.74757493266057]
  複数面シナリオと複雑なグラフワークフロー構造を備えた統合ワークフロー生成ベンチマークであるWorFBenchを紹介する。 また,サブシーケンスとサブグラフマッチングアルゴリズムを利用したシステム評価プロトコルWorFEvalを提案する。 我々は、生成されたタスクが下流のタスクを強化し、推論中により少ない時間で優れたパフォーマンスを達成することができることを観察する。
  論文  参考訳（メタデータ） (2024-10-10T12:41:19Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。 我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。 ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
  論文  参考訳（メタデータ） (2024-02-29T15:36:01Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Plannerは、大きな言語モデルでタスクプランニングを3つの異なるフェーズに再構成する。 Tree-Plannerは高い効率を維持しながら最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-10-12T17:59:50Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。 並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
  論文  参考訳（メタデータ） (2022-10-04T07:34:06Z)
• Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
  我々は、専門家ベースのシミュレータを使用し、MCTSのデフォルトポリシーを適用して製造プロセスに対処する。 一般的な理由は、プロセスの効率的なシミュレータが存在しないことや、MCTSをプロセスの複雑な規則に適用する際の問題があることである。
  論文  参考訳（メタデータ） (2021-07-28T14:56:17Z)

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

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