Estudio comparativo de heurísticas constructivas y algoritmos genéticos, para el problema de programación de tareas en máquinas paralelas idénticas con setup

Estudio comparativo de heurísticas constructivas y Algoritmos Genéticos, para el problema de programación de tareas en máquinas paralelas idénticas con Setup
Juan Carlo Medina S. Postgrado en Ingeniería Industrial Universidad de Concepción Facultad de Administración y Negocios Universidad de las Américas Santiago - Chile jmedinas@udla.cl Eduardo Salazar H. Departamento de Ingeniería IndustrialUniversidad de Concepción Concepción - Chile esalazar@udec.cl Abril, 2010

RESUMEN
En esta investigación se realiza un análisis comparativo entre heurísticas constructivas y dos alternativas propuestas de la metaheurística Algoritmos Genéticos; de manera de evaluar el desempeño alcanzado por éstas, en relación a la capacidad de minimizar el makespan dentro de una configuración productiva demáquinas paralelas idénticas con tiempos de Setup dependientes de la secuencia de trabajos. Para la observación de estos métodos se genera un conjunto de problemas de prueba, en donde tanto los tiempos de Setup como los tiempos de proceso siguen una distribución de probabilidad uniforme. Con el desarrollo de este trabajo, se busca comprobar que la aplicación de algoritmos genéticos a un problema deprogramación de tareas en máquinas paralelas idénticas con setup, se desempeña mejor, usando el makespan como criterio de evaluación, que las heurísticas específicas desarrolladas para este problema, y que esto se hace más notorio en la medida que este aumenta su tamaño. Palabras Claves: Scheduling, Máquinas paralelas, Heurísticas constructivas y Algoritmos Genéticos.

1. INTRODUCCION En estainvestigación se analiza el problema de programación de tareas en un taller de máquinas paralelas. Básicamente este problema contempla el secuenciamiento y la asignación de un conjunto de n trabajos, que deben ser procesados en cualquiera de las m máquinas idénticas dispuestas en paralelo. Con frecuencia se puede encontrar en la literatura una serie de variantes de este problema, en los que seconsideran restricciones tales como que los trabajos deben cumplir con una fecha de entrega, no todos ellos están disponibles al mismo tiempo al inicio de las operaciones, deben ser procesados en una sola máquina y sin interrupciones, son independientes entre sí (no existen relaciones de precedencia), cada máquina puede procesar una sola tarea a la vez y sus tiempos de preparación son dependientes de lasecuencia de los trabajos procesados. Todo esto hace que el problema de programar tareas en este ambiente de máquinas sea de un alto nivel de complejidad computacional (NP-Hard), por lo que el estudio de métodos no exactos, pero más eficientes como lo son las heurísticas y metaheurísticas, puede ser un gran aporte para las organizaciones que operan con esta configuración productiva.

2. MARCOCONCEPTUAL El problema de programación de máquinas paralelas En relación al caso del taller de máquinas paralelas, Baker (1974) [3] señala que el modelo básico supone que existen n trabajos, con una sola operación, y simultáneamente disponibles en un tiempo cero. También supone que existen m máquinas idénticas disponibles para procesar y que cada trabajo puede ser procesado en a lo más una máquina ala vez. Por su parte Hax y Candea (1984) [17] agregan que este tipo de taller es una generalización del problema de 1 máquina, ya que los trabajos requieren de una sola operación pero que esta vez pueden pasar a través de m máquinas en paralelo. Una característica de esta configuración es que se utiliza la misma instalación para obtener una gran variedad de productos. Cuando se obtiene lacantidad requerida de un producto particular, se realizan los ajustes de las instalaciones (setup) para procesar otro lote del siguiente producto, repitiéndose esto en forma continua. Heurísticas Constructivas para el problema de máquinas paralelas con setup a. Heurística Extensión de LPT (LPT_Setup)1 En Cortés (2009) [10] se plantea un procedimiento heurístico sencillo, basado en la regla LPT,...