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 / 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 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.

No description available.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / El sistema MUCH, desarrollado en conjunto por la Universidad de Chile y la empresa CODELCO, es una herramienta de optimización y evaluación de proyectos mineros cuyo motor es un modelo de programación entera mixta que describe las operaciones mineras de largo plazo. El módulo Minería a Rajo Abierto del sistema es utilizado activamente en el proceso de planificación de proyectos de minería a cielo abierto de gran envergadura, por lo que su desarrollo y mejora continua son fundamentales para que la herramienta responda a las complejidades que involucra su aplicación. El objetivo del presente trabajo de tesis es producir una mejora sustancial en el proceso de construcción de soluciones del módulo Minería a Rajo Abierto del sistema MUCH. Se establecen dos frentes de mejora. Como primer frente, se considera extender la formulación del modelo matemático actual, permitiendo la existencia de bancos que pueden ser extraídos en más de un periodo. Como segundo frente, se considera desarrollar un método heurístico automatizable que permita la generación de soluciones enteras con un rendimiento superior, en términos de la calidad de la función objetivo y el tiempo de ejecución, al de las heurísticas actualmente utilizadas en el sistema. El problema se aborda en tres etapas. Primero, se realiza una investigación donde se recopila información para definir el problema y las posibles fuentes de mejora. Segundo, se diseña una solución considerando los antecedentes reunidos y los objetivos establecidos. Por último, se valida la solución mediante un set de experimentos. Los resultados obtenidos son un modelo de programación entera mixta que describe de manera más fidedigna las operaciones de extracción de rajo abierto, y un método de solución para la construcción de planes mineros que constituye una mejora sustantiva al motor de optimización del módulo Minería a Rajo Abierto del sistema MUCH.

La presente tesis doctoral aborda el análisis y modelización de los problemas de programación en el corte de perfiles estructurales de acero, así como la propuesta de diferentes metodologías y algoritmos basados en técnicas heurísticas que permiten resolverlos de manera óptima. En concreto se profundiza en los siguientes temas: - Se estudia la problemática concreta en el corte de vigas estructurales en una empresa de transformados metalúrgicos. Dicho estudio motiva y justifica todo el trabajo posterior, a la vez que proporciona un contexto concreto en el que aplicar de forma práctica los resultados obtenidos con los algoritmos desarrollados. - Se modeliza matemáticamente el Problema del Corte de vigas a partir de perfiles estructurales. - Se presenta una metodología que resuelve de manera eficiente, mediante el uso de patrones, el Problema del Corte para satisfacer la demanda de vigas en un periodo concreto. A tal efecto se desarrolla: un primer algoritmo genético que genera patrones de corte idóneos (fase 1); un segundo algoritmo genético que determina las frecuencias de uso de cada patrón para minimizar tanto el desperdicio como la sobreproducción (fase 2); y cuatro algoritmos adicionales que mejoran la solución obtenida en la fase anterior (fase 3). - A fin de evaluar la metodología propuesta, se desarrolla un generador de problemas que a partir de unos parámetros de instancia obtiene distintos problemas de test. - Se propone otro algoritmo genético para resolver el Problema multiobjetivo de Secuenciación de Patrones optimizando dos objetivos: minimizar las necesidades de espacio para el apilamiento de pedidos en curso y minimizar la extensión temporal requerida para procesar los pedidos. - Finalmente se propone una metodología para la resolución del Problema Global de Corte y Secuenciación. / Gracia Calandin, CP. (2010). Métodos y Algoritmos para resolver problemas de Corte unidimensional en entronos realistas. Aplicación a una empresa del sector Siderúrgico [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7530 / Palancia