日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

スケジューリング最適化arXiv:2611.17682

LLMエージェントが書いたヒューリスティクスは商用ソルバに匹敵するか:未解決ジョブショップベンチマークでの検証

Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances

シェア:XThreadsFacebookLINEはてブBluesky

LLMをコーディングエージェントとして使い、オープンソースツールのみでジョブショップ問題の解法を自動生成し、商用ソルバと品質・速度で比較した。大規模インスタンスで下界との差が商用より小さく、未解決インスタンスの改善も達成した。

詳しい要約

1. どんなもの?

- LLM を coding agent として使い、open-source tools のみで job-shop scheduling の商用 solver に品質・速度で匹敵できるかを調べた研究。 - 対象は tai_100_1000_1(100,000 operations)、Behnke-Geiger flexible job shops、transport robots 2台の MKT instances。 - 全 run を報告し、independent checkers が全 schedule を検証。 - agent が書いた solver は 525,515 を達成し OptalCP・Hexaly・CP Optimizer を下回った。

2. 先行研究と比べてどこがすごい?

- 商用 solver が標準の難問 scheduling に対し、frontier LLM を coding agent として使うだけで同等以上を狙う点が新しい。 - 同一 workstation・equal budgets で agent-written solver は lower bound 比 0.0-1.8%、CP Optimizer は 2.6-5.8%、Hexaly は 2.4-4.4%。 - 未変更の solver で tai 系 10 instance 全てを改善し 2 件を closed。 - Behnke-Geiger では agent-written tabu search が 32 open instances 中 11 件を改善。

3. 技術・手法の肝は?

- frontier large language model を coding agent として用い、open-source tools のみで solver を生成・改善。 - tai_100_1000_1 では agent-written solver をそのまま適用し改善。 - Behnke-Geiger では agent-written tabu search を利用。 - 2 transport robots の MKT instances 向け solver も agent が作成。 - agent-run improvement campaigns により追加で 8 instances を closed。

4. どうやって有効だと検証した?

- 全 run を報告し、independent checkers が全 schedule を検証。 - tai_100_1000_1 で 525,515 を達成し商用 solver と比較。 - equal budgets・同一 workstation で lower bound 比を CP Optimizer・Hexaly と比較。 - Behnke-Geiger 32 open instances 中 11 件改善、MKT 10 件中 7 件改善を確認。 - 新 lower bounds により published MKT values の 4 件が distributed instance files 上で達成不能と示した。

5. 議論はある?

- 商用 solver に対する agent-written heuristics の品質・速度上の優位性を主張。 - 一方で published MKT values の一部が distributed instance files では達成不能という lower bound の知見を示す。 - 対象は限られた benchmark family であり、一般性や再現性の議論は要旨からは不明。 - LLM・open-source tools 依存のため、計算資源や run 条件の影響は要旨からは不明。

6. 次に読むべき論文は?

- OptalCP、Hexaly、CP Optimizer など商用 solver の比較研究。 - Behnke-Geiger flexible job shop の benchmark 論文。 - MKT instances および transport robots を含む distributed scheduling 研究。 - LLM を coding agent として使う solver 生成・heuristic 設計の関連研究(具体名は要旨からは不明)。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Andre Albrecht, Enzo Morosini Frazzon, Leandro C. Coelho, Bruno Vieira

分類: math.OC, cs.AI

原文アブストラクト

Commercial solvers are the standard tool for difficult scheduling problems. We study whether a frontier large language model, used as a coding agent with open-source tools only, can match them in quality and speed. We report every run, and independent checkers verify every schedule. On the 100,000-operation job shop tai_100_1000_1, an agent-written solver reached 525,515, below OptalCP, Hexaly, and CP Optimizer. Unchanged, it improved all ten instances of the family and closed two. With equal budgets on the same workstation, it ended 0.0-1.8% above the lower bound, against 2.6-5.8% for CP Optimizer and 2.4-4.4% for Hexaly. On the Behnke-Geiger flexible job shops, an agent-written tabu search improved 11 of 32 open instances. With two transport robots, an agent-written solver improved seven of ten MKT instances. New lower bounds show that four published MKT values cannot be attained on the distributed instance files. Agent-run improvement campaigns closed eight further instances.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3Google DeepMind、ロボット向けAIを発表新製品・発表
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI