Una red está compuesta por un conjunto de nodos y un conjunto de aristas que comunican pares de nodos. La confiabilidad de una red es una medida que refleja la capacidad de la misma de continuar operativa frente a posibles fallos de algunos de sus componentes, y se define como la probabilidad de comunicación exitosa entre cierto conjunto de nodos de la red, dadas las probabilidades de funcionamiento de los componentes y la topología de la red. La evaluación exacta de esta medida es un problema NP-difícil, por lo que los algoritmos de cálculo exacto se hacen impracticables para redes de tamaño considerable. Una alternativa es utilizar métodos de simulación y en particular el método Monte Carlo. El algoritmo Monte Carlo estándar, directo o crudo requiere de un gran esfuerzo computacional para lograr estimaciones precisas en redes muy confiables. Por este motivo es de interés el estudio de algoritmos denominados de reducción de varianza. En este trabajo se estudia en particular la técnica de Reducción Recursiva de la Varianza aplicada al cálculo de confiabilidad en redes. Se realiza un estudio comparativo de tres algoritmos: el algoritmo exacto de Generación Completa de Estados y los algoritmos estimativos Monte Carlo Crudo y Reducción Recursiva de la Varianza. Se presentan los detalles de implementación de los algoritmos, los casos de prueba seleccionados para su testeo y los resultados numéricos obtenidos, así como las conclusiones extraídas a partir de los mismos. También se muestra la incorporación de las implementaciones realizadas a la herramienta HEIDI y la construcción de un sitio web para la difusión de este trabajo.

Palabras clave: confiabilidad en redes, grafos, simulación, método Monte Carlo, reducción de varianza, HEIDI

http://www.fing.edu.uy/~mauttone

El presente proyecto tiene como protagonistas fundamentales a las metaheurísticas y a los problemas de optimización combinatoria.  Estos últimos proporcionan el motivo apropiado para conducir nuestra investigación  por el místico mundo de los métodos heurísticos.   Las heurísticas aparecen como una opción poco interesante de resolución para los problemas de tipo P, pero si  constituyen una de las principales vías para abordar problemas de tipo NP.  Por este motivo presentaremos dos casos de estudio:  Corte Mínimo para Grafos (Problema P) y Arbol de Steiner (Problema NP).  Además de ser representados mediante grafos, ambos problemas tienen en común la propiedad de representar Sistemas Coherentes.  Siendo éstos últimos el principal objetivo del presente trabajo.
Se utilizan las metaheurísticas de Algoritmos Genéticos y GRASP.  La primera de ellas basada en lo que se da en llama computación evolutiva y la otra técnica nos conduce por le mundo de los algoritmos  que utilizan estrategia Greedy.

Palabras clave: Optimización Combinatoria, Heurísticas, Metaheurísticas, Sistemas Coherentes, Algoritmos Genéticos, GRASP, Búsqueda Tabú, Árbol de Steiner

Informe

El presente informe detalla el desarrollo e implemetación de un proyecto de Taller V, cuyo objetivo es la resolución de un problema que surge en la Confiabilidad de Redes, el problema del Arbol de Steiner (GSMT). Dado que el problema del Arbol de Steiner es NP-completo, se procedió a resolverel mismo por medio de heurísticas. El algoritmo desarrollado es una instancia de la Metaheurística conocida como Ant Systems. La misma es una abstracción del comportamiento real de hormigas, modelando a estas como agentes con un comportamiento elemental, que se comunican (influencian) entre sí, y trabajan en paralelo para lograr un objetivo común. Además de implementar el algoritmo, se procedió a testear el desempeño del mismo, observándose buenos resultados dentro de determinadas restricciones.

Este informe corresponde al trabajo realizado en un proyecto de Taller V dirigido por el Departamento de Investigación Operativa del Intituto de Computación de la Facultad de Ingenería, acerca del Modelo Mixto de Confiabilidad en Redes. Modelo Mixto se entiende por aquel en el cual se puedn apreciar fallas, tanto en las líneas de comunicación como en los nodos que esas líneas comunican. En trabajos anteriores se han estudiado modelos donde fallan solo las aristas (Modelo de Aristas) y donde fallan solo los nodos (Modelos de Nodos). Además se analiza HEIDI y su posible rediseño en base a una biblioteca de tipos de datos y algoritmos implemetada en C++: LEDA.

