Fugu-MT 論文翻訳(概要): Theoretical Lower Bounds for the Oven Scheduling Problem

論文の概要: Theoretical Lower Bounds for the Oven Scheduling Problem

arxiv url: http://arxiv.org/abs/2410.01368v1
Date: Wed, 2 Oct 2024 09:30:01 GMT
ステータス: 処理完了
システム内更新日: 2024-11-04 21:29:22.028877
Title: Theoretical Lower Bounds for the Oven Scheduling Problem
Title（参考訳）: オーブンスケジューリング問題に対する理論的下界
Authors: Francesca Da Ros, Marie-Louise Lackner, Nysret Musliu,
Abstract要約: 問題の目的は、複数の要因を最小化しながら、オーブンに一連のジョブをスケジュールすることである。効率的なスケジュールを得るための鍵は、バッチで互換性のあるジョブを同時に処理することだ。我々はOSPの理論的、問題固有の下限を非常に高速に計算できるように開発する。
参考スコア（独自算出の注目度）: 6.144680854063938
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Oven Scheduling Problem (OSP) is an NP-hard real-world parallel batch scheduling problem arising in the semiconductor industry. The objective of the problem is to schedule a set of jobs on ovens while minimizing several factors, namely total oven runtime, job tardiness, and setup costs. At the same time, it must adhere to various constraints such as oven eligibility and availability, job release dates, setup times between batches, and oven capacity limitations. The key to obtaining efficient schedules is to process compatible jobs simultaneously in batches. In this paper, we develop theoretical, problem-specific lower bounds for the OSP that can be computed very quickly. We thoroughly examine these lower bounds, evaluating their quality and exploring their integration into existing solution methods. Specifically, we investigate their contribution to exact methods and a metaheuristic local search approach using simulated annealing. Moreover, these problem-specific lower bounds enable us to assess the solution quality for large instances for which exact methods often fail to provide tight lower bounds.
Abstract（参考訳）: オーブンスケジューリング問題(オーブンスケジューリング問題、英: Oven Scheduling Problem、OSP)は、半導体産業で発生するNPハードな実世界の並列バッチスケジューリング問題である。問題の目的は、オーブン全体の実行時間、仕事の難易度、セットアップコストを最小化しながら、オーブン上の一連のジョブをスケジュールすることである。同時に、オーブンの適格性と可用性、ジョブのリリース日、バッチ間のセットアップ時間、オーブンの容量制限など、さまざまな制約にも従わなければならない。効率的なスケジュールを得るための鍵は、バッチで互換性のあるジョブを同時に処理することだ。本稿では,OSPの論理的,問題固有の下限を高速に計算する手法を提案する。これらの下位境界を徹底的に検討し、それらの品質を評価し、既存のソリューション手法への統合を探求する。具体的には, シミュレーションアニーリングを用いて, 高精度な手法とメタヒューリスティックな局所探索手法について検討する。さらに、これらの問題固有の下限は、厳密な下限の提供に失敗することが多い大規模インスタンスの解の質を評価することができる。

関連論文リスト

Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling [9.674641730446748]
フレキシブルなジョブショップスケジューリング問題(FJSSP)は、複雑な最適化タスクを提供する。近似法は、ソリューションが許容される時間枠内にあることを保証するために使用される。量子力学的効果を利用したメタヒューリスティックな量子アナリングは、短時間で優れた解品質を示す。
論文参考訳（メタデータ） (2024-08-28T09:52:14Z)
Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport [35.440243358517066]
我々は,ミニバッチOT問題の解を集約して構築した最適輸送問題に対して,上下境界の新たなファミリーを導入する。上界ファミリーは、一方の極端における従来のミニバッチ平均化と、もう一方の極端におけるミニバッチの最適結合によって見出されるタイトな境界を含む。様々な実験を通じて,計算予算と拘束力のトレードオフについて検討し,コンピュータビジョン応用におけるこれらの境界の有用性を示す。
論文参考訳（メタデータ） (2022-10-24T22:12:17Z)
Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
論文参考訳（メタデータ） (2022-05-24T20:51:37Z)
Exact methods and lower bounds for the Oven Scheduling Problem [5.7485371212305685]
Oven Scheduling Problem (OSP) は、電子部品製造の領域で発生する新しい並列バッチスケジューリング問題である。オーブンの実行はエネルギー集約性の高いため、時間内にジョブを終了する以外に、すべてのオーブンの累積バッチ処理時間を最小化することが主な目的である。本稿では、制約計画法(CP)と整数線形計画法(ILP)とそれに対応するモデルを用いて、このNPハードスケジューリング問題を解決することを提案する。
論文参考訳（メタデータ） (2022-03-23T16:28:05Z)
Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems [30.759279275710078]
インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。コストのかかる有限地平線問題を解くことなく,指数減衰をキャプチャするアルゴリズムを提供する。当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。
論文参考訳（メタデータ） (2021-03-08T13:10:31Z)
An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
論文参考訳（メタデータ） (2021-02-17T19:55:42Z)
Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文参考訳（メタデータ） (2020-11-27T16:42:12Z)
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)
An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文参考訳（メタデータ） (2020-06-18T20:09:53Z)
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)

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

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