Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En este trabajo se estudian problemas de programación de tareas en un entorno de máquinas paralelas. A diferencia de la literatura clásica, asumimos que los trabajos pueden ser divididos en distintas partes, cada una de las cuales puede ser procesada en distintas máquinas. Antes de procesar cualquier parte de un trabajo, la máquina debe prepararse y requiere un tiempo de instalación. Primero se estudia el problema de minimizar la suma ponderada de tiempos de completación, para el cual se obtiene una $(2+\varepsilon)$-aproximación cuando los tiempos de instalación son todos iguales. Este resultado corresponde al primer algoritmo de aproximación de factor constante para este problema. Usando técnicas similares se diseña una 2-aproximación para el caso de una ponderación uniforme de los trabajos, que en particular mejora el factor 2.781 obtenido por Schalekamp et al. Finalmente, con un algoritmo de {\it programación en lista}, se obtiene una 4-aproximación para el problema original con tiempos de instalación dependientes del trabajo. Posteriormente se estudia el problema en máquinas no relacionadas, donde los tiempos de proceso e instalación dependen de cada máquina. Los algoritmos diseñados en esta sección están basados en técnicas de redondeo de relajaciones lineales. La primera relajación que se estudia permite diseñar una 3-aproximación para el problema. Al realizar un paso de {\it lift and project} sobre una restricción es posible fortalecer la relajación, lo que permite diseñar una $(1+\phi)$-aproximación, donde $\phi=\frac{\sqrt{5}+1}{2}$. Respecto a la inaproximabilidad del problema se demuestra una cota inferior igual a $\frac{e}{e-1}$ basada en un resultado de Feige para {\it Max-$k$-Cover}. Usando la relajación lineal fuerte se muestra una 2-aproximación para la versión del problema en que cada trabajo posee un conjunto restringido de máquinas en las que puede ser procesado, teniendo igual tiempo de instalación y procesamiento en todas ellas. Finalmente, se estudia relajaciones basadas en {\it configuraciones} sobre trabajos, es decir, las variables corresponden a vectores que representan la asignación de un trabajo a máquinas en una cierta programación. El programa lineal de configuraciones de trabajos posee una cantidad infinita de variables, sin embargo, se demuestra que es posible restringirse a una cantidad finita de ellas y que además es posible aproximar este programa lineal en tiempo polinomial a un factor de $1+\varepsilon$. Determinar el gap de integralidad de esta relajación queda como una pregunta abierta.