Informe

En este informe se presenta el trabajo realizado en el marco de Taller V de la carrera Ingeniero en Computación. Consiste en desarrollar una interface gráfica (bautizada Petripad) para el modelado y evaluación de la confiabilidad y performance de sistemas. Dicha interface gráfica es una herramienta para modelar sistemas utilizando el formalismo de las redes de Petri estocásticas generalizadas. Con respecto a la evaluación de la confiabilidad y performance de los sistemas modelados, esta herramienta genera automáticamente la especificación del modelo a los efectos de usarla como entrada de los programas de cálculo correspondientes.

Informe

El presente trabajo trata el problema de la organización del tránsito urbano, específicamente la del transporte colectivo de pasajeros en los ómnibus. En él se aborda el desarrollo de una herramienta de simulación que permita el análisis del comportamiento de los ómnibus y pasajeros, utilizando técnicas de modelado y programación orientadas a objetos y simulación orientada a eventos.

El alto costo de la búsqueda de soluciones exactas por los métodos conocidos a algunos problemas complejos de optimización, especialmente optimización combinatoria, ha llevado a la búsqueda de métodos aproximados capaces de proveer buenos resultados en tiempos computacionales aceptables.
Dentro de este conjunto, nuestro trabajo se concentra en tres clases de problemas: el TSP (Travelling Salesman Problem), TSPTW (TSP con restricciones de tiempo) y TSP-mTW (TSP con múltiples restricciones de tiempo). Daremos una definición formal de cada uno de ellos y plantearemos su resolución mediante la metodología de Ant Systems.
El desarrollo de Ant Systems, así como otras heurísticas está basado en la observación de fenómenos naturales. En particular Ant Systems estudia el comportamiento de colonias de hormigas trabajando de forma cooperativa.
Los resultados obtenidos en las pruebas realizadas a las implementaciones muestran la efectividad del método en este tipo de problemas. Como aspecto novedoso de este taller debemos tener en cuenta que la metodología que aquí tratamos no ha sido aplicada hasta el momento a las clases de problemas TSPTW y TSP-mTW.

En el presente trabajo, abordamos el formalismo denominado Ant System el que se inspira en el comportamiento real de las hormigas y como éstas, siendo individuos con un comportamento elemental, se comunican y trabajan en conjunto para lograr un fin común. Utilizamos esta herramienta para resolver problemas de optimización combinatoria, en particular los bien conocidos problemas TSP y VRP, no habiéndose enocntrado ninguna aplicación para éste último en la literatura investigada. Se diseñan e implementan algoritmos basados en el Ant System para resolver dichos problemas, además de una interface gráfica para editar, crear y modificar los grafos que representan instancias del TSP y VRP. Finalmente, los buenos resultados obtenidos para el VRP demuestran que el Ant System es un formalismo a tener en cuenta a la hora de abordar la resolución de problemas de ruteo de vehículos.

Año a año la Facultad de Ingeniería, así como otras facultades, liceos o institutos, debe enfrentarse con el problema de asignar los salones y horarios para cada curso que se dictará en los meses siguientes. Este problema se resuelve actualmente en forma manual y lleva varias horas de trabajo. Sería útil entonces encontrar una manera de automatizar esta tarea para facilitarla y ahorrar así tiempo y esfuerzo. El problema a tratar es un problema de optimización combinatoria complejo, y se consideran varias alternativas para su resolución, en particular las metodologías heurísticas desarrolladas a partir de la observación de fenómenos de la naturaleza. Dentro de esta familia de algoritmos, se estudia la aplicación al problema de una heurística basada en el comportamiento de colonias de agentes cooperativos, conocida como 'Ant Systems'. Este método no ha sido aplicado aún a problemas de asignación en instituciones de enseñanza.

