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.

En este trabajo nos concentramos en optimizar el proceso de la planificación de la producción en la etapa de agua-mar en una empresa salmonera. La planificación de la producción en agua-mar consiste en programar las fechas futuras de ingreso y salida de salmones de cada uno de los centros de engorda en agua-mar que posee la salmonera, considerando un horizonte de planificación de 5 años. El objetivo de la planificación es maximizar la biomasa recolectada en un horizonte de tiempo considerado, sujeto a cumplir con diversas restricciones de carácter biológico, económico y sanitario. Para resolver el problema proponemos una formulación de programación lineal entera mixta y se estudian algunas de sus propiedades teóricas, llegándose a la conclusión de que es una buena formulación. Además, como los tiempos de ejecución del modelo deben ser pequeños, diseñamos un algoritmo ad-hoc, que permite reducir notablemente los tiempos de corrida del modelo. Se presentan experimentos numéricos que permiten ilustrar el buen comportamiento de la formulación y los resultados obtenidos por la metodología de reducción de tiempos. Por otro lado se realiza un análisis de las soluciones del modelo y una comparación entre las decisiones que se toman con la metodología actual de planificación y las decisiones que sugiere el modelo. Basados en el trabajo realizado, se puede concluir que estas metodologías empleadas para resolver el problema de planificación de la salmonera, en instancias de tamaño no real, resultan ser eficientes, pues se mejora la calidad del programa de siembras en agua-mar aumentando la cantidad de biomasa total cosechada y logrando el cumplimiento de buenas prácticas que, dada la complejidad del problema son difícil de cumplir con la metodología actual. Finalmente, como se puede ver en la sección de resultados computacionales, se logran reducir notablemente los tiempos asignados a la planificación misma.

El presente trabajo muestra la implementación de metodologías basadas en modelos de optimización para resolver el problema de programación de horarios de clases y asignación de salas para la Facultad de Ingeniería de la Universidad Diego Portales. Los métodos utilizados en este trabajo integran la programación de los horarios de las clases de cátedra y de las clases auxiliares de todos los cursos de jornada diurna que se dictan en la Facultad, con su respectiva asignación de salas. Para resolver el problema se implementaron tres metodologías basadas en modelos de programación lineal entera. La primera metodología consiste en un modelo único que pretende resolver el problema completo, cumpliendo con todas las condiciones impuestas por la Facultad, basando sus decisiones en la asignación de cada una de las clases a algún bloque horario y a una sala disponible. La segunda metodología consiste en dos modelos: el primero, para resolver la programación de horarios de clases y el segundo, para resolver la asignación de salas. Ambos modelos operan en forma secuencial, basando sus decisiones en la asignación de cada una de las clases a algún bloque horario y a una sala disponible. La tercera metodología utiliza el concepto de grupos de bloques horarios, que consiste en conjuntos de uno, dos o tres bloques horarios de la semana. Esta metodología se basa en un modelo único que resuelve la problemática completa basando sus decisiones en la asignación de todas las clases de cátedra o auxiliares de un curso a un grupo de bloques horarios y a una sala disponible. Las metodologías segunda y tercera se pretenden utilizar en semestres posteriores para llevar a cabo esta labor de manera automática y evitar ineficiencias de la actual programación manual. Los resultados obtenidos se resumen como una programación de horarios que cumple con todos los requerimientos exigidos y una asignación de salas que cumple con los requisitos de capacidad de cada curso. El tiempo de resolución del problema es inferior a una hora.

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.

