En este trabajo se evalúan algoritmos heurísticos de exploración de entornos (AED, ANED, SA, TS, GA y GRASP) en la programación de pedidos en una máquina de la vida real, con el objetivo de minimizar la suma de retrasos . El caso estudiado se diferencia de los problemas convencionales en que los tiempos de preparación de las operaciones están separados de los tiempos de procesamiento y son dependientes de la secuencia. Los resultados computacionales revelan que la Búsqueda Tabú funciona mejor que los otros algoritmos aplicados.