Algoritmo de recocido simulado aplicado al problema de secuenciamiento regular

Simulated annealing algorithm applied to a flow-shop problem

En este trabajo se realizó una descripción detallada del algoritmo de Recocido Simulado como metodología de solución a problemas de optimización combinatorial. Este se enfocó especialmente a la solución del problema de secuenciamiento de tareas dentro de una planta de producción con recursos limitados. Se presentan resultados de simulaciones realizadas sobre un problema de la literatura especializada, mostrando la amplia versatilidad, eficiencia, y facilidad de implementación del algoritmo propuesto.

1. Introducción

La permanencia de una empresa dentro de mercados competitivos exige una planificación eficiente de las actividades productivas, de forma que se aproveche al máximo los recursos disponibles y se reduzcan los costos a niveles apropiados sin afectar la calidad de los bienes manufacturados. Desde este punto de vista, la eficiencia en el proceso productivo puede ser definida como el porcentaje de tiempo en que los recursos son usados para la generación del producto final. En este aspecto se reconoce la existencia de actividades que, si bien son necesarias para el funcionamiento de la planta, generan periodos en los que la materia prima no  es procesada, como, por ejemplo, el arranque de maquinaria, reconfiguración de maquinaria por cambio de productos, mantenimiento, tiempos muertos e interrupciones por roturas. Por otro lado, existen periodos de tiempo en los cuales parte de la maquinaria (y operarios) permanece inactiva a la espera del finalizado de un proceso previo, lo cual redunda en el aumento de costos por mano de obra inactiva y retrasos en los tiempos de entrega. Así, es evidente la necesidad de generar un programa en el que todas las actividades necesarias para la generación del producto final sean ejecutadas en el menor tiempo posible. De manera más formal, el problema secuenciamiento de tareas consiste en la generación de un programa de eventos para la ejecución de n tareas las cuales deben ser procesadas en un conjunto de m máquinas ubicadas en línea.

Debido a la importancia dentro el planeamiento operativo de las empresas, este problema se ha convertido en un área de estudio clásico en la literatura, y se ha tratado de resolver a partir de diversas metodologías de solución, entre las cuales se destacan aquellas que implementan metaheurísticas, debido a su eficiencia, facilidad de programación y calidad de resultados [1].

En este trabajo, se propuso la implementación de un algoritmo denominado como Recocido Simulado (RS), el cual fue propuesto en 1982 por tres investigadores de IBM Society [2], y cuya principal característica es que puede escapar de óptimos locales. Un trabajo similar, desarrollado en forma contemporánea e independiente, fue publicado por [3]. El algoritmo de RS puede interpretarse como un proceso iterativo similar al algoritmo de Metrópolis [4], en el cual se evalúa y se decrementa de forma controlada un parámetro de control conocido como Temperatura. El algoritmo de Metrópolis simula el proceso físico basado en la temperatura a la cual los sólidos obtienen estados de baja energía o de equilibrio térmico, conocido como recocido de sólidos. Durante este proceso, la energía libre del sólido es minimizada.

En la optimización combinatoria se desarrolla un proceso similar al de recocido de sólidos. Este proceso puede ser formulado como una metodología que encuentra, entre muchas soluciones, aquella que tenga mínimo costo. Así, se establecen las siguientes correspondencias: