Teoría de Grafos Aplicada al Análisis de Redes S4PR y Subclases: El Problema de Cálculo de los Cerrojos Mínimos

Abstract

La presente memoria utiliza la teoría de grafos en el análisis de redes s4pr. La necesidad de disponer de algoritmos eficientes para calcular los cerrojos mínimos u otros conjuntos de cerrojos para esta clase de redes es el motivo que ha conducido esta investigación. Para alcanzar el objetivo trazado se ha desarrollado como punto de partida las propiedades estructurales que poseen las redes s4pr, esto se ha hecho debido a que en todos los trabajos anteriores se utilizaban las mismas propiedades que poseen las redes de petri generales y no se tomaba ventaja de la estructura que este tipo de redes posee. De igual forma se han caracterizado los cerrojos mínimos en función del conjunto de recursos que estos poseen. A partir de los resultados antes mencionados se ha desarrollado una herramienta denominada relación de poda entre los cerrojos mínimos de un recurso la cual nos permite determinar el conjunto de lugares que un cerrojo mínimo de un recurso puede podar a otro cerrojo mínimo de un recurso. Esta herramienta nos permite obtener los cerrojos mínimos del conjunto de cerrojos que la red posee. Para representar esta relación se utiliza un grafo al cual se le ha llamado grafo de poda y tres funciones de etiquetado asociadas al mismo. Este grafo nos permite realizar el cálculo de cerrojos para un conjunto de recursos dado o el cálculo de cerrojos mínimos de una manera más eficiente al trabajar calculando y manipulando los subgrafos fuertemente conexos máximos del grafo. Por lo tanto, la memoria requerida es muy pequeña y del orden del tamaño del grafo de poda. Finalmente, se presenta la especialización de los algoritmos de cálculo de cerrojos mínimos con más de un recurso para las redes l-s3pr, s3pr y soar2 cuyo objetivo es obtener algoritmos que sean más eficientes que el desarrollado para las redes s4pr. Este trabajo contribuye en: 1. Nuevas propiedades estructurales para las redes s4pr. 2. Cotas inferior y superior de los cerrojos mínimos para las redes s4pr, l-s3pr, s3pr y soar2. 3. Caracterización de los cerrojos mínimos por el conjunto de recursos que contienen. 4. Nuevas herramientas: relación de poda y grafo de poda, que nos permiten obtener los cerrojos mínimos del conjunto de cerrojos que una red s4pr posee. 5. Algoritmo para calcular los cerrojos de una red s4pr que contengan determinados recursos. 6. Algoritmo para calcular los cerrojos mínimos para redes s4pr, l-s3pr, s3pr y soar2.