論文の概要: Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing
- arxiv url: http://arxiv.org/abs/2609.00004v1
- Date: Sun, 05 Jul 2026 23:37:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.418198
- Title: Discrete-Time MDP Modeling for Multi-Item Capacitated Lot Sizing with Stochastic Demand Timing
- Title（参考訳）: 確率的需要タイミングを考慮した複数項目容量ロットサイズに対する離散時間MDPモデリング
- Abstract要約: 本稿では,需要量が決定論的である有限ホライズン多面体キャパシタン化ロットサイズ問題について検討する。
提案モデルでは,需要レベルの生産・配分決定を行い,キャパシティ競争,需要固有のバックログ,アロケーションに依存した在庫動態を表現できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a finite-horizon multi-item capacitated lot-sizing problem in which demand quantities are deterministic, while demand-arrival periods are stochastic. Each demand occurs once within a known time window and must be satisfied no later than its deadline. The proposed model makes production and allocation decisions at the demand level, allowing it to represent capacity competition, demand-specific backlog, and allocation-dependent inventory dynamics. The stochastic problem is formulated as a discrete-time Markov decision process (DTMDP), including the state space, feasible actions, transition kernel, and one-period cost function. To isolate the computational effect of stochastic timing, each stochastic instance is first compared with a deterministic counterpart in which each arrival distribution is replaced by its most likely arrival period. This comparison shows that stochastic timing substantially increases the number of states, the number of transitions, solution time, and memory pressure. A genetic algorithm (GA) is then proposed for the stochastic-timing problem. The GA searches over feasible state-feedback policies and evaluates each policy exactly under the DTMDP transition model. Computational experiments on 330 benchmark instances show that the GA remains close to the exact stochastic solution whenever the latter is available, with an average optimality gap of about $3.44\%$. On the difficult benchmark instances, comprising 90 test cases, the GA remains below the $5\%$ optimality-gap threshold and achieves an average optimization speedup of $6.89 \pm 1.41$ at the $95\%$ confidence level. For instances that cannot be solved exactly on the available hardware, an empirical Bellman-time regression is used to estimate the missing exact resolution time and extrapolate the expected GA speedup.
- Abstract（参考訳）: 本稿では,需要量が決定論的である有限ホライズン多面体キャパシタン化ロットサイズ問題について検討する。
各要求は、既知のタイムウィンドウ内で一度発生し、その期限までに満たされなければならない。
提案モデルでは,需要レベルの生産・配分決定を行い,キャパシティ競争,需要固有のバックログ,アロケーションに依存した在庫動態を表現できる。
確率問題は、状態空間、実行可能な動作、遷移カーネル、一周期コスト関数を含む離散時間マルコフ決定過程(DTMDP)として定式化される。
確率的タイミングの計算効果を分離するために、各確率的インスタンスをまず、各到着分布を最も起こりそうな到着周期に置き換える決定論的インスタンスと比較する。
この比較は、確率的タイミングが状態数、遷移数、解時間、記憶圧を大幅に増加させることを示している。
遺伝的アルゴリズム (GA) は確率的タイミング問題に対して提案される。
GAは、実現可能な状態フィードバックポリシーを探索し、それぞれのポリシーをDTMDPトランジションモデルの下で正確に評価する。
330ベンチマークインスタンスの計算実験によると、GAは後者が利用可能であればいつでも正確な確率解に近づき、平均最適性ギャップは約3.44 %$である。
90のテストケースからなる難しいベンチマークインスタンスでは、GAは5\%$Optimity-gapしきい値以下に留まり、平均最適化速度は9,5\%$信頼性レベルで6.89 \pm 1.41$に達する。
利用可能なハードウェアで正確に解決できないインスタンスに対しては、経験的なベルマン時間回帰を用いて、未解決の正確な解像度時間を推定し、予測されたGAスピードアップを外挿する。
関連論文リスト
- SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。
SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。
オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
論文 参考訳（メタデータ） (2026-01-04T04:52:11Z) - ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
ZIP-RCは、モデルに報酬とコストのゼロオーバーヘッド推論時間予測を持たせる適応推論手法である。
ZIP-RCは、同じまたはより低い平均コストで過半数投票よりも最大12%精度が向上する。
論文 参考訳（メタデータ） (2025-12-01T09:44:31Z) - Monitoring State Transitions in Markovian Systems with Sampling Cost [65.4151496405543]
自然なアプローチは、予想される予測損失がクエリコスト以下で、クエリがなければいつ発生するかを予測する、欲張りのポリシーである。
最適(OPT)戦略は状態依存のしきい値ポリシである。
遷移確率が未知の場合、我々は、グレディポリシーの予測勾配降下(PSGD)に基づく学習変種を提案する。
論文 参考訳（メタデータ） (2025-10-25T15:07:37Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times [49.1574468325115]
最適勾配を計算できる複数の並列作業者の設定において、滑らかな非関数の期待を最小化する問題について検討する。
この文脈における課題は、任意に不均一で分散された計算時間の存在である。
本稿では,このギャップに対処する新しい並列SGD法であるMindFlayer SGDを紹介する。
論文 参考訳（メタデータ） (2024-10-05T21:11:32Z) - Solution Path of Time-varying Markov Random Fields with Discrete
Regularization [7.79230326339002]
本研究では,時間変化確率場(MRF)をパラメータの離散的および時間的正規化で推定する問題について検討する。
すべての空間レベルの解は$mathcalO(Tp3)$で得られ、$T$は時間ステップの数、$p$は任意の時間における未知のパラメータの数である。
論文 参考訳（メタデータ） (2023-07-25T18:19:50Z) - Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。
動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。
提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
論文 参考訳（メタデータ） (2023-06-05T03:57:16Z) - Preconditioned Score-based Generative Models [45.66744783988319]
直感的な加速度法はサンプリングの繰り返しを減らし、しかしながら重大な性能劣化を引き起こす。
本稿では,行列プレコンディショニングを利用して上記の問題を緩和する新しいプリコンディショニング拡散サンプリング法を提案する。
PDSはSGMの出力分布を保ち、元のサンプリングプロセスに系統的バイアスを引き起こすリスクはない。
論文 参考訳（メタデータ） (2023-02-13T16:30:53Z) - Optimal Admission Control for Multiclass Queues with Time-Varying
Arrival Rates via State Abstraction [16.99621896314678]
我々は、意思決定者がランダムに到着したタスクを受け入れ、拒否する必要があるという、新しいキュー問題を考える。
目的は、処理されたタスクの総価格が有限の地平線上で最大になるように、どのタスクを受け入れるかを決定することである。
最適値関数は特定の構造を持ち、ハイブリッドMDPを正確に解くことができることを示す。
論文 参考訳（メタデータ） (2022-03-14T12:38:13Z) - Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in
the Presence of Stragglers [31.309253646602933]
我々は、マスターが分散勾配降下(SGD)アルゴリズムを、データのサブセットを持つそれぞれ$n$ワーカー上で実行したいという設定について検討する。
分散SGDは、遅延を引き起こす遅い作業者や非応答的な作業者など、ストラグラーの影響に悩まされることがある。
本稿では,統計的概念に基づく適応分散SGDのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-25T16:25:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。