En el presente trabajo de tesis se realiza un Análisis Situacional a la Empresa Grupo Digigraf S.A., haciendo uso de la metodología del Enfoque Sistémico o Enfoque de Sistemas. El análisis Situacional nos brinda información que sirve de guía para enfocar la realidad de la Empresa. Luego de realizar un análisis minucioso de todos los subsistemas de la institución, se determina que la Empresa cuenta con un serio problema de baja rentabilidad económica que debe resolver; continuando con el Análisis de los procesos internos, se logra identificar que la causa principal que genera este problema es el mal procedimiento que utiliza la empresa para realizar los cortes de rollos de película que se utilizan como insumo principal en el proceso de producción. Para resolver el problema se utiliza la Programación Lineal que permite construir un Modelo Matemático que describe el problema y para cuya solución utilizamos el Método Simplex que permite obtener la solución optima que permitirá solucionar el problema y por ende mejorar la situación de la Empresa. Finalmente, se propone este modelo de solución el cual remplazará la metodología actual que realiza la empresa, y se recomienda su pronta implementación, para poder favorecer el mejoramiento de la Empresa. / --- In this Thesis work is carried out a Situational Analysis to the Grupo Digigraf S.A. Enterprise, using the Systems Approach Methodology or Systemic Approach. The Situation Analysis provides us with information that guides us to set focus in the reality of the Company. After to make a thorough analysis of all company subsystems, is determined that the company has a serious problem of low profitability economic to be solved; continuing with the analysis of internal processes, is possible to detect that the main cause that generates this problem is the wrong method using by the company to make cuts rolls of film used as the main input in the production process. To solve the problem is used the Linear Programming that permit build a mathematical model that describe the problem and to solve it we used the Simplex Method for obtain the optimal Solution that will resolve the problem and therefore improve the Company Situation. Finally, is proposed this model of solution which will replace the current methodology is performed in the company, and is recommended for early implementation, in order to promote the improvement of the Company. / Tesis

Las gramáticas de atributos, desde que fueron propuestas por Knuth en 1966, se han utilizado ampliamente para el desarrollo de herramientas de procesamiento de lenguajes formales como compiladores e intérpretes de lenguajes de programa-ción; como también para especificar la semántica de lenguajes. Las gramáticas de atributos son un formalismo simple para la especificación de la semántica de lenguajes formales, como ser lenguajes de programación o de especifi-cación. Integran la modularidad que brindan las gramáticas libres de contexto y la expresividad de un lenguaje funcional. Si bien las gramáticas de atributos han sido ampliamente estu-diadas no es fácil encontrar definiciones precisas y rigurosas. Los principales motivos del desarrollo de esta tesis son en primer lugar, obtener un material autocontenido sobre sus defi-niciones, extensiones, implementación y aplicaciones, ya que prácticamente no existen libros actualizados en el tema. En segundo lugar, se realiza un estudio profundo sobre nuevas clasificaciones propuestas y métodos de evaluación. En este último aspecto es donde se presentan los aportes más signifi-cativos de esta tesis. En este trabajo se presentan las gramá-ticas de atributos en su forma clásica, mostrando definiciones más precisas que las que se pueden encontrar en la bibliografía tradicional. Se describen diferentes clasificaciones y métodos de evaluación secuenciales y concurrentes. Entre los principa-les aportes de este trabajo, se propone un algorimo eficiente de evaluación dinámica bajo demanda, que puede aplicarse para la evaluación de cualquier gramática de atributos bien definida (no circular). Este algorimo se ha implementado en la herramienta agcc, la cual ha sido desarrollada en el marco de este trabajo. Se analiza una nueva clasificación, la jerarquía NC, propuesta por Wuu Yang en 1999 y se relaciona con la clasificación tradicional. Se describe NCeval, una herramienta desarrollada en el marco de esta tesis, la cual genera evalua-dores estáticos para la familia NC(1). Un evaluador generado por NCEval realiza la evaluación disparando procesos o tareas concurrentes que no requieren sincronización, ya que operan sobre conjuntos independientes de instancias de atributos. El método de particionado usado en NCEval está basado en las dependencias y se demuestra que la partición inducida sobre el conjunto de atributos es la mas fina posible. Hasta el momento, no se conocen herramientas que utilicen este enfo-que. Finalmente se describe agcc (Attribute Grammars Compiler Compiler), herramienta desarrollada en el marco de esta tesis, la cual tiene un diseño totalmente modular per-mitiendo su extensibilidad tanto en los generadores de código como en los métodos de evaluación utilizados. Acepta la familia más amplia de gramáticas de atributos para las cuales pueden generarse evaluadores estáticos