Tesis para optar al grado de Magíster en Gestión de Operaciones / Memoria para optar al título de Ingeniero Civil Industrial / En el marco de una extinción global de especies y de recursos limitados disponibles para la conservación ecológica, emerge la urgente necesidad de priorizar tanto la selección de sitios como los esfuerzos de gestión de las intervenciones para hacer frente a las amenazas. Con la finalidad de asegurar la persistencia de aquellas especies en peligro de extinción, se toman acciones específicas para disminuir las amenazas que las afectan. Normalmente, se utiliza un enfoque binario, en donde se efectúa una acción específica y se asume que ésta elimina la amenaza. Por lo tanto se considera que, para reducir los costos, no es necesario tomar acciones en su valor total, pues se puede considerar una curva que relaciona la intensidad de la amenaza existente y la probabilidad de persistencia de las especies. De igual forma, se tiene en cuenta el efecto de minimizar la fragmentación espacial y los costos totales. Dicho modelo se pone a prueba en un caso de estudio de la cuenca del río Mitchell, al norte de Australia. Este modelo consiste en el intento de asignar un esfuerzo óptimo para aumentar la probabilidad de persistencia de 45 especies nativas de peces de agua dulce. Se comparan los resultados obtenidos para cuatro curvas de respuestas continuas de las especies, con un escenario base de respuestas binarias. Para representar especies sensibles a las amenazas, se utiliza una curva convexa, y para las menos sensibles se utiliza una curva cóncava. Cabe destacar que se mide la eficiencia como una relación entre el área protegida y los costos totales incurridos. Se demuestra que no hay diferencias significativas en los resultados cuando las respuestas a las acciones son convexas y lineales, como es de esperarse. Por el contrario, se logra percibir que existen beneficios en la eficiencia cuando se considera una curva sigmoidal, y aún más cuando se considera una curva cóncava, lo cual hace que esta propuesta se vuelva más atractiva que los métodos tradicionales. Por otro lado, cuando se exige un mayor nivel de conectividad para las acciones, los niveles de eficiencia se mantienen prácticamente iguales, y las respuestas continuas logran soluciones mejor conectadas que aquellas logradas por la respuesta binaria. Al considerar este modelo, se puede identificar de manera eficiente el nivel de esfuerzo óptimo que será asignado a múltiples intervenciones, tal como el dónde realizarlas para combatir las amenazas existentes. / SuFoRun y ISCI por medio del programa Marie Sklodowska-Curie

El objetivo general de la investigación es la determinación de la contribución total máxima mediante la asignación óptima de máquinas a órdenes de producción, para lo cual se hace uso de un modelo de Programación Lineal Entera. Se ha probado la hipótesis que si se determina la asignación óptima de máquinas a órdenes de producción con el modelo de Programación Lineal Entera, entonces, el margen de contribución total mensual que perciba la empresa será el máximo. La metodología empleada fue no experimental, transeccional y descriptiva. Se usó una muestra no probabilística de tres máquinas de diferente tipo. Las principales conclusiones a que se arribaron es que para la realización de un estudio de este tipo no se necesita grandes inversiones económicas ni tecnológicas, pues contando con recursos limitados se ha logrado desarrollar el presente estudio, que es el de brindar una herramienta útil y necesaria para que las organizaciones puedan optimizar la utilización de sus recursos y maximizar sus contribuciones y de esta manera cumplir con sus obligaciones como tal. / --- The overall objective of the research is to determine the maximum total contribution through the optimum allocation of machines to production orders, which uses an Integer linear programming model. It has tested the hypothesis that if it determines the optimal allocation of machines to production orders with the Integer linear programming model, then the total monthly contribution margin earned the company will be the maximum. The methodology used was non-experimental and descriptive transectional. We used a sample of three different types of machines. The main conclusions reached is that a study of this type do not require large financial investments or technology, because with limited resources has been developed for this study, which is to provide a useful and necessary so that organizations can optimize the use of its resources and maximize their contributions and thus fulfilling its obligations as such.

