# Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

arXiv: https://arxiv.org/abs/2510.24013 · HTML: https://mlsanity.com/paper/2510.24013/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 28 Oct 2025.

## Builds on (most cited first, 11 of 11)

- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Talking About Large Language Models](https://mlsanity.com/paper/2212.03551/) (2022)
- [DeepOPF: A Feasibility-Optimized Deep Neural Network Approach for AC Optimal Power Flow Problems](https://mlsanity.com/paper/2007.01002/) (2020)
- [LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning](https://mlsanity.com/paper/2407.02511/) (2024)
- [Large Language Models for Scientific Synthesis, Inference and Explanation](https://mlsanity.com/paper/2310.07984/) (2023)
- [FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch](https://mlsanity.com/paper/2406.04824/) (2024)
- [Learning Optimal Solutions via an LSTM-Optimization Framework](https://mlsanity.com/paper/2207.02937/) (2022)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making](https://mlsanity.com/paper/2311.06972/) (2023)

## Built on by (most cited first, 4 of 4)

- [Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search](https://mlsanity.com/paper/2608.03129/) (2026)
- [LLM Agents for Combinatorial Efficient Frontiers: Investment Portfolio Optimization](https://mlsanity.com/paper/2601.00770/) (2026)
- [Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontiers](https://mlsanity.com/paper/2604.11507/) (2026)
- [GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization](https://mlsanity.com/paper/2605.19119/) (2026)

## Abstract (arXiv)

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.