Algoritmo De Recocido Simulado

SECUENCIACIÓN DE TAREAS EN EL ÁMBITO DE LA PRODUCCIÓN: UNA APLICACIÓN DEL ALGORITMO DEL RECOCIDO SIMULADO
Zuleyka Díaz Martínez (a) José Fernández Menéndez (b) Paloma Martínez Almodóvar (b)
(a)

Departamento de Economía Financiera y Contabilidad I.
(b)

Departamento de Organización de Empresas. Universidad Complutense de Madrid.

RESUMEN
Un problema esencial en la Dirección deOperaciones en entornos industriales y manufactureros es la determinación de la secuencia óptima en la que ejecutar los distintos lotes de productos de manera que se minimicen los tiempos de preparación de máquinas. Se trata de un problema de optimización combinatoria que obliga a utilizar técnicas heurísticas ante la imposibilidad práctica de llevar a cabo búsquedas exhaustivas. Un algoritmo muy conocidopor su sencillez es el de Kaufmann, que tiene el inconveniente de que proporciona un óptimo local que puede ser poco adecuado. En nuestro trabajo hemos elaborado un programa de ordenador en lenguaje C que implementa dicho algoritmo con algunas modificaciones y otro programa que implementa el algoritmo del Recocido Simulado, el cual suele proporcionar buenos resultados en problemas de optimizacióncombinatoria al conseguir evitar óptimos locales. Para la implementación se ha utilizado una serie de subrutinas en C proporcionadas por la GNU Scientific Library. Se ha comparado el desempeño de ambos algoritmos y se han buscado los parámetros que permiten ajustar de forma adecuada el algoritmo del Recocido Simulado para su uso eficiente en estos problemas de minimización de los tiempos depreparación de máquinas. Palabras clave: Dirección de Operaciones, Recocido Simulado, tiempos de preparación de máquinas.

1

1. INTRODUCCIÓN.
La secuenciación adecuada de pedidos constituye un importante problema que se plantea dentro de la Dirección de Operaciones a corto plazo. El orden en que los pedidos serán atendidos o procesados, o en general el orden en el que cualquier tipo de tareasserán realizadas, no resulta indiferente, sino que determinará algún parámetro de interés cuyos valores convendrá optimizar en la medida de lo posible. Así podrá verse afectado el coste total de ejecución de las tareas, el tiempo necesario para concluirlas o el stock de productos en curso que será generado. Esto conduce de forma directa al problema de determinar cuál será el orden más adecuado parallevar a cabo las tareas con vistas a optimizar alguno de los anteriores parámetros u otros similares. Se trata de un problema de secuenciación o scheduling que se presenta de forma habitual en la programación de operaciones a corto plazo en entornos industriales o manufactureros (Heizer y Render, 2001) y que puede adoptar una enorme variedad de formulaciones. La gran dificultad para resolver elproblema determinando una secuencia óptima, o al menos admisible, junto con la importancia de conseguirlo, han hecho proliferar reglas, más o menos complejas, muchas de ellas heurísticas, y algunas incluso empíricas, que proporcionan soluciones rápidas y fáciles de calcular destinadas a su uso en situaciones de trabajo reales (Fernández Sánchez y Vázquez Ordás, 1994). El desarrollo de los ordenadoresy la aparición de nuevas técnicas de simulación y optimización heurística que aprovechan plenamente las disponibilidades de cálculo intensivo que aquéllos proporcionan -optimización Montecarlo, soft computing, metaheurísticas, etc, (Melián et al., 2003) - han abierto una nueva vía para abordar los problemas de secuenciación, suministrando un creciente arsenal heurísticas usadas tradicionalmente.El problema concreto al que aquí se prestará atención es el de determinar la secuencia óptima según la cual deben ser elaborados una serie de lotes distintos para minimizar los tiempos de preparación de máquinas. de métodos y algoritmos cuyo uso se extiende paulatinamente sustituyendo a las sencillas reglas

2

En un sistema de producción intermitente o por lotes (también denominado con...