Magíster en Ciencias de la Ingeniería, Mención Ingeniería Eléctrica / El trabajo de tesis compara en forma sistemática las diferencias de rendimiento entre las principales metodologías de solución del problema de Predespacho (UC) y muestra la aplicación de la relajación lagrangeana a casos reales del Sistema Interconectado del Norte Grande (SING). Se propone una metodología para la creación de casos sintéticos de UC que permitan obtener diversidad a distintas escalas sin que resulten alejados de la realidad, siendo ésta la principal contribución del presente trabajo junto con los resultados estadísticos que favorecen MIP por sobre LR para sistemas de medianas dimensiones. La relajación lagrangeana (LR) y la programación entero mixta (MIP) son los métodos de solución que han encontrado el mayor número de aplicaciones prácticas al UC. Sin embargo, las comparaciones de rendimiento y calidad entre ambas, aunque propuestas conceptualmente y cuyas nociones intuitivas se encuentran dispersas en la bibliografía especializada, adolecen de falta de generalidad, escasa representación de la realidad, ausencia de especificaciones computacionales o, inclusive, éstas pueden haber quedado obsoletas. Ante la escasez de librerías de modelos de UC o, al menos, de métodos de creación de casos de aplicación, en el presente trabajo se propone y aplica un generador de casos sintéticos de prueba de UC. Este método formula casos basados en la combinación de datos estandarizados con la generación aleatoria de parámetros. De esta forma, los problemas de UC creados adquieren diversidad (universalidad) sin que las instancias se alejen demasiado de la realidad. La diversidad de las instancias generadas es controlada mediante los parámetros de las funciones de distribución de probabilidades, tanto para la selección de unidades candidatas como para la variedad en los parámetros técnicos característicos. Estas instancias son resueltas por los métodos para resolver el UC en una misma plataforma computacional. El método de LR encuentra soluciones factibles para 429 instancias de las 480 (89,4%), cumpliendo con el gap objetivo de 0,01% en tan sólo 90 casos (18,8%), mientras que el MIP encuentra la solución óptima para el 98,3% de los casos. Los resultados obtenidos verifican que para el rango de 10 a 100 unidades, la mejor solución entera factible alcanzada por LR tiene una menor calidad (valor mayor de la función objetivo en problemas de minimización) que la encontrada por el optimizador MIP. Los resultados permiten determinar que el sobrecosto (respecto al MIP) esperado de las soluciones mediante LR fue de 6,03%. El aumento de la dispersión en los parámetros técnicos beneficia ambos métodos al obtener la mejor solución factible en menores tiempos de ejecución. De esta forma se muestra que no sólo la calidad de la solución por LR se ve afectada por unidades similares, sino que también afecta al método MIP. Se comprueba que a medida que los problemas son más difíciles (juzgando por la adaptabilidad y por el número de unidades), la cota inferior de LR resulta en promedio mayor (mejor) a la cota inferior promedio por MIP. Respecto al caso práctico inspirado en el SING, la calidad de la solución por LR se ve especialmente deteriorada cuando las restricciones de mínimos técnicos de las unidades obligan que la solución óptima entera se aleje de la relajación lineal. Si bien para este caso la resolución mediante MIP también se dificulta requiriendo de hasta un 60% más tiempo de ejecución, este efecto es comparativamente menor al deterioro de la calidad de la solución observada mediante LR (que resulta hasta 4.5% mayor que MIP). Conceptualmente, este hallazgo se explica por los valores de actualización de los multiplicadores en LR, lo que se traduce en imposibilidad para explorar zonas del espacio de soluciones. Como conclusión general, el estudio entrega evidencia práctica a favor de la tendencia observada en la revisión bibliográfica en relación a privilegiar desarrollos de tipo MIP, la cual es aplicable a sistemas medianos como el caso real en estudio basado en el SING chileno. Esta conclusión no se extiende para otros sistemas reales de grandes dimensiones (eg. CAISO, MISO, UCTE). Como futuros desarrollos se sugiere explorar esquemas integrados LR-MIP explotando las mejoras de la cota inferior que proporciona LR en comparación con la relajación lineal del MIP y la creación de soluciones factibles por el método LR para inicializar el MIP.

