論文の概要: Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

• arxiv url: http://arxiv.org/abs/2510.24013v1
• Date: Tue, 28 Oct 2025 02:43:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:36.725584
• Title: Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling
• Title（参考訳）: 混合整数プログラムのための大規模言語モデル(LLM)によるヒューリスティック発見:単一マシンスケジューリング
• Authors: İbrahim Oğuz Çetinkaya, İ. Esra Büyüktahtakın, Parshin Shojaee, Chandan K. Reddy,
• Abstract要約: EDD Challenger (EDDC) と MDD Challenger (MDDC) という2つの新しい LLM-covered を開発した。 我々は,プリエンプションや処理時間,期限を指定せずにnジョブを単一プロセッサにシークエンシングすることで,トータルタドルネスを最小化することを目的とした,シングルマシントータルタドルネス(SMTT)問題に着目する。
• 参考スコア（独自算出の注目度）: 15.936380178807712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Our study contributes to the scheduling and combinatorial optimization literature with new heuristics discovered by leveraging the power of Large Language Models (LLMs). We focus on the single-machine total tardiness (SMTT) problem, which aims to minimize total tardiness by sequencing n jobs on a single processor without preemption, given processing times and due dates. We develop and benchmark two novel LLM-discovered heuristics, the EDD Challenger (EDDC) and MDD Challenger (MDDC), inspired by the well-known Earliest Due Date (EDD) and Modified Due Date (MDD) rules. In contrast to prior studies that employed simpler rule-based heuristics, we evaluate our LLM-discovered algorithms using rigorous criteria, including optimality gaps and solution time derived from a mixed-integer programming (MIP) formulation of SMTT. We compare their performance against state-of-the-art heuristics and exact methods across various job sizes (20, 100, 200, and 500 jobs). For instances with more than 100 jobs, exact methods such as MIP and dynamic programming become computationally intractable. Up to 500 jobs, EDDC improves upon the classic EDD rule and another widely used algorithm in the literature. MDDC consistently outperforms traditional heuristics and remains competitive with exact approaches, particularly on larger and more complex instances. This study shows that human-LLM collaboration can produce scalable, high-performing heuristics for NP-hard constrained combinatorial optimization, even under limited resources when effectively configured.
• Abstract（参考訳）: 本研究は,Large Language Models (LLMs) のパワーを利用した新しいヒューリスティックスを用いたスケジューリングと組合せ最適化の文献に寄与する。 我々は,プリエンプションや処理時間,期限を指定せずにnジョブを単一プロセッサにシークエンシングすることで,トータルタドルネスを最小化することを目的とした,シングルマシントータルタドルネス(SMTT)問題に着目する。 我々は、EDDC(EDDC)とMDDチャレンジャー(MDDC)という2つの新しいLLM発見ヒューリスティックを開発、ベンチマークし、その成果をよく知られたEDD(Early Most Due Date)とMDD(Modified Due Date)ルールにインスパイアした。 より単純な規則に基づくヒューリスティックスを用いた従来の研究とは対照的に,SMTTの混合整数計画法(MIP)から導かれる最適性ギャップや解時間を含む厳密な基準を用いて,LLMが発見したアルゴリズムを評価する。 現状のヒューリスティックスと,さまざまな仕事規模(20,100,200,500)の正確な方法を比較した。 100以上のジョブを持つインスタンスの場合、MIPや動的プログラミングのような正確なメソッドは計算的に難解になる。 500ジョブまでのEDDCは古典的なEDDルールと文献で広く使われているアルゴリズムを改善している。 MDDCは、伝統的ヒューリスティックよりも一貫して優れており、特に大規模で複雑なインスタンスにおいて、正確なアプローチと競合し続けている。 本研究では,人間とLLMの協調により,NPの制約付き組合せ最適化のためのスケーラブルで高性能なヒューリスティックが実現可能であることを示す。

関連論文リスト