Informe

Informe

De la observación de los fenómenos físicos, biológicos y sociales de la naturaleza, el hombre ha sido capaz de extraer ciertas características de esos fenómenos que pueden ser aplicadas en la resolución de Problemas de Optimización  Combinatoria.
En analogía al comportamiento de de las colonias de hormigas surgió la definición de un nuevo método de resolución para problemas de Optimización, llamado Ant Systems. Originalmente fue propuesto para la resolución del bien conocido Problema del Viajante de Comercio (TSP), pero también ha sido aplicado con suceso a Problemas de Asignación Cuadrática (QAP), de Despacho de Tareas (Job-shop Scheduling), de Ruteo de Vehículos (VRP), etc.
En el presente trabajo presentamos el problema de asignar los alumnos a los proyectos de Taller V de la carrera de Ingeniería en Computación y su resolución utilizando Ant Systems.

Palabras clave: Optimización Combinatoria, Colonia de Agentes Cooperativos, Optimización con Colonias de Hormigas, Meta-Heurísticas, Ant Systems, Problemas de Asignación.

El presente trabajo se realiza como proyecto de grado (Taller V 1992) de la carrera Ingeniero en Computación, en el Departamento de Investigación Operativa, en el área de Simulación de Sistemas.
El objetivo cumplido fue el de diseñar, desarrollar e implementar un gestor de simulaciones a eventos discretos, llamado C++Sim, con el fin de facilitar el desarrollo de aplicaciones de interés, en este caso problemas de tránsito. C++Sim es una biblioteca que permite realizar las simulaciones mediante el mecanismo de simulación orientada a procesos, inspirándose en el lenguaje de simulación por excelencia Simula.
C++Sim tiene incorporado además, una serie de clases para: manejo de listas, generación de números pseudoaleatorios, muestreo de distintas distribuciones de probabilidad, generación de procesos según cierta distribución, recolección de datos y tratamiento estadístico de los mismos.
La implementación del gestor, como su nombre lo indica, recae en el lenguaje orientado a objetos C++, comprobándose la modularidad que brinda la programación orientada a objetos, facilitando la tarea de modelado, desarrollo y mantenimiento de los sistemas simulados.
Con el fin de verificar las funcionalidades de C++Sim, se desarrolló la aplicación: Un Cruce con Semáforos en versión animada, pudiéndose comprobar la facilidad de integración de esta biblioteca con las de gráficos XView y XLib.

El presente trabajo se enmarca dentro de los proyectos que forman parte de la tesis de grado de la carrera Ingeniería en Computación.
En él se logra exitosamente realizar una Reingeniería de procesos al Sistema de Información del Instituto de Computación, obteniendo importantes mejoras que facilitan y apoyan la toma de decisiones y el manejo de la información a los directores y docentes encargados de la administración y planificación.
En el trabajo se encontrará una breve introducción de la Reingeniería y la evolución del proyecto haciendo énfasis en los procesos rediseñados, así como en el desarrollo del sistema informático implementado.
Se destaca además la forma atípica de la reingeniería y las soluciones que se encontraron para resolver los problemas a los cuales nos enfrentamos.

Finalmente se incluye el seguimiento del proyecto, con la planificación inicial y el desarrollo en detalle del mismo, especificando la cantidad de horas empleadas y demostrando en las conclusiones que a partir de la aplicación de la reingeniería se consiguen mejoras sustanciales en el Sistema de Información del InCo.

Se trata de paralelizar un algoritmo secuencial ya implementado, que resuelve la planificación de producción de energía eléctrica en el mediano y largo plazo, optimizando los costos de producción de energía teniendo en cuenta la existencia de incertidumbre en los datos y satisfaciendo la demanda de energía en el sistema respetando las restricciones operativas y las impuestas por la red de transmisión.

