論文の概要: Exact methods and lower bounds for the Oven Scheduling Problem

• arxiv url: http://arxiv.org/abs/2203.12517v1
• Date: Wed, 23 Mar 2022 16:28:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-24 16:30:07.390043
• Title: Exact methods and lower bounds for the Oven Scheduling Problem
• Title（参考訳）: オーブンスケジューリング問題に対する厳密な方法と下界
• Authors: Marie-Louise Lackner, Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz, Felix Winter
• Abstract要約: Oven Scheduling Problem (OSP) は、電子部品製造の領域で発生する新しい並列バッチスケジューリング問題である。 オーブンの実行はエネルギー集約性の高いため、時間内にジョブを終了する以外に、すべてのオーブンの累積バッチ処理時間を最小化することが主な目的である。 本稿では、制約計画法(CP)と整数線形計画法(ILP)とそれに対応するモデルを用いて、このNPハードスケジューリング問題を解決することを提案する。
• 参考スコア（独自算出の注目度）: 5.7485371212305685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding models. For an experimental evaluation, we introduce a multi-parameter random instance generator to provide a diverse set of problem instances. Using state-of-the-art solvers, we evaluate the quality and compare the performance of our CP- and ILP-models. We show that our models can find feasible solutions for instances of realistic size, many of those being provably optimal or nearly optimal solutions. Finally, we derive theoretical lower bounds on the solution cost of feasible solutions to the OSP; these can be computed within a few seconds. We show that these lower bounds are competitive with those derived by state-of-the-art solvers.
• Abstract（参考訳）: Oven Scheduling Problem (OSP) は、電子部品製造の領域で発生する新しい並列バッチスケジューリング問題である。 ジョブは複数のオーブンの1つにスケジュールされ、互換性のある要件があれば同時に1回のバッチで処理される。 ジョブのスケジューリングは、オーブンの適性と可用性、ジョブのリリース日、バッチ間のセットアップ時間、およびオーブン容量に関するいくつかの制約を尊重しなければならない。 オーブンの実行は非常にエネルギー集約的なため、ジョブを時間通りに終えることに加えて、オーブン全体の累積バッチ処理時間を最小化することが主な目的である。 この目的はOSPと他のバッチ処理の問題とを区別するが、これは通常、マシパン、重大さ、遅さに関連する目的を最小化する。 本稿では,制約プログラミング (cp) と整数線形計画 (ilp) によるnp-ハードスケジューリング問題の解法を提案し,対応するモデルを提案する。 実験的な評価のために,多パラメータランダムインスタンス生成器を導入し,多様な問題インスタンスを提供する。 そこで,最先端ソルバを用いて品質評価を行い,cpモデルとilpモデルの性能比較を行った。 我々のモデルは現実的なサイズのインスタンスに対して実現可能な解を見つけることができ、その多くが証明可能な最適解あるいはほぼ最適解であることを示す。 最後に、OSPに対する実現可能なソリューションのソリューションコストに関する理論的に低い境界を導出し、これらは数秒で計算できる。 これらの下限は最先端の解法で導かれる解法と競合していることを示す。

関連論文リスト

• Theoretical Lower Bounds for the Oven Scheduling Problem [6.144680854063938]
  問題の目的は、複数の要因を最小化しながら、オーブンに一連のジョブをスケジュールすることである。 効率的なスケジュールを得るための鍵は、バッチで互換性のあるジョブを同時に処理することだ。 我々はOSPの理論的、問題固有の下限を非常に高速に計算できるように開発する。
  論文  参考訳（メタデータ） (2024-10-02T09:30:01Z)
• 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)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  本稿では,ロボット推論と計画における連続的制約満足度問題(CCSP)の解法について紹介する。 対照的に、構成拡散連続制約解法(Diffusion-CCSP)は、CCSPに対する大域的な解を導出する。
  論文  参考訳（メタデータ） (2023-09-02T15:20:36Z)
• Constraint programming models for depth-optimal qubit assignment and SWAP-based routing [0.0]
  量子ビット割り当てとルーティング問題に対する制約プログラミング(CP)モデルを提案する。 回路深さ最小化のための整数線形プログラミング(ILP)モデルと比較する。 実験分析の結果,提案手法はソリューションの品質と実行時間の両方において,ILPモデルよりも優れていることがわかった。
  論文  参考訳（メタデータ） (2023-06-14T16:42:36Z)
• Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling [18.286430978487388]
  我々は、シーケンス依存のセットアップ時間とリリース日を持つ並列マシン上で、困難なスケジューリング問題に対処する。 個々のマシンを非到達順に配置し、結果として生じるロバスト性を語彙的に最小化する。 実験の結果,ASPは実際にこの問題に対して有望なKRRパラダイムであり,最先端のCPおよびMIPソルバと競合していることがわかった。
  論文  参考訳（メタデータ） (2022-12-18T12:43:24Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem [0.0]
  本稿では,資格制約のある並列マシン上での異なる家族のジョブのスケジューリングについて検討する。 目標は、フロー時間と不平等の数の両方を最小化することです。 本稿では,不等式が考慮されない単一機械緩和における流速を最小化する時間アルゴリズムを用いる。
  論文  参考訳（メタデータ） (2020-11-20T10:00:14Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Exact and Metaheuristic Approaches for the Production Leveling Problem [5.510992382274775]
  本稿では,生産水準問題(Product Leveling Problem)と呼ぶ生産計画分野における新たな問題を紹介する。 タスクは、各期間の負荷と各生産資源のバランスが取れ、容量制限が越えられず、注文の優先順位が考慮されるように、生産期間に注文を割り当てることである。 問題の公式モデルを提案し、Bin Backingからの還元によりNP硬度を示す。
  論文  参考訳（メタデータ） (2020-06-15T20:04:59Z)

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

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