• MM-HELIX: Boosting Multimodal Long-Chain Reflective Reasoning with Holistic Platform and Adaptive Hybrid Policy Optimization [103.74675519953898]
  ロングチェーンのリフレクティブ推論は、複雑な現実世界の問題を解決するための前提条件である。 我々は42の難解な合成タスクの1,260のサンプルからなるベンチマークを構築した。 トレーニング後のデータを生成し、そのようなデータを活用するための学習パラダイムを探索する。
  論文  参考訳（メタデータ） (2025-10-09T17:53:58Z)
• Minimizing the Weighted Number of Tardy Jobs: Data-Driven Heuristic for Single-Machine Scheduling [0.0]
  我々は、各ジョブの重み、期間、予定日、期限によって定義されるシングルマシンスケジューリング問題に焦点を当てる。 本稿では,機械学習と問題固有の特徴を組み合わせた新しいデータ駆動スケジューリングを提案する。 実験結果から,本手法は最適解数,最適解数,適応性の観点から,最先端技術よりも優れていた。
  論文  参考訳（メタデータ） (2025-08-19T10:09:02Z)
• Evaluating the Efficacy of LLM-Based Reasoning for Multiobjective HPC Job Scheduling [6.375075345747834]
  ReActスタイルフレームワークを用いたLarge Language Model (LLM)ベースのスケジューラ(Reason + Act) Systemはスクラッチパッドメモリを内蔵し、スケジューリング履歴を追跡し、自然言語のフィードバックを通じて決定を洗練する。 我々は,OpenAI の O4-Mini と Anthropic の Claude 3.7 を用いて,実世界の7つの HPC ワークロードシナリオに対してアプローチを評価した。
  論文  参考訳（メタデータ） (2025-05-29T14:25:29Z)
• Collab: Controlled Decoding using Mixture of Agents for LLM Alignment [90.6117569025754]
  人間のフィードバックからの強化学習は、大規模言語モデルを整合させる効果的な手法として現れてきた。 制御された復号化は、再訓練せずに推論時にモデルを整列するメカニズムを提供する。 本稿では,既存の既成のLCMポリシを活用するエージェントベースのデコーディング戦略の混合を提案する。
  論文  参考訳（メタデータ） (2025-03-27T17:34:25Z)
• On Speeding Up Language Model Evaluation [48.51924035873411]
  我々はこの空間を探索するために$textitadaptive$アプローチを提案する。 我々は、マルチアームの包帯に頼り、次の(メソッド、バリデーションサンプル)ペアを順次識別して評価する。 典型的資源の5～15%のみを用いて,トップパフォーマンスの手法を同定できることを示す。
  論文  参考訳（メタデータ） (2024-07-08T17:48:42Z)
• MindStar: Enhancing Math Reasoning in Pre-trained LLMs at Inference Time [51.5039731721706]
  MindStarは、大言語モデルの純粋に推論に基づく探索手法である。 推論タスクを探索問題として定式化し、最適な推論経路を特定するための2つの探索アイデアを提案する。 Llama-2-13BやMistral-7Bのようなオープンソースモデルの推論能力を大幅に向上させ、GPT-3.5やGrok-1に匹敵する性能を実現している。
  論文  参考訳（メタデータ） (2024-05-25T15:07:33Z)
• A Memetic Algorithm with Reinforcement Learning for Sociotechnical Production Scheduling [0.0]
  本稿では、フレキシブルジョブショップスケジューリング問題(DRC-FJSSP)に深層強化学習(DRL)を適用したメメティックアルゴリズムを提案する。 産業における研究プロジェクトから、フレキシブルマシン、フレキシブルなヒューマンワーカー、作業能力、セットアップと処理操作、材料到着時間、材料製造の請求書の並列タスク、シーケンス依存のセットアップ時間、人間と機械のコラボレーションにおける(一部)自動化タスクを検討する必要性を認識します。
  論文  参考訳（メタデータ） (2022-12-21T11:24:32Z)

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

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