論文の概要: An Aligned Constraint Programming Model For Serial Batch Scheduling With Minimum Batch Size

• arxiv url: http://arxiv.org/abs/2511.16045v1
• Date: Thu, 20 Nov 2025 05:05:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-21 17:08:52.472796
• Title: An Aligned Constraint Programming Model For Serial Batch Scheduling With Minimum Batch Size
• Title（参考訳）: 最小バッチサイズ付きシリアルバッチスケジューリングのための制約プログラミングモデル
• Authors: Jorge A. Huertas, Pascal Van Hentenryck,
• Abstract要約: 連続的なバッチスケジューリングでは、類似のファミリーのジョブがバッチにグループ化され、繰り返し設定を避けるために順次処理される。 本稿では,バッチの仮想集合に依存しない新しいCPモデルを提案する。 キーアライメントパラメータを使用して、マシン上でスケジュールされた同じ家族のジョブのシーケンスを直接推論する。
• 参考スコア（独自算出の注目度）: 16.447342678728827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In serial batch (s-batch) scheduling, jobs from similar families are grouped into batches and processed sequentially to avoid repetitive setups that are required when processing consecutive jobs of different families. Despite its large success in scheduling, only three Constraint Programming (CP) models have been proposed for this problem considering minimum batch sizes, which is a common requirement in many practical settings, including the ion implantation area in semiconductor manufacturing. These existing CP models rely on a predefined virtual set of possible batches that suffers from the curse of dimensionality and adds complexity to the problem. This paper proposes a novel CP model that does not rely on this virtual set. Instead, it uses key alignment parameters that allow it to reason directly on the sequences of same-family jobs scheduled on the machines, resulting in a more compact formulation. This new model is further improved by exploiting the problem's structure with tailored search phases and strengthened inference levels of the constraint propagators. The extensive computational experiments on nearly five thousand instances compare the proposed models against existing methods in the literature, including mixed-integer programming formulations, tabu search meta-heuristics, and CP approaches. The results demonstrate the superiority of the proposed models on small-to-medium instances with up to 100 jobs, and their ability to find solutions up to 25\% better than the ones produces by existing methods on large-scale instances with up to 500 jobs, 10 families, and 10 machines.
• Abstract（参考訳）: 連続的なバッチ(sバッチ)スケジューリングでは、類似のファミリーのジョブがバッチにグループ化され、異なるファミリーの連続的なジョブを処理する際に必要となる反復的なセットアップを避けるために順次処理される。 スケジューリングに大きな成功を収めたにもかかわらず、半導体製造におけるイオン注入領域を含む多くの実用的な環境において、最小バッチサイズを考慮した3つの制約プログラミング(CP)モデルのみが提案されている。 これらの既存のCPモデルは、次元の呪いに悩まされ、問題に複雑さをもたらす可能性のあるバッチの事前定義された仮想セットに依存している。 本稿では,この仮想集合に依存しない新しいCPモデルを提案する。 代わりにキーアライメントパラメータを使用して、マシン上でスケジュールされた同じ家族のジョブのシーケンスを直接推論することで、よりコンパクトな定式化を実現している。 この新モデルは、探索位相を調整した問題構造と制約プロパゲータの推論レベルを強化することにより、さらに改善される。 約5万のインスタンス上での広範な計算実験は、混合整数プログラミングの定式化、タブ探索メタヒューリスティックス、CPアプローチなど、提案されたモデルと文献の既存の手法を比較した。 その結果、最大100ジョブの小規模インスタンスにおいて提案したモデルが優れていること、最大500ジョブ、10ファミリー、10マシンの大規模インスタンスにおいて、既存のメソッドが生成したモデルよりも最大25倍優れたソリューションを見つける能力を示した。

関連論文リスト

• CP-Bench: Evaluating Large Language Models for Constraint Modelling [6.250460397062786]
  制約プログラミング(CP)は、問題を解くために広く使われているが、その中核となるプロセス、すなわち制約モデリングは、かなりの専門知識を必要とし、広く採用される際のボトルネックと考えられている。 近年,問題記述を実行可能な制約モデルに変換するために,Large Language Models (LLMs) を用いて検討されている。 制約モデリングのための既存の評価データセットは、しばしば、現実のシナリオの多様性を捉えない、小さく、均一で、ドメイン固有のインスタンスに限られる。 この研究はCP-Benchの導入によってこのギャップに対処する。CPコミュニティから得られた様々な既知の問題を含む新しいベンチマークであるCP-Benchは構造化されている。
  論文  参考訳（メタデータ） (2025-06-06T12:56:02Z)
• Constraint Programming Models For Serial Batch Scheduling With Minimum Batch Size [17.283429743575194]
  シリアルバッチ(sバッチ)スケジューリングでは、ジョブはバッチにグループ化され、バッチ内で順次処理される。 本稿では、複数の並列マシン、非同一のジョブウェイトとリリース時間、および異なるファミリーのバッチ間のシーケンス依存セットアップ時間について考察する。
  論文  参考訳（メタデータ） (2025-04-07T17:14:19Z)
• 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)
• Automatic Mixed-Precision Quantization Search of BERT [62.65905462141319]
  BERTのような事前訓練された言語モデルは、様々な自然言語処理タスクにおいて顕著な効果を示している。 これらのモデルは通常、数百万のパラメータを含んでおり、リソースに制約のあるデバイスへの実践的なデプロイを妨げている。 本稿では,サブグループレベルでの量子化とプルーニングを同時に行うことができるBERT用に設計された混合精密量子化フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-30T06:32:47Z)

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

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