論文の概要: Exact and Metaheuristic Approaches for the Production Leveling Problem
- arxiv url: http://arxiv.org/abs/2006.08731v1
- Date: Mon, 15 Jun 2020 20:04:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 04:43:33.742327
- Title: Exact and Metaheuristic Approaches for the Production Leveling Problem
- Title（参考訳）: 生産水準問題に対する厳密かつメタヒューリスティックなアプローチ
- Authors: Johannes Vass, Marie-Louise Lackner, Nysret Musliu
- Abstract要約: 本稿では,生産水準問題(Product Leveling Problem)と呼ぶ生産計画分野における新たな問題を紹介する。
タスクは、各期間の負荷と各生産資源のバランスが取れ、容量制限が越えられず、注文の優先順位が考慮されるように、生産期間に注文を割り当てることである。
問題の公式モデルを提案し、Bin Backingからの還元によりNP硬度を示す。
- 参考スコア（独自算出の注目度）: 5.510992382274775
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we introduce a new problem in the field of production planning
which we call the Production Leveling Problem. The task is to assign orders to
production periods such that the load in each period and on each production
resource is balanced, capacity limits are not exceeded and the orders'
priorities are taken into account. Production Leveling is an important
intermediate step between long-term planning and the final scheduling of orders
within a production period, as it is responsible for selecting good subsets of
orders to be scheduled within each period.
A formal model of the problem is proposed and NP-hardness is shown by
reduction from Bin Backing. As an exact method for solving moderately sized
instances we introduce a MIP formulation. For solving large problem instances,
metaheuristic local search is investigated. A greedy heuristic and two
neighborhood structures for local search are proposed, in order to apply them
using Variable Neighborhood Descent and Simulated Annealing. Regarding exact
techniques, the main question of research is, up to which size instances are
solvable within a fixed amount of time. For the metaheuristic approaches the
aim is to show that they produce near-optimal solutions for smaller instances,
but also scale well to very large instances.
A set of realistic problem instances from an industrial partner is
contributed to the literature, as well as random instance generators. The
experimental evaluation conveys that the proposed MIP model works well for
instances with up to 250 orders. Out of the investigated metaheuristic
approaches, Simulated Annealing achieves the best results. It is shown to
produce solutions with less than 3% average optimality gap on small instances
and to scale well up to thousands of orders and dozens of periods and products.
The presented metaheuristic methods are already being used in the industry.
- Abstract（参考訳）: 本稿では,生産水準問題(Product Leveling Problem)と呼ぶ生産計画分野における新たな問題を紹介する。
タスクは、各期間の負荷と各生産資源のバランスが取れ、容量制限が越えられず、注文の優先順位が考慮されるように、生産期間に注文を割り当てることである。
生産レベル設定は、長期計画と生産期間内の注文の最終スケジューリングの間の重要な中間ステップであり、各期間内にスケジュールされる注文の優れたサブセットを選択する責任がある。
問題の公式モデルを提案し、Bin Backingからの還元によりNP硬度を示す。
適度なサイズのインスタンスを解くための正確な方法として、MIP定式化を導入する。
大きな問題を解くために,メタヒューリスティックな局所探索について検討した。
局所探索のためのグリーディ・ヒューリスティックと2つの近傍構造を提案し, 可変近傍DescentとSimulated Annealingを用いて適用した。
正確な技術については、どのサイズのインスタンスが一定時間以内に解決可能であるか、研究の主な疑問である。
メタヒューリスティックなアプローチでは、より小さなインスタンスに対してほぼ最適のソリューションを生成するが、非常に大きなインスタンスに対しては十分にスケールできることが示される。
産業パートナーによる現実的な問題インスタンスのセットは、ランダムなインスタンスジェネレータと同様に文献に貢献する。
実験の結果,最大250注文のインスタンスに対して提案したMIPモデルが有効であることがわかった。
研究したメタヒューリスティックアプローチのうち、シミュレート・アニーリングは最良の結果を得る。
小規模インスタンスの平均最適性ギャップが3%未満のソリューションを生成し、数千の注文と数十の期間と製品に十分にスケールできることが示されている。
提示されたメタヒューリスティックな手法は、すでに業界で使われている。
関連論文リスト
- MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。
MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。
また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
論文 参考訳（メタデータ） (2024-06-11T17:55:25Z) - Mixed-model Sequencing with Stochastic Failures: A Case Study for
Automobile Industry [0.0]
自動車業界では、製造日に先立って製造される車両の順序が決定される。
本稿では,製品故障に伴う混合モデルシークエンシング(MMS)問題に対する2段階プログラムを提案する。
論文 参考訳（メタデータ） (2023-06-22T01:09:18Z) - Leaving the Nest: Going Beyond Local Loss Functions for
Predict-Then-Optimize [57.22851616806617]
本手法は,文献から得られた4つの領域において,最先端の成果が得られることを示す。
提案手法は, 局所性仮定が破られた場合, 既存手法よりも200%近く性能が向上する。
論文 参考訳（メタデータ） (2023-05-26T11:17:45Z) - Concepts and Algorithms for Agent-based Decentralized and Integrated
Scheduling of Production and Auxiliary Processes [78.120734120667]
本稿ではエージェントベースの分散型統合スケジューリング手法について述べる。
要求の一部は、線形にスケールする通信アーキテクチャを開発することである。
このアプローチは、工業的要件に基づいた例を使って説明されます。
論文 参考訳（メタデータ） (2022-05-06T18:44:29Z) - Towards Standardizing Reinforcement Learning Approaches for Stochastic
Production Scheduling [77.34726150561087]
強化学習はスケジューリングの問題を解決するのに使える。
既存の研究は、コードが利用できない複雑なシミュレーションに依存している。
から選ぶべきRLの設計の広大な配列があります。
モデル記述の標準化 - 生産セットアップとRL設計の両方 - と検証スキームは前提条件です。
論文 参考訳（メタデータ） (2021-04-16T16:07:10Z) - Solving a Multi-resource Partial-ordering Flexible Variant of the
Job-shop Scheduling Problem with Hybrid ASP [0.4511923587827302]
我々は、MPF-JSS(Multi-resource Partial-ordering Flexible Job-shop Scheduling)問題を検討する。
リソースは柔軟性があり、その特性に応じて1つ以上の操作を実行できる。
中規模半導体故障解析ラボから抽出された一組のインスタンスについて実験した結果,本手法は実世界の91インスタンス中87のスケジュールを見出すことができた。
論文 参考訳（メタデータ） (2021-01-25T15:21:32Z) - Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
この実際のスケジューリング問題は、現代の印刷業界で現れたもので、シークエンシングの柔軟性を備えたフレキシブルなジョブショップスケジューリング問題に対応している。
この問題に対する局所探索戦略とメタヒューリスティックアプローチを提案し,評価した。
フレキシブルなジョブショップスケジューリング問題における古典的事例を用いた数値実験により,本事例に適用した場合,導入手法も競争力を持つことが示された。
論文 参考訳（メタデータ） (2020-06-22T15:38:00Z) - Exact and heuristic methods for the discrete parallel machine scheduling
location problem [0.0]
問題は、有限個の候補の中から$p$マシンの位置を選択し、これらのマシン上の一連のジョブをスケジューリングすることである。
広範囲な計算実験によって評価される新しいアークフロー定式化,列生成,3つの手順を提案する。
論文 参考訳（メタデータ） (2020-06-09T00:10:18Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z) - Improving a State-of-the-Art Heuristic for the Minimum Latency Problem
with Data Mining [69.00394670035747]
ハイブリッドメタヒューリスティックスは、オペレーション研究のトレンドとなっている。
成功例は、Greedy Randomized Adaptive Search Procedures (GRASP)とデータマイニング技術を組み合わせたものだ。
論文 参考訳（メタデータ） (2019-08-28T13:12:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。