論文の概要: 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方式が生産プラントの制御装置に実装されている。

関連論文リスト

• Benchmarking Agentic Workflow Generation [80.74757493266057]
  複数面シナリオと複雑なグラフワークフロー構造を備えた統合ワークフロー生成ベンチマークであるWorFBenchを紹介する。 また,サブシーケンスとサブグラフマッチングアルゴリズムを利用したシステム評価プロトコルWorFEvalを提案する。 我々は、生成されたタスクが下流のタスクを強化し、推論中により少ない時間で優れたパフォーマンスを達成することができることを観察する。
  論文  参考訳（メタデータ） (2024-10-10T12:41:19Z)
• Optimizing Agricultural Order Fulfillment Systems: A Hybrid Tree Search Approach [1.1470070927586018]
  効率的なオーダーフルフィルメントは、特に種子サプライチェーンの季節的性質のため、農業において不可欠である。 本稿では, 受注を波動で処理する集中型倉庫において, 種子の受注を最適化する課題について述べる。 モンテカルロ木探索とドメイン固有知識を組み合わせた適応型ハイブリッド木探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-19T01:25:39Z)
• 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)
• Faithful Question Answering with Monte-Carlo Planning [78.02429369951363]
  本稿では,FAME(Fithful Questioning with Monte-carlo planning)を提案する。 我々は,タスクを離散的な意思決定問題として定式化し,推論環境とコントローラの相互作用によって解決する。 FAMEは標準ベンチマークで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2023-05-04T05:21:36Z)
• A Memetic Algorithm with Reinforcement Learning for Sociotechnical Production Scheduling [0.0]
  本稿では、フレキシブルジョブショップスケジューリング問題(DRC-FJSSP)に深層強化学習(DRL)を適用したメメティックアルゴリズムを提案する。 産業における研究プロジェクトから、フレキシブルマシン、フレキシブルなヒューマンワーカー、作業能力、セットアップと処理操作、材料到着時間、材料製造の請求書の並列タスク、シーケンス依存のセットアップ時間、人間と機械のコラボレーションにおける(一部)自動化タスクを検討する必要性を認識します。
  論文  参考訳（メタデータ） (2022-12-21T11:24:32Z)
• Deploying a Steered Query Optimizer in Production at Microsoft [10.647568709854877]
  我々は、与えられたワークロードのより良い計画に向けてクエリを操縦し、以前の研究アイデアを本番環境に推し進めるという、最近の取り組みを続けています。 ステアリングアクションをより管理可能にすること、ステアリングのコストを予算内で維持すること、製品のパフォーマンスの予期せぬ低下を避けることなどです。 私たちのシステムであるQQ-advisorは、クエリプランナを大規模なオフラインパイプラインに外部化して、より優れた探索と特殊化を実現します。
  論文  参考訳（メタデータ） (2022-10-24T21:57:57Z)
• 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)

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

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