An integrated methodology to state and solve optimization problems with Petri nets as disjunctive constraints for decision-making support stars

Resumen

El análisis, diseño y control de sistemas de eventos discretos constituye una de las piedras angulares de nuestra civilización, donde el uso de una tecnología que hace un uso intensivo de los computadores afecta a muchos ámbitos de la actividad humana. Un proceso de toma de decisiones apropiado puede permitir a estos sistemas alcanzar sus objetivos, definidos normalmente en términos de evaluación de prestaciones. Un enfoque efectivo para la toma de decisiones es el planteamiento formal de un problema de optimización o de satisfacción de restricciones. La obtención de una solución exacta para un problema real de optimización combinatoria suele requerir enormes recursos computacionales como espacio y tiempo. Para superar estas limitaciones se ha investigado ampliamente en métodos metaheurísticos probabilísticos, que pueden proporcionar soluciones cuasi-óptimas en un tiempo razonable. Partiendo de estas consideraciones, en esta tesis se ha abordado la toma de decisiones sobre sistemas de eventos discretos modelados con el formalismo de las redes de Petri. La principal contribución de esta tesis se describe a continuación. La investigación desarrollada en el marco de esta tesis contribuye al conocimiento en el planteamiento formal de los problemas de optimización en los que el modelo del sistema constituye una restricción disyuntiva, debido a la existencia de alternativas estructurales. El número de estas alternativas puede ser elevado como consecuencia de consideraciones combinatorias. La investigación ha permitido encontrar diferentes representaciones para un modelo disyuntivo de un sistema, como las redes de Petri compuestas, las RdP alternativas, las RdP de agregación de alternativas y las RdP coloreadas disyuntivas. La existencia de diversas posibles representaciones para el modelo del sistema permite escoger la más apropiada para desarrollar un algoritmo de optimización eficiente para un problema determiado. En particular esta eficiencia puede alcanzarse por los siguientes motivos: a) Reducción de los requerimientos de los algoritmos de optimización por medio de la compactación de la información que describe el modelo del sistema (matrices de incidencia). Se elimina la información redundante en un modelo con alternativas estructurales. b) Fusión de los espacios de soluciones de los diferentes modelos alternativos de un sistema de eventos discretos para realizar una única búsqueda en vez de n, una por cada alternativa. Esta única optimización puede ser más eficiente puesto que los recursos computacionales no se invierten en las regiones menos prometedoras del espacio de soluciones. Algunos de los resultados teóricos de esta tesis se han aplicado a la resolución de un ejemplo por medio de un proceso de búsqueda basado en un algoritmo genético. Los resultados obtenidos han sido comparados con una metodología clásica de descomposición del problema en otros más simples y, en la aplicación mencionada, el primero mejora al segundo, reduciendo el tiempo computacional en un porcentaje significativo. El análisis sistemático de un problema de decisión y su formalización en un problema de optmización basado en una red de Petri indefinida, el modelo de un sistema con grados de libertad para la toma de decisiones, ha conducido a la investigación presentada en esta tesis a un campo prometedor de los sistemas de toma de decisiones aplicados a situaciones en las que existen alternativas estructurales y restricciones en el uso de recursos computacionales.