Magíster en Gestión de Operaciones / En este trabajo se desarrolla una metodología basada en un modelo de programación lineal entera mixta para la el diseño de cuadrantes, en el contexto del Plan Cuadrante de Seguridad Preventiva (PCSP) de Carabineros de Chile. El modelo presentado en este trabajo es una extensión del modelo de P-medianas con restricciones de equidad en la demanda por recursos policiales entre cada uno de los cuadrantes. Este último modelo arroja formas que no son del todo deseable, incluso creando cuadrantes inconexos. Por eso en este trabajo se incorpora una penalización en el tamaño de la frontera de cada distrito. Por otra parte, Carabineros de Chile se enfrenta a una demanda de recursos policiales cuya unidad de medición es denominada Unidad de Vigilancia Equivalente (U.V.E.). Esta demanda está dividida en dos componentes: una de reacción que es fija para cada subsector geográfico; y otra de prevención que depende del máximo de tres factores (nivel de delito, población, kilómetros viales). La primera componente de la demanda es sometida a restricciones de equidad, y la segunda al depender de la forma en que se divide la comuna, es penalizada en la función objetivo. El modelo propuesto que resuelve el diseño óptimo de cuadrantes resulta ser difícil de resolver para instancias superiores a los 100 bloques. Por este motivo se desarrollan varias reglas para disminuir el tamaño del problema para finalmente utilizar una heurística tipo Localización-Asignación, en la cual se divide el problema original en dos problemas, uno en el cual se determina el centro geométrico de los cuadrantes y otro en el que se le asignan a cada centro los bloques. Esta heurística fue implementada de dos maneras. En una se resolvía el problema de asignación a óptimalidad, y en la otra se resolvía la relajación lineal y se utiliza alguna regla de aproximación sacrificando algunas veces factibilidad. Estos métodos fueron aplicados a la comuna de Ñuñoa cuya instancia sobrepasa los 400 bloques. Los resultados de la heurística fueron satisfactorios, encontrando muchas soluciones factibles y de mejor calidad que las que pueden ser obtenidas a través de los métodos de optimización implementados en CPLEX. El desarrollo de esta metodología permite encontrar muchas soluciones factibles con garantías de equidad, lo cual es bueno para tener los tomadores de decisiones, que pueden a posteriori tener otras consideraciones en el diseño de cuadrantes.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / El trabajo desarrollado en esta tesis se enmarca dentro del área de investigación de operaciones, en el campo de la optimización estocástica para un problema de planificación forestal, el cual se modela como un problema lineal de carácter mixto. El problema de planificación forestal abordado en esta tesis consiste en la maximización del valor presente del plan de explotación táctico de un conjunto de 17 bosques sujeto a incertidumbres internas (rendimiento de los diversos predios) y externas (precio de los productos y cantidad demandada de estos), incertidumbres que se representan a través de árboles de escenarios. Dentro de las principales decisiones a realizar se encuentra la construcción y/o mejora de caminos de la red interna junto a la cantidad de cada predio que será cosechada, almacenada y vendida durante cada periodo. Llevar a cabo la resolución de este tipo de problemas estocásticos bajo las técnicas de optimización tradicionales se vuelve inabordable en la medida que el tamaño de la instancia aumenta, lo que justifica la utilización de un algoritmo adecuado para alcanzar resultados en tiempos razonables. La metodología de resolución utilizada se basa en el algoritmo de descomposición por escenarios Progressive Hedging (PH) sobre el cuál se realizan una serie de ajustes según las características del problema con tal de obtener mejores rendimientos. Junto a esto, se realizan una serie de comparaciones de diversas implementaciones del mismo algoritmo con respecto a técnicas de optimización tradicionales, determinando y analizando las ventajas que ofrece PH para el problema en estudio. Se implementa una metodología de generación de árboles de escenarios basada en un modelo matemático robusto, utilizando como punto de partida un proceso estocástico para representar el movimiento de las variables aleatorias, lo que permite obtener soluciones rigurosas y de calidad. Se lleva a cabo un estudio detallado respecto a técnicas de reducción de escenarios, así como del desarrollo de una metodología de simulación que permite comparar de forma cuantitativa el rendimiento de modelos estocásticos y determinísticos, permitiendo estimar el número suficiente de escenarios que logran representar de buena manera la realidad, manteniéndose óptimo el trade-off entre calidad de solución y tiempos de cómputo involucrados. Los resultados concluyen que la utilización del algoritmo PH bajo las configuraciones y ajustes realizados ofrece rendimientos superiores a las técnicas de optimización clásicas y tradicionales para problemas estocásticos de gran escala, con la posibilidad de explotar de gran manera su implementación en paralelo, obteniéndose así rendimientos superiores en la medida que se cuente con mayores recursos computacionales. Se determinan los mejores métodos para llevar a cabo la reducción del número de escenarios de la instancia original, permitiendo así el manejo abordable de instancias que inicialmente se presentan complejas. Finalmente, la aplicación de la metodología de comparación de rendimiento entre modelos determinísticos y estocásticos fue satisfactoria, determinándose un rango para el número suficiente de escenarios a utilizar dentro del modelo en estudio de tal forma de alcanzar un punto óptimo entre calidad de la solución y el rendimiento computacional del modelo.

Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / En el mundo actual la mayoría de los problemas logísticos son dinámicos; sin embargo, la investigación desarrollada hasta hoy se concentra principalmente en enfoques basados en adaptaciones de algoritmos estáticos. El vertiginoso avance de la tecnología ha incrementado significativamente las posibilidades de diseñar modelos de ruteo dinámico, lo que debe ser explotado para mejorar la eficiencia en problemas reales. En esta tesis se aborda el problema que enfrenta el Servicio Técnico de Xerox en Santiago, el cual es una aplicación real del Problema Dinámico de Ruteo de Vehículos con Ventanas de Tiempo. El objetivo es atender a los clientes con el menor retraso posible dentro de los límites factibles, minimizando a la vez los costos de trasporte. La complejidad de este problema radica principalmente en su naturaleza dinámica, ya que la información de las llamadas se conoce una vez que son recibidas durante el día, por lo que las rutas diseñadas deben ser modificadas para incorporar la nueva información cuando entran al sistema nuevos clientes. Para resolver este problema se desarrolló un algoritmo que utiliza la información histórica de las llamadas para definir Idle Points o puntos de espera, a los cuales acuden los vehículos desocupados para anticipar la demanda futura y minimizar los tiempos de respuesta. Además, se considera un sistema de puntuación según la intensidad de la demanda con el cual se premia la cobertura de las zonas con mayor intensidad de demanda y un esquema de Generación Dinámica de Columnas, en el se utilizan las rutas generadas anteriormente para diseñar nuevas columnas cada vez que surge una nueva solicitud de un cliente. El modelo fue implementado computacionalmente en C++ utilizando Ilog Cplex como motor de optimización, con el fin de realizar simulaciones con datos disponibles de la operación real y evaluar su desempeño en comparación a una versión dinámica de un algoritmo Greedy. Respecto a este benchmark se obtienen mejoras de 26% en los costos totales evaluando instancias que corresponden a 120 días de operación real de todos los meses del año. Además, se compara el modelo con dos versiones simplificadas para medir el impacto de incluir la información histórica y el covering en el modelamiento. Se observa que ambas componentes del modelo permiten disminuir los tiempos de espera de los clientes. Finalmente se comparan los resultados obtenidos con la operación manual de Xerox, obteniendo mejoras significativas en el nivel de servicio y una reducción de un 23% en el tamaño de flota requerido para la atención. Se concluye que el enfoque propuesto se adapta de manera satisfactoria a problemas dinámicos cuya prioridad es el nivel de servicio ofrecido a los clientes.