Este informe presenta de la forma más detallada posible el proceso de investigación y desarrollo que tuvo lugar durante el transcurso del presente Taller V. Dicho proyecto, está dirigido a la implementación de soluciones para los siguientes problemas: Problemas de inventarios (dónde se pretende minimizar los costos de mantener un stock de uno o varios artículos, teniendo en cuenta las relaciones que existen entre ellos), Problemas de inventarios con remanufacturación y disposición final (se pretende minimizar los costos de mantener un artículo en stock, pero además interesa obtener un beneficio ecológico ya que como por ejemplo desechar todo cada vez y producir nuevamente puede ser perjudicial para el medio ambiente, y a veces también imposible tecnológicamente), Problemas de mantenimiento de equipos (también llamados problemas de reemplazo, en ellos se pretende obtener un calendario que indique cuando reemplazar un equipo existente por un equipo nuevo, de forma de minimizar los costos totales durante un período de tiempo) y  Pronósticos (dónde se pretende conocer el valor futuro de una cantidad, la cual varía en el tiempo con una cierta tendencia). Para cada uno de estos problemas se implementaron soluciones que van desde métodos clásicos de optimización pasando por programación dinámica y hasta recorridas sobre grafos. Las soluciones planteadas, son políticas óptimas o métodos heurísticos. Los problemas de inventarios se solucionaron mediante métodos de optimización  iterativos como el método de relajación de Lagrange [4.2] o de programación dinámica simplificados como Wagner-Whitin [4.3] y diversos heurísticos (por ejemplo el método de Silver-Meal [10]), y para el caso de varios artículos se presentan distintas soluciones, según si la relación entre los mismos es independiente (Limitación de Espacio de Almacenamiento) o dependiente (Plan de Requerimiento de Materiales, MRP [3]). Los problemas de Inventarios con Remanufacturación y Disposición final, se resolvieron mediante el modelo planteado por Knut Richter [5][6][7][8], que es una adaptación del modelo clásico de EOQ [2.1][1.1] para este problema. Las soluciones propuestas para resolver los problemas de mantenimiento de equipos se basaron en programación dinámica y recorridas sobre grafos. Los problemas de pronósticos se resolvieron mediante el método de Series de Tiempo con Suavizamiento Exponencial [1.9]. Algunos métodos eran presentados de forma particular en la literatura estudiada, por lo que se realizó una extensión de los mismos para brindar una mayor funcionalidad. El resultado del proyecto es un conjunto de funcionalidades que resuelven los problemas antes mencionados. Tanto las soluciones implementadas, como los problemas resueltos, fueron seleccionados entre una gran cantidad de opciones, por considerarlos clásicos o de fácil aplicación práctica, y que este es un taller introductorio con respecto a estos temas.Todas estas funcionalidades pueden ser utilizadas tanto de forma local o de forma remota, ya sea en una LAN (red de área local) o a través de  Internet.

KeyWords:   Control de Inventarios, Remanufacturación, Disposición final, MRP, Mantenimiento, Pronósticos.
Area: Investigación de Operaciones, Optimización.

Centrado en un nuevo problema de optimización combinatoria complejo dado a conocer recientemente, este trabajo resulta ser el primero en su clase en estudiar el Diseño y Optimización de Redes Diámetro-Confiables. En el transcurso del mismo se ha analizado detalladamente un variado número de metaheurísticas, determinando las dos más adecuadas para el problema en cuestión. Constituyendo este trabajo el primero en su clase, resultan  originales todas las ideas en las que se basan los algoritmos desarrollados, sin considerar las básicas y generales sugeridas por cada metaheurística. El resultado final constituye la presentación de los dos primeros algoritmos que diseñan y optimizan redes según la Diámetro-Confiabilidad. Los mismos fueron desarrollados sobre la base de los principios promulgados por Algoritmos Genéticos y GRASP. Se presenta asimismo un algoritmo polinomial para simplificar, bajo ciertas condiciones, una red a otra equivalente según la Diámetro-Confiabilidad.
Los algoritmos en su totalidad exhiben en la práctica un muy buen desempeño para los más de 500 juegos de pruebas realizados.

Informe