Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina menos cargada. En el problema en linea los trabajos son revelados uno a uno sucesivamente, y ante la llegada de cada trabajo el programador debe decidir a qué máquina asignar el trabajo. A diferencia del modelo clásico, donde las decisiones son irrevocables, se considera un modelo dinámico introducido por Sanders et al. \cite{SSS09}. En este modelo, ante la llegada de un trabajo nuevo, algunos trabajos anteriores pueden ser reasignados. Sin embargo la carga total de trabajos migrados debe ser a lo más proporcional al tamaño del trabajo entrante. La constante de proporcionalidad se denomina \emph{factor de migración} del algoritmo, y mide la robustez de las soluciones construidas. En primer lugar se estudian algoritmos de búsqueda local, ya que gran parte de estos algoritmos pueden ser adaptados de manera sencilla al contexto en línea con migración. Se demuestra que para la vecindad de \emph{Saltos} e \emph{Intercambios}, el factor de aproximación de una solución localmente óptima yace en el intervalo $[1.691, 1.723]$. Además, usando técnicas de sensibilidad para programación entera, se da una vecindad para la cual las soluciones localmente óptimas son $(1+\e)$-aproximadas y pueden ser halladas en una cantidad polinomial de iteraciones, obteniéndose un PTAS basado exclusivamente en búsqueda local. Posteriormente se analizan y diseñan algoritmos para el problema en línea con migración. El primer resultado es una mejora en la cota inferior del factor de competitividad alcanzable con migración constante de $\frac{20}{19}$ obtenida por Skutella y Verschae \cite{SV10} a $\frac{17}{16}$. Luego, utilizando un procedimiento de redondeo para la instancia distinto al usado en trabajos anteriores, denominado redondeo a múltiplos, se diseña una versión en línea de optimalidad local respecto a saltos con factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Modificando esta propiedad levemente, se obtiene un algoritmo $\left(\frac{3}{2} + \e\right)$-competitivo usando factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Finalmente, explotando la simetría otorgada por el redondeo a múltiplos, se diseña una versión en línea de $\LPT$, que es una $(\frac{4}{3}+\e)$-aproximación para el problema de Cubrimiento de Máquinas, con factor de migración $O\left(\frac{1}{\e^3}\log\frac{1}{\e}\right)$. Usando la intuición generada por esta simetría junto a las técnicas de programación entera y \emph{configuraciones} de máquinas, se obtiene un nuevo programa entero para el problema que es más simple y abre las puertas a obtener un PTAS para el problema de Minimización de Makespan en línea cuyo factor de migración tenga dependencia polinomial en $\frac{1}{\e}$, lo que aún es un problema abierto.

Presenta un método que sigue la trayectoria central para resolver un problema de programación lineal. Las ideas están basadas en el trabajo realizado por Kojima, Mizuno y Yoshise [15] y Monteiro y Adler [18]. El método permite deducir un algoritmo conocido como Algoritmo Primal-Dual de pasos cortos y alcanza una complejidad de orden de tiempo, debido a que hace uso de una medida de proximidad. / Tesis

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.

La gestión en deportes es una creciente y muy fértil área para aplicaciones de Gestión de Operaciones. Dentro de una liga deportiva existen múltiples factores económicos y logísticos que la transforman en un interesante elemento de estudio. Hasta la fecha, los investigadores de esta disciplina, conocida mundialmente como Sports Scheduling, se han centrado principalmente en resolver el problema de la programación de partidos o fixtures considerando diversas condiciones, que lo suelen convertir en un problema combinatorial de difícil solución. Estas condiciones se refieren a conseguir mayores beneficios económicos tanto para los equipos participantes como para las entidades organizadoras, mayor equidad deportiva, espectáculos más seguros y torneos más atractivos para el público, entre otros objetivos. Entre las últimas y nuevas aplicaciones del Sports Scheduling se encuentra el problema conocido como TUP (Tournament Umpire Problem) o RAP (Referee Assignment Problem) que consiste en encontrar la mejor programación de los árbitros para un fixture ya definido, considerando diversos factores. El problema se ha estudiado y/o aplicado en Brasil, Inglaterra y EE.UU. a deportes en particular. A pesar que en el torneo de fútbol profesional de Chile existen las condiciones favorables para implementar un sistema automático de asignación de árbitros, este proceso se realiza semanalmente de forma manual, lo que lo transforma en una de las situaciones que mayor desconfianza y problemas trae a lo largo del campeonato. En Chile, desde el año 2005 a la fecha, el Centro de Gestión de Operaciones (CGO) del Departamento de Ingeniería Industrial de la Universidad de Chile elabora el fixture del campeonato de fútbol, tarea encargada por la Asociación Nacional de Fútbol Profesional (ANFP), con excelentes resultados. Se espera que a partir de un futuro cercano, el CGO también elabore la asignación de los árbitros al campeonato de fútbol nacional. Este trabajo presenta un estudio del problema de asignación de árbitros a partidos de un campeonato de fútbol. El modelamiento matemático utilizado incorpora metas de partidos por dirigir y distancias por recorrer, además de novedosas restricciones que buscan hacer la asignación lo más justa y equitativa posible para todos los actores involucrados. El caso de estudio es el campeonato de fútbol chileno de primera división (Primera A). Se obtiene una solución óptima para el modelamiento en tiempos bastante razonables y que satisface todos los requerimientos impuestos. Comparada con la asignación manual realizada para el campeonato del año 2007, las pruebas realizadas presentan una mejora en los indicadores de equidad en la asignación de árbitros y de distancias por recorrer de hasta un 99%. Para su implementación, se diseña una herramienta computacional que permite asistir el proceso de asignación. Además, se propone un modelamiento alternativo y discuten futuras extensiones.