Se presenta un método de punto proximal escalarizado inexacto para resolver problemas irrestrictos de minimización multiobjetivo cuasiconvexos definidos en espacios Euclidianos, donde las funciones vectoriales son localmente Lipschitz. Bajo algunas hipótesis naturales, se prueba que la sucesión generada por el método está bien definida y converge globalmente. Seguidamente proporcionando al método propuesto dos criterios de error, se obtienen dos variantes del mismo, y se prueba que las sucesiones generadas por cada una de esas variantes, convergen hacia un punto crítico Pareto-Clarke del problema; también se prueba que al dotar a la función vectorial de ciertas condiciones, la tasa de convergencia de uno de estos métodos es lineal y superlineal. Finalmente para validar el método propuesto y los resultados encontrados, se presentan algunos experimentos computacionales. / Tesis

Plantea el uso de dos escenarios (financiero/gestión y de venta) para el cálculo de la eficiencia global y técnica de cada oficina y propone un sistema de ranking en base a la eficiencia media, análisis de ventana de tiempo y recurrencia como referencia en las soluciones para brindar a la gerencia una herramienta útil de gestión de la red de oficinas. El análisis fue realizado sobre una muestra de 110 oficinas sobre un horizonte temporal de 6 meses, con una aplicación del enfoque Output en su forma envolvente. Las variables de entrada consideradas incluyeron los arribos a los diferentes canales de atención de la oficina, cantidad clientes y capacidad instalada. Por otro lado, las variables de salida estuvieron relacionadas a las ventas, saldos, margen financiero y volumen de transacciones. / Tesis