El presente trabajo tiene como objetivo la implantación del VRP Solver para poder minimizar las distancias utilizadas en el envío de productos de una empresa distribuidora. Para la determinación de la solución que se adapta al problema, se realiza evaluaciones por criterios de los modelos, heurísticas, y algoritmos analizados, lo cual da como resultado, que el modelo que se adapta a la solución del problema es el modelo VRP, con la heurística de Clarke Wright y el algoritmo de Búsqueda Tabú. El software implantado precisamente utiliza la heurística de Clarke Wright para minimizar distancias, tomando como datos de entradas, la ubicación de cada cliente y dando como resultados las rutas optimas, con las pruebas realizadas, se logra disminuir en un 10% la distancia total utilizada en las rutas de la empresa del caso de estudio. / 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.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / La presente tesis consiste en presentar la resolución del problema de asignación de turnos de trabajadores que tiene una cadena de retail en el rubro farmacéutico. Para ello se dará a conocer la realidad de esta farmacia, donde se detallarán las restricciones, reglas de negocios, número de trabajadores, distintos tipos de contratos, entre otros. La farmacia hoy en día ha visto que en momentos de baja como de alta demanda existe sobre-dotación y sub-dotación de personal, lo cual ha mostrado la necesidad de una herramienta para programar los turnos de forma óptima. El objetivo de esta tesis es la creación de un modelo y algoritmo que permita optimizar y planificar las dotaciones del personal de ventas cumpliendo con la demanda, reglas de negocio y restricciones legales de manera de minimizar los costos dentro de los locales. También se busca encontrar cotas del problema original a través de una metodología de generación columnas para poder medir el rendimiento técnico de la heurística. Los objetivos específicos es encontrar los requerimientos mínimos de personal; determinar el número de personal óptimo; hacer uso más eficiente de la horas, encontrando turnos que permitan distribuir de manera más eficiente el personal diario; generar más contratos de tipo part-time que permitan adecuarse de mejor manera a la demanda, y asignar turnos a trabajadores que no están sujetos a demanda de acuerdo a un criterio definido. Actualmente el sistema está implementado en aproximadamente 100 locales. En la fase de piloto, con 14 locales en funcionamiento, las ventas aumentaron 0,5 %, se redujeron costos de personal en 2,5 %, las horas extras disminuyeron 36 %, y se incrementó las comisiones de los vendedores en 1 %. Entre las mejoras cualitativas encontramos la estandarización de procesos, cumplimiento de la ley vigente, lo cual permite evitar multas, como también una rotación del personal que prohibe que se generen derechos adquiridos de los vendedores. Por otro lado, se demostró que las soluciones de asignación de los turnos están a menos de un 8 % del óptimo.

El presente proyecto de fin de carrera corresponde a la construcción de un entorno de desarrollo que permita la ejecución y ejecución de pseudocódigo como herramienta de apoyo a las etapas de diseño, ejecución y validación de un algoritmo. Se permitirá la traducción a VBA, Java, Ruby, Python y c++. El documento presenta siete capítulos, en el primer capítulo se describen generalidades del proyecto como la problemática, objetivo general, objetivos específicos, resultados esperados, alcance, justificación, viabilidad y plan de actividades del proyecto. En el segundo capítulo se presenta el marco conceptual donde se describen los conceptos necesarios para entender el problema que se desea solucionar con el presente proyecto. En el tercer capítulo se presenta el estado del arte. En lo referente al estado del arte se realizó una búsqueda entre productos comerciales y no comerciales que intentan solucionar algunos aspectos del problema a resolver. En el cuarto capítulo, se describe cómo se realizó la definición y la validación de la gramática del pseudocódigo mediante el uso de la notación BNF. En el quinto capítulo se presenta el desarrollo del intérprete que permite la ejecución del pseudocódigo y del traductor que permitirá transformar el pseudocódigo a código en VBA, Java, Ruby, Python y C++. En el sexto capítulo se realiza la descripción del entorno de desarrollo que permitirá la integración del intérprete y traductor para que puedan ser utilizados por el usuario final. En el séptimo capítulo se exponen las conclusiones. / Tesis

Este proyecto de fin de carrera parte de la ausencia de herramientas que sirvan de ayuda para aquellos alumnos que quieran aprender a programar. Si bien existen programas que permiten generar diagramas de flujo y luego exportarlos a un lenguaje de programación, estos no poseen un compilador que permita detectar errores de sintaxis, que pueda poseer la solución. Por ello se plantea implementar un proceso de traducción y verificación de programas diseñados en diagrama de flujo utilizando como paso intermedio pseudocódigo, para que el alumno pueda preocuparse más en la lógica de su solución, que en la sintaxis o estructura del lenguaje de programación, a codificar. Para realizar este proyecto se definió una serie de objetivos específicos. En primer lugar se desarrolló un entorno para dibujar diagramas de flujo, para ello se adaptaron las librerías de Microsoft office que ofrecen las herramientas necesarias para la creación del entorno de trabajo. Luego, se definió la gramática que almacena la sintaxis del pseudocódigo utilizando la notación Backus-Naur Form (BNF). Después se implementó el método de conversión del formato XML de Microsoft office, representación del diagrama de flujo, a pseudocódigo utilizando la sintaxis definida anteriormente y un editor de texto en el cual se muestre el resultado de la conversión al usuario. Finalmente se implementó el intérprete que utiliza la gramática para verificar que el código se encuentre léxicamente, sintácticamente y semánticamente correcto. De esta manera los alumnos podrán obtener a partir de un diagrama, el cual al ser gráfico es de fácil entendimiento, el código de su programa sin necesidad de conocer la sintaxis del mismo y validado. / Tesis

Con el surgimiento de los lenguajes de programación y el gran interés que estos atraen, cada vez hay más personas que deciden sumergirse a este mundo. Otro punto a tomar en cuenta es que no solo hay un estilo de programación sino que la programación puede estar sujeta a diversos paradigmas, siendo estos el paradigma estructurado, el paradigma orientado a objetos, el paradigma orientado a eventos, entre otros. Si bien los diversos paradigmas se relacionan entre ellos, es decir tienen características afines; en ocasiones, no es fácil para las personas dar un salto de un paradigma a otro. Otra dificultad existente suele ser que existen diversos lenguajes de programación orientados a un mismo paradigma lo que genera usualmente confusión en la definición de conceptos propios de dicho paradigma, a causa de las diferentes sintaxis y alcances que poseen estos lenguajes. El propósito del proyecto es centrarse en la adaptación al paradigma orientado a objetos, definiendo así que problemas se presentan para su correcto aprendizaje; así como también buscar las soluciones existentes y proponer una solución de mejora que conlleve a su correcto aprendizaje. / Tesis

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.