論文の概要: Petri Net Induced Heuristic Search for Resource Constrained Scheduling
- arxiv url: http://arxiv.org/abs/2605.15983v1
- Date: Fri, 15 May 2026 14:15:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.312068
- Title: Petri Net Induced Heuristic Search for Resource Constrained Scheduling
- Title（参考訳）: ペトリネットによる資源制約スケジューリングのためのヒューリスティック探索
- Authors: Ido Lublin, Dor Atzmon, Izack Cohen,
- Abstract要約: 本稿では資源制約付きプロジェクトスケジューリング問題(RCPSP)を時間遷移ペトリネットの到達可能性グラフ上の最適探索として定式化する。
我々は、クリティカルパスとリソースベースの下限を組み合わせた仲介によって導かれる$A*$の問題を解く。
- 参考スコア（独自算出の注目度）: 1.6047175421546533
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We formulate the Resource-Constrained Project Scheduling Problem (RCPSP) as optimal search over the reachability graph of a Timed Transition Petri Net with Resources, using relative-delay tokens so that scheduling decisions correspond to transition firings in the induced state space. We solve the resulting problem with $A^*$ guided by a heuristic that combines Critical Path and resource-based lower bounds, and prove that it is consistent under our token-based time semantics. Experiments on the PSPLIB benchmarks show that the approach outperforms strong exact Mixed-Integer Linear Programming (MIP) baselines (SCIP, CBC) in both success rate and solve time. Per-instance analysis shows that heuristic search and MIP degrade along independent axes, resource tightness for $A^*$ and formulation size for MIP, with resource strength mediating which solver benefits from scale.
- Abstract（参考訳）: 本稿では、資源制約付きプロジェクトスケジューリング問題(RCPSP)を、相対遅延トークンを用いてリソース付きタイムトトランジションペトリネットの到達可能性グラフ上の最適探索として定式化し、スケジュール決定が誘導状態空間の遷移焼成に対応するようにした。
我々は、クリティカルパスとリソースベースの下限を組み合わせたヒューリスティックによって導かれる$A^*$の問題を解決し、トークンベースの時間意味論の下で一貫性があることを証明する。
PSPLIBベンチマークの実験では、この手法は成功率と解時間の両方で、MIP(Mixed-Integer Linear Programming)ベースライン(SCIP, CBC)よりも優れていることが示された。
Per-instance Analysisによると、ヒューリスティックサーチとMIPは独立した軸に沿って劣化し、A^*$のリソースタイトネスとMIPの定式化サイズはスケールから恩恵を受けるリソース強度を仲介する。
関連論文リスト
- ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
ODAR-Expertは、原則化されたリソース割り当てによる精度と効率のトレードオフを最適化する適応的なルーティングフレームワークである。
我々は、MATHの98.2%の精度、HumanityのLast Examの54.8%を含む、強く一貫した利得を示している。
論文 参考訳（メタデータ） (2026-02-27T05:22:01Z) - $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
$textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。
我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
論文 参考訳（メタデータ） (2025-06-15T05:50:05Z) - Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。
このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
論文 参考訳（メタデータ） (2024-06-12T06:41:47Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process [4.685121820790546]
マルコフ決定過程(CMDP)の強化学習問題について考察する。
これは$O(frac1Deltacdotepsiloncdotlog2(1/epsilon))$ sample complexity boundとなる。
本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
論文 参考訳（メタデータ） (2024-02-26T06:08:25Z) - Langevin Thompson Sampling with Logarithmic Communication: Bandits and
Reinforcement Learning [34.4255062106615]
トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。
バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。
アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
論文 参考訳（メタデータ） (2023-06-15T01:16:29Z) - Learning to Schedule Heuristics for the Simultaneous Stochastic
Optimization of Mining Complexes [2.538209532048867]
提案したL2P(Learning-to-perturb)ハイパーヒューリスティックは,マルチ隣り合うシミュレートアニールアルゴリズムである。
L2Pは、効率、堅牢性、一般化能力に重点を置いて、いくつかの実世界の鉱業施設で試験されている。
その結果,反復回数を30～50%削減し,計算時間を30～45%削減した。
論文 参考訳（メタデータ） (2022-02-25T18:20:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。