Doctor en Ingeniería de Minas / Scientific and engineering efforts in mine planning theory are focused on improving the speed and size capacity of existing algorithms. They look for changing from minutes to seconds, and hundreds of thousands to million blocks of an ore body representation. However, mining practices are so full of manual work and personal decisions, that algorithmic solutions are changed considerably by the mine planner, lasting weeks in this process to achieve operative final results. This thesis proposes a different point of view, joining some of such hand work decisions, like design and ore body modeling. The developed work concentrates on parametric representations of mine design and an ore body model, through volumes and morphological tools, optimized by simulated annealing. It is shown that it is possible to model and optimize a final open pit, with road, benches and switch-backs design and to fit an ore body with parametric volumes, which include geological knowledge. The principal applications of such results are: mine design could be obtained in minutes instead of weeks, the project value will not change because of handmade decisions, mine operation and geological units will have a common language through parametric volumes, geostatistical predictions will depend on geological knowledge and fitted data, geological uncertainty would be modeled from parameter stochasticity, so stochastic optimization could be implemented from simulations. In fact, mine planning algorithm inputs would no longer be a block model, but directly drill hole data. Despite that some numeral examples were developed, real cases were not the scope of this thesis work. The value of this work concentrates on proposing ideas and a new field of investigation in mine planning, focused on more realistic mining needs and bringing different tools, as those that until today were the paradigm, and trying to join professional areas that work separately.

Tesis para optar al grado de Doctor en Ciencias de la Ingeniería, Mención Ingeniería Química y Biotecnología / Nowadays, the increase in the industrial production is causing environmental problems when appropriate planning and control are absent. To overcome this situation, the Eco-Industrial Parks (EIPs) arise as a new way to plan and design industrial complexes, where the companies located together are connected with each other to achieve sustainability advantages for its participants and the sector. Since these advantages depend on its configuration, a proper planning and design is critical. Moreover, the stability of this network plays a significant part when a participant suffers a stop in production. This work seeks to propose a mathematical-based design of an EIP to promote and support the implementation of industrial networks with sustainability and security objectives. To achieve this goal, (i) a database of sustainability indicators is built and four criteria for their selection are proposed; (ii) a resilience indicator for EIPs is defined to improve their operation security; and (iii) a multi-objective optimization problem is formulated to design EIPs. A significant set of sustainability indicators are listed and classified regarding the number of assessed dimensions: \textit{single}, if one sustainability dimensions is assessed, and \textit{integrated}, if two or three are assessed. Moreover, to select a subset of proper indicators, four criteria are proposed: understanding, pragmatism, relevance, and partial representation of sustainability. An indicator is constructed and proposed to follow the resilience of an EIP, improving the security of the whole system by considering the dynamic of the participants to endure a disruptive event. This indicator is based on two main characteristics of an industrial network: its topology and its operation; which are respectively assessed by the weighted sum of two sub-indicators: Network Connectivity Index (NCI) and Flow Adaptability Index (φ). A multi-objective optimization model is constructed based on the industrial complex of Ulsan, in South Korea, in order to design a sustainable and resilient EIP. This model considers a subset of sustainability indicators and the proposed resilience indicator. The sustainability indicators are filtered with the four criteria for selection. The resulting configurations improve all the considered aspects at the same time, allowing to design an EIP with focus on its sustainability and resilience. The use of the resilience indicator as an additional objective allows to compose an EIP with an improved adaptation to reality, addressing the reluctance of the industries to participate in this industrial network. Finally, the optimization model achieves the systematic design of new EIPs, considering the sustainability and resilience aspects as objectives in the optimization. This tool could play an important role in supporting decision-makers to design industrial networks, generating new, more sustainable and more resilient alternatives. / CONICYT-PCHA/Doctorado Nacional/2014-21140400

