Resumen: Nuestro estudio contribuye a la literatura sobre programación y optimización combinatoria con nuevas heurísticas descubiertas aprovechando el poder de los modelos de lenguaje grande (LLM). Nos centramos en el problema de la tardanza total en una sola máquina (SMTT), que tiene como objetivo minimizar la tardanza total secuenciando n trabajos en un solo procesador sin preferencia, dados los tiempos de procesamiento y las fechas de vencimiento. Desarrollamos y comparamos dos heurísticas novedosas descubiertas por LLM, EDD Challenger (EDDC) y MDD Challenger (MDDC), inspiradas en las conocidas reglas de fecha de vencimiento más temprana (EDD) y fecha de vencimiento modificada (MDD). A diferencia de estudios anteriores que emplearon heurísticas basadas en reglas más simples, evaluamos nuestros algoritmos descubiertos en LLM utilizando criterios rigurosos, incluidas brechas de optimización y tiempo de solución derivados de una formulación de programación entera mixta (MIP) de SMTT. Comparamos su rendimiento con heurísticas de última generación y métodos exactos en varios tamaños de trabajos (20, 100, 200 y 500 trabajos). En casos con más de 100 trabajos, los métodos exactos como MIP y la programación dinámica se vuelven computacionalmente intratables. Hasta 500 trabajos, EDDC mejora la regla EDD clásica y otro algoritmo ampliamente utilizado en la literatura. MDDC supera consistentemente a las heurísticas tradicionales y sigue siendo competitivo con enfoques exactos, particularmente en instancias más grandes y complejas. Este estudio muestra que la colaboración entre humanos y LLM puede producir heurísticas escalables y de alto rendimiento para la optimización combinatoria restringida por NP, incluso con recursos limitados cuando se configura de manera efectiva.
Publicado originalmente en export.arxiv.org el 28 de octubre de 2025.
Ver fuente original