El objetivo general de la investigación es la determinación de la contribución total máxima mediante la asignación óptima de máquinas a órdenes de producción, para lo cual se hace uso de un modelo de Programación Lineal Entera. Se ha probado la hipótesis que si se determina la asignación óptima de máquinas a órdenes de producción con el modelo de Programación Lineal Entera, entonces, el margen de contribución total mensual que perciba la empresa será el máximo. La metodología empleada fue no experimental, transeccional y descriptiva. Se usó una muestra no probabilística de tres máquinas de diferente tipo. Las principales conclusiones a que se arribaron es que para la realización de un estudio de este tipo no se necesita grandes inversiones económicas ni tecnológicas, pues contando con recursos limitados se ha logrado desarrollar el presente estudio, que es el de brindar una herramienta útil y necesaria para que las organizaciones puedan optimizar la utilización de sus recursos y maximizar sus contribuciones y de esta manera cumplir con sus obligaciones como tal. / The overall objective of the research is to determine the maximum total contribution through the optimum allocation of machines to production orders, which uses an Integer linear programming model. It has tested the hypothesis that if it determines the optimal allocation of machines to production orders with the Integer linear programming model, then the total monthly contribution margin earned the company will be the maximum. The methodology used was non-experimental and descriptive transectional. We used a sample of three different types of machines. The main conclusions reached is that a study of this type do not require large financial investments or technology, because with limited resources has been developed for this study, which is to provide a useful and necessary so that organizations can optimize the use of its resources and maximize their contributions and thus fulfilling its obligations as such.

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.

Ingeniero Civil Industrial / El presente Trabajo de Título versa sobre el problema de asignar recursos cuando estos son escasos, permitiendo un mejor control de quiebres y de costos asociados para la empresa interesada en la eficiencia y entrega de un buen servicio. Se presenta el caso particular de asignación de cajeros para un grupo de 39 estaciones de la red de Metro S.A., encargadas a un Operador de contratos. Este Operador tiene bajo su responsabilidad la respuesta a los requerimientos de servicio de Metro con el personal que estime conveniente. Las condiciones laborales y propias del problema hacen necesario un análisis detallado en cuanto a definición del problema y levantamiento de información, describiéndose la demanda y oferta actual de personal, analizando los contratos celebrados como también las multas y costos involucrados. Así se presenta una metodología que parte desde este punto para luego generar un modelo de asignación de turnos (Shift Assignment Problem), donde el personal es homogéneo y solo interesa determinar cuánto, cuándo y dónde se necesita personal. Se presenta así la resolución del problema modelado como un Problema de Programación Entera Mixta (MIP), incorporando distintos tipos de contratos y definiendo el modelo base de la programación y sus variantes. Se desarrolla la estrategia de programar de menos a más y se determina que la solución entregada por el modelo corto de una semana resulta beneficiosa para el Operador y en tiempos de ejecución cortos. Se incorpora una etapa de validación del modelo en la que se compara la solución entregada para el mes de Junio con la del Operador, llegando a una mejora de un 58% de eficiencia en la oferta de Horas Hombre, con una dotación superior en 57 cajeros y con un beneficio por concepto de sueldos superior a los nueve millones de pesos para el total de las 48 mesaninas, repartidas entre las 39 estaciones. En este trabajo se entrega un set de herramientas computacionales, elaboradas con Visual Studio 2010, en lenguaje de Visual Basic, capaces de traducir los requerimientos de servicio a una programación de turnos, permitiendo ejecutar el software de programación empleado (GAMS) de manera remota y modificando el output para ser presentado en un formato estándar de turno. Se desarrolla además una planilla que entrega soporte al área de asignación de cajeros con los turnos generados tras la ejecución del modelo, todo esto usando Macros de Excel, permitiendo al Operador la automatización del proceso y una autonomía de trabajo del mismo, integrando herramientas de TI para una solución completa y amigable.