Magíster en Ingeniería Industrial

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.

En Chile, la industria forestal es completamente privada, con una alta concentración en dos grandes firmas; Arauco y Mininco, las que poseen aproximadamente la mitad de las plantaciones del país y que verticalmente integran plantas de celulosa, aserraderos y papeleras. Diariamente en las faenas forestales se deben transportar diferentes productos desde los distintos orígenes en los predios hasta diferentes destinos determinados. Las empresas forestales subcontratan el servicio de transporte a diferentes empresas de servicios llamadas EMSEFOR. Las EMSEFOR perciben sus ingresos por cada kilómetro recorrido con carga desde un origen determinado a un destino cualquiera. El costo del recorrido siguiente a realizar, es decir el retorno por una nueva carga ya sea al mismo origen u otro es asumido íntegramente por la empresa que presta el servicio. A nivel país, las empresas mandantes utilizan un Sistema de Asignación de Camiones (Asicam) para la programación del transporté forestal. Esta programación tiene diferentes problemas asociados tales como: sobre carga de algunos camiones, jornada extensas de trabajo y tramos largo de recorrido sin carga. Asicam define una ventana de tiempo a todos sus despachos (Viajes). La idea en este estudio, es reasignar los viajes a los distintos camiones con el objetivo de minimizar los kilómetros recorridos sin carga. El problema a resolver (NP-hard) se puede interpretar como un problema de programación de la producción de “n” trabajos sobre “m” máquinas paralelas idénticas con tiempos de preparación o setup dependientes. Se proponen dos metaheurísticas basadas en algoritmos genéticos para optimizar la programación de camiones para el transporte forestal. El primer algoritmo genético (GA) utiliza los principios de la evolución genética, mientras el segundo algoritmo (GALS) combina la evolución genética con búsqueda local. Los algoritmos reducen los kilómetros recorridos sin carga en un 31 por ciento y aumentando la productividad por camión en un 25 por ciento.

El objetivo de este trabajo es desarrollar un algoritmo de búsqueda tabú para dar solución al problema de asignación de horarios de trabajo de tal forma de poder cubrir los turnos y las necesidades en el mes del personal que se desempeña en el cargo de Mucama en una empresa del rubro entretención, hotelería y turismo. Para ello, el trabajo se iniciará con la recopilación de información para el estudio, que incluye datos particulares del cargo Mucamas en la unidad: dotación según tipo de contrato, turnos a cubrir según horarios de demanda, cantidad de citaciones diarias de colaboradores por turno (definido como necesidad operativa), las restricciones operativas, legales y organizacionales de la compañía en el proceso de programación de turnos, entre otros aspectos relevantes. Dicha información será facilitada por el área de Planificación de Turnos de la compañía. Luego, se realizará un estado del arte respecto al problema en cuestión y sus métodos de solución disponibles en la bibliografía existente. Seguidamente, se elaborará el marco teórico del estudio donde se explique en detalle cómo opera el algoritmo de búsqueda tabú. Posteriormente, se modelará el problema descrito preliminarmente, identificando la situación problema relativa al cargo Mucama y todas las restricciones asociadas; esto permitirá desarrollar el algoritmo a utilizar, detallando sus características y operatividad, el cual se programará en un ambiente computacional en lenguaje C#. Finalmente, se analizarán los resultados obtenidos de estudios experimentales y se comparará con el actual método de la empresa para obtener las conclusiones y recomendaciones relevantes del estudio.

En esta tesis se resuelve el Problema de la Localización de Contenedores y Ruteo de Vehículos (PLCRV) para la Recolección de Residuos Domiciliarios. Se considera la siguiente modalidad para la recolección de la basura: cada usuario debe dirigirse a su contenedor asignado y depositar su basura en él. Luego, camiones especializados recorren y recogen la basura de cada uno de estos contenedores para así transportarla al sitio de disposición final. Se considera que los contenedores y los camiones recolectores tienen una capacidad predeterminada de basura que pueden almacenar y transportar, respectivamente. El PLCRV consiste en determinar la localización de los contenedores, la asignación de los usuarios a los contenedores y la ruta que los vehículos deben seguir para recoger la basura de cada uno de estos contenedores. Minimizando tanto el costo total de transporte, como la distancia total recorrida por los usuarios a sus contenedores asignados. Para resolver el PLCRV, con dos objetivos contrapuestos, se propone un modelo de programación lineal entera para determinar soluciones no inferiores en forma óptima que describen la frontera eficiente. Se consideran restricciones de capacidad tanto para los contenedores, como para los camiones. Para su resolución, se utiliza un procedimiento basado en planos cortantes para obtener una buena cota inferior y luego se aplica el algoritmo Branch and Bound para obtener la solución óptima.

Actualmente para la valoración de proyectos de inversión se utiliza normalmente la metodología del Flujo de Caja Descontado. Esta metodología no cuantifica la incertidumbre del proyecto, por lo que las estimaciones realizadas podrían no reflejar correctamente las eventualidades en el transcurso de la ejecución del proyecto. En este trabajo se aplica la metodología de Opciones Reales, capaz de cuantificar la incertidumbre a través de la volatilidad de los Flujos de Caja. Esta metodología se aplicará a un proyecto de inversión referido a una Planta de Purificación de Biogás para uso Vehicular. Para ello se considera una ejecución en 10 años sujeta a los cambios en precios de Gas Natural Licuado y de Energía Eléctrica. Se pretende comparar el método de análisis de Redes Binomiales con los métodos de Forma Cerrada, como lo es el Black & Scholes. Además se evaluarán con Redes Binomiales las opciones de ejecutar, expandir, abandonar, contraer, y para finalizar una opción compuesta del proyecto de inversión,ésta última considera todas las anteriores Al evaluar el proyecto con la metodología tradicional, el Valor Actual Neto Tradicional resulta ser cercano a US$1,3MM. Para la opción de ejecutar el proyecto, el valor que más se asemeja al valor calcula con la metodología de Black & Scholes es el valor obtenido con la red binomial de 1000 pasos. Sin embargo, para el análisis de las opciones de expandir, abandonar, contraer y la opción compuesta, la red binomial de 20 pasos resulta ser una buen aproximación con respecto al valor con más pasos, 200 de ellos. Por otro lado, la opción que agregó menos valor al proyecto fue la opción de ejecutar el mismo, con un valor de US$1,3MM. La opción que entrega mayor valor es la opción de elegir, valorada en US$4,0MM. Se espera que con este estudio ayude a que la metodología de Opciones Reales se masifique y se identifique como una metodología válida para la evaluación de proyectos de inversión al considerar su incertidumbre.