Actualmente, la investigación en el sector energético se encuentra en continuo desarrollo. Asimismo, el número de ingenieros diseñadores de centrales hidroeléctricas aplicables a las condiciones del Perú está en aumento, lo cual se evidencia en la ampliación de nuevos proyectos hidroeléctricos. Sin embargo, solo se ha explotado un 5% del potencial hidroenergético en el país. Por ello, para contribuir con la investigación, la presente tesis propone 3 aspectos a considerar en el plan de diseño de tuberías forzadas en centrales hidroeléctricas de agua fluyente para una etapa de prefactibilidad: un análisis económico de los costos para la optimización del diámetro, un conjunto de simulaciones fluido-dinámicas mediante el uso del software ANSYS, y un predimensionamiento de las estructuras que componen la tubería forzada. El análisis económico de la tubería forzada se centra en definir el diámetro óptimo de diseño mediante dos métodos: el método tradicional (Mosonyi, 1965) y el nuevo método detallado que propone la presente tesis. El primero consiste en una comparación de costos anuales entre las partidas de mantenimiento y costo de energía no vendida. El segundo método consiste en la comparación de costos de inversión de diferentes variables entre los cuales se pueden encontrar los costos de equipamiento hidromecánico, concreto, transporte, excavación, montaje, bajo dimensionamiento y mantenimiento. Estos factores mantienen una relación directa con el diámetro que se le asigne a la conducción a presión por lo que se pueden estimar costos en función a dicho diámetro para establecer el diámetro óptimo. Con respecto a las simulaciones fluido-dinámicas, el software ANSYS permite estudiar los efectos que se presentan frente a disminución del diámetro que solo se había analizado mediante la teoría básica de la mecánica de fluidos. Mencionado estudio brinda una justificación más sólida al análisis económico ya que presente el mismo nivel de precisión que los modelos realizados a escala. En síntesis se podrá corroborar y dar mayor alcance a los criterios empleados en el análisis económico. Después de establecer el diámetro óptimo, se elaboran los diseños de las diferentes estructuras que componen la tubería forzada. Entre ellas se encuentran los machones verticales, bloques de apoyo, juntas de expansión, abrazaderas, anclajes y espesor de la tubería. Se exponen los criterios que se deben tener en cuenta para dimensionar cada una de las partes de la conducción a presión. El diseño es realizado a un nivel de pre-factibilidad, es decir, se omiten los cálculos correspondientes a la ingeniería de detalle, pero se establecen cálculos y consideraciones necesarios para establecer una geometría adecuada. / Tesis

La mesa de ayuda es un área importante en la resolución de incidentes de tecnologías de información en las empresas, tanto dentro (para la misma empresa y sus empleados) como fuera (para los clientes que la empresa ofrece sus servicios y productos). Sin embargo, la planificación de la resolución de incidentes se hace difícil debido a la imprevisibilidad y espontaneidad de éstos. Dichos incidentes afectan de manera diversa a la continuidad de negocio con consecuencias y tiempo de resolución de diversa magnitud. Asimismo, los técnicos en la mesa de ayuda tienen un tiempo de resolución diverso, con experiencia laboral distinta y son un número finito de personas. Dicho problema se le conoce en problemas de asignación de tareas como “asignación estocástica en línea”. El algoritmo MinIncrease permite la resolución de problemas de asignación estocásticos en línea. Sin embargo, el problema reside en que los técnicos son personas de diversa experiencia que pueden estar divididos en técnicos con mucha o poca experiencia en el ambiente de una mesa de ayuda. No es preciso que al mejor técnico se le asignen incidentes triviales ni que algún técnico no trabaje hasta que aparezca un incidente de su dificultad apropiada. Es por ello que el algoritmo MinIncrease sólo no basta. El siguiente proyecto presenta el diseño de un algoritmo metaheurístico GRASP para la mejoría de un algoritmo MinIncrease. La combinación de estos algoritmos permitirá que los incidentes, a pesar de que su aparición sea imprevista, puedan asignarse a los técnicos de la mesa de ayuda de manera eficiente. / Tesis