Benchmarking LLM-generated heuristics for the multi-objective flexible job shop: an anchored comparison against exact and metaheuristic methods

Abstract Scheduling in flexible job shops faces a trade-off between exact methods, which provide high-quality solutions at the cost of problem-specific modelling and substantial computation, and dispatching rules, which are fast but often less effective. This paper investigates whether Large Language Models (LLMs) can automatically generate executable scheduling heuristics that narrow this gap. Two frontier LLMs from different providers are used as generators and variation operators within a Non-dominated Sorting Genetic Algorithm II (NSGA-II) framework optimising makespan and total machine workload. The generated heuristics are evaluated on the Brandimarte instances against a constraint-programming solver, a multi-objective memetic algorithm, and classical dispatching rules using a common Pareto-based protocol, with training and evaluation instances kept disjoint. Since an individual heuristic produces a single schedule while the exact solver, run once per weight of the protocol, returns a set of optimal points, comparison is performed at the portfolio level. The generated portfolio matches the memetic algorithm while requiring three to five times less computation, and outperforms classical dispatching rules under an equivalent wall-clock budget on 11 of the 15 instances (\((p=0.036)\) after Holm correction). The approach requires only 54 lines of natural-language problem specification, compared with 221 lines for the corresponding disjunctive formulation, and the generated heuristics transfer to a new objective. The two models produce results within 1.3% of each other, while most of the gain from evolutionary search appears in the first two or three generations on the instances evaluated here, improving the best heuristic by approximately 2.5% in total.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-13
DOI
https://doi.org/10.21203/rs.3.rs-11359760/v1
Primary Topic
Scheduling and Optimization Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Benchmarking LLM-generated heuristics for the multi-objective flexible job shop: an anchored comparison against exact and metaheuristic methods

Alejandro Uribe, Arkaitz Artetxe, Urtzi Otamendi, Diego Forniés-Tabuenca et al.
3 links
Research Square
Scheduling and Optimization Algorithms
preprint

Benchmarking LLM-generated heuristics for the multi-objective flexible job shop: an anchored comparison against exact and metaheuristic methods

Alejandro Uribe, Arkaitz Artetxe, Urtzi Otamendi, Diego Forniés-Tabuenca, Juan Carlos Rivera
preprint en

Abstract

Abstract Scheduling in flexible job shops faces a trade-off between exact methods, which provide high-quality solutions at the cost of problem-specific modelling and substantial computation, and dispatching rules, which are fast but often less effective. This paper investigates whether Large Language Models (LLMs) can automatically generate executable scheduling heuristics that narrow this gap. Two frontier LLMs from different providers are used as generators and variation operators within a Non-dominated Sorting Genetic Algorithm II (NSGA-II) framework optimising makespan and total machine workload. The generated heuristics are evaluated on the Brandimarte instances against a constraint-programming solver, a multi-objective memetic algorithm, and classical dispatching rules using a common Pareto-based protocol, with training and evaluation instances kept disjoint. Since an individual heuristic produces a single schedule while the exact solver, run once per weight of the protocol, returns a set of optimal points, comparison is performed at the portfolio level. The generated portfolio matches the memetic algorithm while requiring three to five times less computation, and outperforms classical dispatching rules under an equivalent wall-clock budget on 11 of the 15 instances (\((p=0.036)\) after Holm correction). The approach requires only 54 lines of natural-language problem specification, compared with 221 lines for the corresponding disjunctive formulation, and the generated heuristics transfer to a new objective. The two models produce results within 1.3% of each other, while most of the gain from evolutionary search appears in the first two or three generations on the instances evaluated here, improving the best heuristic by approximately 2.5% in total.

Research Square
Vicomtech (ES), Universidad EAFIT (CO)
Scheduling and Optimization Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon