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

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.