Extensiones de meta-raps al problema de máquinas paralelas no relacionadas

Abstract

En este estudio se presenta el diseño de una aplicación de Meta-RaPS (Meta-heuristic for Randomized Priority Search) para resolver el problema de programación de la producción en máquinas paralelas no-relacionadas, con tiempos de preparación dependientes de la secuencia, con el objetivo de minimizar el makespan. El cual consiste en programar n trabajos (sin interrupción), disponibles en el tiempo cero, en m máquinas en paralelo (Rm), que procesan los trabajos con tiempos de procesamiento arbitrarios. Cada trabajo debe ser asignado a una máquina, y cada máquina puede procesar un trabajo a la vez. Si el trabajo j es programado en la máquina k, el tiempo necesario para procesar ese trabajo es Pjk, que depende del trabajo j, y de la máquina k. Siempre que un nuevo trabajo se inicia, se requiere un tiempo de preparación en la máquina, ese tiempo de preparación es dependiente de la secuencia y de la máquina (Sijk), donde el tiempo de preparación en la máquina k necesario para realizar el trabajo j después del trabajo i puede ser diferente al tiempo de preparación para el trabajo i después del trabajo j. El objetivo del problema es encontrar el programa de producción que minimice el máximo tiempo de completación o makespan (Cmax). En términos de la notación de scheduling introducida por Graham et al. (1979), el problema en cuestión puede ser representado mediante Rm|Sijk|Cmax. El problema de scheduling en estudio es un problema fuertemente NP-hard (Garey & Johnson, 1979). Por lo que es necesario el uso de meta-heurísticas para encontrar soluciones de buena calidad en tiempos de respuesta factibles. En el Capítulo 1 se realiza una introducción del estudio realizado, planteando las hipótesis, objetivos, justificación y el alcance del estudio. En el Capítulo 2 se presenta una revisión bibliográfica del problema, y se describen los modelos matemáticos asociados al problema Rm|Sijk|Cmax. Luego, en el Capítulo 3 se realiza una descripción de Meta-RaPS, donde se detallan los aspectos más importantes de esta meta-heurística. El diseño de la aplicación de Meta-RaPS se dividió en tres etapas: • Fase de construcción • Fase de mejoramiento • Ajuste de parámetros Para evaluar el desempeño de la meta-heurística diseñada en cada una de estas etapas, se consideró la mejor aplicación encontrada en la literatura (propuesta por Rabadi et al., 2006), llamada Meta-RaPS SAPSL. También se utilizó la librería de problemas propuesta por Rabadi (2005). En el Capítulo 4 se diseñó la fase de construcción, donde se presenta una heurística constructiva visionaria (look-ahead) para encontrar soluciones al problema Rm|Sijk|Cmax, la cual es comparada satisfactoriamente con una heurística constructiva glotona (greedy). Se presenta un ejemplo numérico de su aplicación, y la adición de aleatoriedad controlada mediante los parámetros de Meta-RaPS (%prioridad y %restricción). La fase de mejoramiento se abordó en el Capítulo 5, donde se diseñó una heurística de mejoramiento local para el problema Rm|Sijk|Cmax, la cual es comparada satisfactoriamente con la heurística propuesta por Rabadi et al. (2006). El problema de ajuste de parámetros presentó en los Capítulos 6 y 7. En el Capítulo 6 se aplica un ajuste de parámetros off-line, en el cual el ajuste de parámetros se realiza previamente a la resolución del problema. En el Capítulo 7 se diseñan técnicas de auto-ajuste de parámetros (ajuste on-line o parámetros auto-adaptables), en el cual el ajuste de parámetros se realiza durante la resolución del problema. En los Capítulos 6 y 7 se comparan satisfactoriamente los resultados obtenidos de la aplicación propuesta contra la aplicación propuesta por Rabadi et al. (2006) (Meta-RaPS SAPSL), para ajuste off-line y on-line respectivamente. Donde se puede observar que la aplicación propuesta reporta en promedio mejores resultados que Meta-RaPS SAPSL, además de encontrar mejores soluciones en la mayoría de los problemas de prueba. En el Capítulo 7 se comparan los resultados obtenidos por la aplicación propuesta (Meta-RaPS LACH) utilizando ajuste de parámetros off-line y on-line, mostrando que los resultados obtenidos por ajuste on-line son mejores que los que se obtienen con un ajuste off-line. Finalmente en el Capítulo 8 se detallan las conclusiones obtenidas de este estudio y las futuras investigaciones a realizar. Mostrando que el enfoque de solución propuesto (Meta-RaPS LACH), permite obtener mejores resultados que los encontrados en literatura. El impacto de este estudio, es diseñar alternativas para resolver problemas complejos de programación de la producción. Específicamente en el diseño propuesto de Meta-RaPS, el cual es modificado para facilitar la tarea de fijación o selección de parámetros. Además de permitir la obtención de mejores resultados que los encontrados en literatura.