Ingeniero Civil Eléctrico / El presente trabajo de memoria se centra en los beneficios económicos asociado al control topológico de la red de transmisión nacional. Para esto se propone un modelo de programación matemática que co-optimiza el despacho de generación con la topología del sistema (conocido en inglés como el problema de Transmission Switching) mediante una representación lineal entera mixto (MILP por su nombre en ingles de Mixed Integer Lineal Program). Además, se propone un algoritmo de solución mediante una técnica de descomposición que separa el sistema en una cantidad determinada de zonas, que se optimizan por separado y de forma iterativa. La metodología propuesta se aplica en el sistema eléctrico chileno proyectado para el año 2025. El objetivo es analizar las mejoras producidas por los cambios topológicos en la operación del sistema, en especial en términos de costos, vertimiento de generación renovable (solar y eólico) y emisión de CO2. Para esto se comparan soluciones de dos corridas: con y sin control topológico (donde el resto de los parámetros y restricciones se mantienen sin alterar). Los resultados de este trabajo demuestran que el control topológico presenta grandes ahorros en términos de costos (hasta un 7%) y en términos de vertimiento (hasta casi un 100%) para los ejemplos estudiados. Una conclusión de particular interés para operadores y reguladores es que varios tramos de transmisión local/subtransmisión (especialmente en la zona de la Región Metropolitana) podrían operar abiertos para algunas condiciones de operación con el fin de: (i) aumentar la transferencia de energía por el sistema nacional/troncal y (ii) permitir un despacho más económico de la generación hidráulica dentro de la Región Metropolitana.

No description available.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / A partir del año 2005 luego del término a nivel nacional del proceso de implementación de la Reforma procesal penal se ha originado un mayor número de imputados y en consecuencia de condenados cumpliendo sus penas de privación de libertad dentro de los recintos penitenciarios del país. Esto genera una mayor demanda de personal de Gendarmería pues se deben hacer cargo de los recintos penitenciarios que albergan a imputados privados de libertad que están a la espera de condena. Lo anterior ha traído como consecuencia lógica una mayor sobrepoblación de los recintos penitenciarios nacionales, aumentando por consiguiente, la demanda del sistema penal. En esta tesis se abordará el problema de la gestión de personal dentro de los recintos penitenciarios en las condiciones actuales del sistema. En ese sentido, se propone un modelo de programación entera para adecuar los tiempos de trabajo de las personas dentro de ellos. El problema de generar un Scheduling (programación de turnos) será abordado con un método basado en programación entera, tomando en cuenta todas las restricciones propias que enfrenta actualmente Gendarmería (Demanda por cargos , Sistemas de franquía, Polivalencia del personal, Personal existente entre otras, las cuales serán propias al recinto penitenciario en estudio), para complementar el estudio y dado que las ausencias a lugares de trabajo son una variable importante al momento de hacer la programación se desarrolla la versión con incertidumbre del mismo, tomando las probabilidades de falla de personas a puestos de trabajo como otro factor importante para la programación, se construye un algoritmo iterativo el cual toma como entrada las demandas de personal por cargo y las probabilidades de falla y entrega como salida el recalculo de estas demandas, las cuales a su vez conforman una nueva entrada para el problema original sin incertidumbre. En ambos casos como salida se genera una programación de turnos por cada cargo a cubrir y la persona que debe realizarlo en un determinado momento en el horizonte de planificación de la programación. El costo total de una programación corresponde a los costos de incumplir una franquía más el costo de no cumplir la demanda un día dado y el costo de sobre programar personas, es así como usando una simulación tipo MonteCarlo para una semana tipo en el penal Santiago I se aprecia que los costos de la programación determinista con respecto a la programación actual son un 96,9% en el caso de la programación con incertidumbre estos costos caen al 50% lo cuál muestra las potencialidades de este trabajo respecto a mejoras en el servicio. Finalmente cabe mencionar que esta tesis fue desarrollada en conjunto con el departamento de estudios de Gendarmería de Chile y que todos los levantamientos de información mostrados a lo largo del trabajo corresponden a datos reales y actuales de la institución.

El presente trabajo se centra en la confección del fixture de Primera A y del fixture de Primera B del fútbol profesional chileno para su temporada 2009. También se analiza el caso del fixture del Torneo de Apertura 2009 de Argentina. Por su parte, esta tesis tiene por finalidad el ser un aporte en el área de sports scheduling, solucionando los problemas antes mencionados en tiempos prudentes. El modelo de programación entera que se desarrolla para Primera A posee 3272 restricciones y 6426 variables binarias. Un problema de estas características es muy difícil de resolver. En tanto que el de Primera B es un poco más pequeño. Si se intenta dar solución a estos problemas en un computador con 4 GB de memoria RAM y procesador Intel Core 2 Duo 2.20 GHz utilizando GAMS y como solver CPLEX 10.2 no hay solución tras más de 100 horas. La misma situación acontece para el problema del fixture de Argentina. Es por ello que se hace necesario implementar una serie de técnicas y procedimientos que permitan acelerar la obtención de resultados. Los procedimientos implementados en esta tesis permiten obtener soluciones en menos de 5 minutos para Primera A. En tanto que para el problema de Primera B por las particularidades del sistema de torneo existen 3 posibles enfoques de solución. Con uno de los enfoques es imposible obtener soluciones que satisfagan todas las restricciones, con los otros enfoques aquello si es posible, tardándose una de las alternativas desde poco más de 30 minutos a alrededor de 18 horas en arrojar soluciones y la otra obteniéndolas en el orden de los 15 minutos. Por último, el caso argentino se utiliza para validar las técnicas expuestas en este trabajo. Y los resultados que se obtienen para este problema son bastante positivos, lo que permite reafirmar la validez de lo que se expone en esta tesis.

No description available.

No description available.