Los sistemas distribuidos, de transporte, logísticos, redes de comunicación, entre otros, son Sistemas de Eventos Discretos (SED), y en general las disciplinas teóricas que soportan su estudio incluyen la teoría de sistemas, la investigación de operaciones, la ciencia de la computación y la ingeniería industrial (ver [2,5,11-14,16]).

Usualmente, un SED es referido como un conjunto discreto de eventos, junto con un mecanismo que especifica las ordenes posibles en que estos pueden ocurrir. Así, la no linealidad inherente de los SED clasifica a esta clase de sistemas como complejos (ver [1]). Ellos consisten de un conjunto de procesos independientes asincrónicos (componentes) que operan concurrentemente e interactúan sobre un medio ambiente compartido (ver [9]). La planificación inapropiada de la ocurrencia de eventos puede conducir a estos sistemas a estancamientos (bloqueo del sistema), a sobreflujos de capacidad, etc, degradando la ejecución deseable para el logro de objetivos. Así, uno siempre quiere que los SED sean funcionalmente correctos en términos de propiedades deseables. En consecuencia, el análisis formal es un aspecto primordial para la verificación de dichas propiedades. Más aun, el análisis automático (enfoque algorítmico) nos permite construir herramientas de software para el estudio adecuado de la dinámica del sistema.

Actualmente, (ver [3,4,6,8,17]) la generación de una planificación en los SED esta direccionada desde:

La comparación de metodologías para la toma de decisiones;

Cualquiera de estos enfoques es potencialmente útil para ordenar el flujo de eventos resultantes. Nosotros presentamos en este artículo un algoritmo para la construcción de una planificación basada en las nociones propias de k-interacción y consenso, entre las componentes asincrónicas de un SED. Este incluye:

Consenso en cada paso: expresado desde criterios de ordenamientos racionales para la toma de decisiones;

Formalmente, dado un SED con comportamiento dinámico , y una planificación capturada por un autómata , es el SED sujeto a la planificación, donde es la composición paralela de las componentes asincrónicas de , condicionadas por bajo consenso.

La organización de este artículo comienza con una sección de Preliminares, que incluye las definiciones básicas de la teoría de lenguajes y autómatas, las cuales constituyen fundamentalmente el piso de nuestro modelo; a saber, la composición paralela. Posteriormente, presentamos una metodología de modelación en el contexto de manufactura, que finaliza en una expresión genuina que llamaremos k-interacción. Ella junto con el concepto de consenso, apertura la base teórica que permitirá la generación de un algoritmo para la planificación de un SED. Luego, presentaremos una aplicación en sistemas de producción, para finalmente establecer algunas conclusiones y trabajos futuros.

Sea un conjunto cualquiera y consideremos el conjunto de todas las combinaciones finitas de elementos de , es decir, el conjunto conformado por n-uplas , con , para todo . El entero n será llamado la longitud de s y es denotado por .

Convenimos reescribir a s como , si , al tomar a α en lugar de la 1- upla (α). Sobre este conjunto definimos una operación binaria como sigue: si , con , para todo j>0; es otro elemento de , entonces el producto es también un elemento de . Esta operación binaria, nombrada concatenación le da a estructura de monoide con unidad ; la 0-upla . Cualquier subconjunto de es llamado un lenguaje sobre ; en consecuencia, la unión, intersección, diferencia y complemento de lenguajes son lenguajes sobre . Más aún, si y son lenguajes sobre un alfabeto entonces

son lenguajes sobre . Sea será llamado un segmento de s si , para algunos . Si , entonces t será llamado un prefijo de s. Por lo tanto, es el conjunto de todos los prefijos de todas las palabras en . Claramente, por definición, . Cuando entonces será llamado prefijo-cerrado o simplemente cerrado (ver [7,10,15]).

Otro tipo de operación que se realiza con frecuencia entre lenguajes es la proyección natural, o simplemente la proyección. Formalmente, sean ; alfabetos y pongamos . Las proyecciones naturales, ; son dadas por

para cualquier y

Sea Σ un alfabeto. Un Generador Finito Determinístico (GFD) G sobre Σ (Σ-generador finito), es un séxtuple (Q,Σ,δ,E,i,T), donde Q es un conjunto finito de estados, i y T⊆Q llamados respectivamente estado inicial y conjunto de estados finales, δ es un subconjunto de Q×Σ×Q de eventos y E es un subconjunto de Q×Σ de eventos activos (o habilitados) sobre los elementos de Q (ver [7]). Un evento (q,σ,p) será denotado . Así, obtenemos un grafo dirigido ponderado: los estados son los vértices y los eventos determinan los arcos, con marca en Σ. El conjunto de todas las trazas es denotado por , y será llamado lenguaje generado por . Una traza en , con , será llamada una tarea. El conjunto de las etiquetas de tareas en forman un lenguaje de llamado el comportamiento de ; es decir,

Un lenguaje de es llamado regular si existe un Σ-generador finito tal que . Ahora dado un Σ-generador finito un estado q∈Q será llamado accesible si existe una traza . Si todos los estados de son accesibles, entonces diremos que es accesible. Se llama parte accesible de al Σ-generador finito , donde Qa es el conjunto de estados accesibles de , , , Note que . Por otro lado, δ determina la función parcial . Algebraicamente podemos extender δ a una función parcial satisfaciendo las siguientes condiciones

Luego, así definida, es efectivamente una extensión de . Por lo tanto, en lo que sigue, no se hará distinción entre y . Sean ; n Σ-generadores finitos determinístico. Se llama Composición Paralela (o síncrona) de los ; al GFD accesible donde con , , y , si para , e indefinida en otro caso, y ; . Se puede chequear sin dificultad que si los , son lenguajes regulares de los sobre , tales que , , entonces se satisfice

Un sistema de manufactura es un par de conjuntos: conjunto de actividades y conjunto de recursos; que interactúan para obtener un producto. Este incluye un plan de proceso de producción (programa) que especifica las actividades y los tipos de recursos, así como también las relaciones de precedencia entre actividades. Sea 𝒢 un sistema de manufactura. La metodología incluida en este artículo para llevar a cabo la modelación será establecida mediante la composición paralela, organizada desde las interpretaciones de condiciones locales de estados (o estatus) y eventos tal como sigue:

Identificar las actividades y recursos necesarios para la producción de un artículo (o producto).

Figura 1 Fuente: Los autores.

Figura 2 Fuente: Los autores.

El modelo para el sistema de manufactura será establecido por , con , donde los > 𝑖 determinan las dinámicas de las n componentes constituyentes , ; del sistema. La construcción del modelo para el sistema de manufactura será establecido desde la interpretación, organización y conjugación de los generadores componentes. Para ello,

Definición 1. Sea el generador que representa un sistema global. Un evento será llamado una k-interacción en si cada vez que ocurre α éste produce cambios en k-componentes, , siempre que .

Convendremos en lo que sigue que una k-interacción en es simplemente un evento de orden k en y al conjunto constituido por las k-interacciones lo denotamos . Luego, es una partición de . Una k-interacción no es más que una expresión simbólica de la ocurrencia simultanea de eventos de ciertos generadores componentes. Estos eventos representan acciones distintas (con etiquetas distintas) pero podríamos darles una interpretación que nos permita conjugarlas mediante un mismo evento. Otro hecho aún más significativo para la construcción del modelo, ocurre cuando una actividad en el sistema requiere de uno o más recursos; donde el comienzo y la completación de dicha actividad tiene una relación directa con el comienzo y la finalización del uso de esos recursos. Igualmente, estos eventos tienen representaciones distintas en el sistema, pero la interpretación de este hecho por el mismo evento nos permitirá simplificar la construcción del modelo. Por lo tanto, diremos que las componentes ; del sistema de manufactura estarán determinadas bajo simetría de los eventos que representan los comienzos y finalizaciones de las actividades, así como de la adquisición y liberación de los recursos. Finalmente, en la composición paralela de los 𝒢 𝑖 , un evento común solo ocurre si ocurre simultáneamente en los 𝒢 𝑖 relacionados a través de dicho evento. Por lo tanto, los están sincronizados sobre los eventos comunes. Los eventos no comunes no están sujetos a esta restricción y pueden ocurrir siempre que sea posible. Por lo tanto .

Sea (sistema de manufactura) la composición síncrona de n componentes (subsistemas) . Sabemos que, para cualesquiera y ; existe un generador finito determinístico tal que y , . Sea una condición (expresada como un lenguaje) para y para cada i, con ; sea la proyección i-ésima de . La afectación que puede producir sobre puede ser proyectada a las dinámicas de las componentes. Más aún, existen condiciones no únicas que producen el efecto global impuesto por las condiciones locales. Por lo tanto, conocer (lenguaje global ante una condición) es conocer los ; es decir, conocer la afectación 𝒞 sobre el sistema 𝒢 es conocer las afectaciones sobre las componentes . Note que la condición no tiene sentido lógico, en relación al acoplamiento con , si ésta no está reflejada en la dinámica del sistema. En este sentido, para la construcción de la metodología por consenso podemos suponer que la planificación es un sublenguaje de .

Definición 2. Sean un sistema global y una condición sobre . Para cualesquiera y una k-interacción, sean ; los índices de las componentes de cambio por la ocurrencia de α en q. Diremos que α es obtenida por consenso si para todo se tiene que .

De acuerdo a la definición 2 establecemos el conjunto de todos eventos permitidos en q obtenidos por consenso, el cual denotaremos por . La construcción para la planificación en los sistemas de manufactura; establecida por el producto síncrono, está fundamentada en el consenso como sigue: Para cada estado del sistema de manufactura; , donde e es el estado inicial, consideramos el conjunto de todos los eventos habilitados en q; : para cada k-interacción , donde son los índices de las componentes de cambio por la ocurrencia en q, α deberá satisfacer: , para ser obtenida por consenso. Comenzamos el procedimiento desde el estado inicial i, y consideremos el subconjunto de eventos obtenidos por consenso en i; . La ocurrencia de un evento α en determinará un nuevo estado q, y por ende se genera un arco dirigido desde i al nuevo estado q etiquetado por el evento α; . Ahora, esto ocurrirá eventualmente para todo evento α en . Y en el estado actual q se repetirá el proceso antes mencionado con respecto a , generando de esta manera bajo consenso el árbol que determina el generador que reconoce la planificación desde un punto de vista constructivo. El procedimiento repetido sucesivamente generará un conjunto de estados bajo consenso y puede ser representado gráficamente. Finalmente, el proceso resultante será un reconocedor de la planificación y será denotado por . Formalmente,

Definición 3. Sea 𝒫(𝒢) como antes. El lenguaje generado por será llamado lenguaje de planificación y es dada por

;

El lenguaje de planificación marcado por es dado por .

Para facilitar la escritura, denotaremos a los lenguajes de planificación y planificación marcada por y respectivamente. El conjunto de todos los estados generados por consenso desde el estado inicial 𝑖 está dado por z, y el generador determinístico accesible es el reconocedor de . La selección de eventos comunes en la composición paralela, lo cual determina el acoplamiento entre las componentes, junto con la reducción en cuanto a la navegación de estados sometidas a las condiciones impuestas localmente permite lidiar eficientemente con la complejidad computacional resultante del modelo completo.

Para la construcción de mediante el algoritmo son necesarias las siguientes especificaciones (ver Fig. 3):

Los elementos del generador composición paralela : el estado inicial , el conjunto de estados finales , el conjunto de estados, el conjunto de eventos activos y la función de transición ;

Figura 3 Fuente: Los autores.

Proposición 1. Sea n el cardinal del conjunto . La planificación se puede llevar a cabo a la sumo en pasos.

Demostración. Supongamos que para ; se tiene que , tal que ; . Ahora, si , entonces el nivel del nodo que representa a está dado por

Si entonces . Esto implica que necesariamente , para algún i; . Sea , una función de nivel: para cada es el nivel del estado 𝑞 𝑗 definida como ; entonces, . Finalmente, .

Nosotros construimos al conjunto cuyos elementos son las k-interacciones obtenidas por consenso, , para obtener posteriormente, para cada una nueva bolsa . Este proceso continua considerando la nueva bolsa , obteniendo de esta manera el lenguaje de planificación , en algún sentido, por sucesiones de bolsas de la forma . Finalmente, es una realización de construida desde las afectaciones locales ; sobre las componentes . La justificación por la cual una condición sobre es dada, es por la necesidad de establecer una planificación sobre el sistema. Por ello estableceremos el acoplamiento con .

Teorema 1. Dado una condición sobre . Sea para cada la condición local para . Entonces, (más restrictivamente, ).

Demostración.

Análogamente, se puede probar que .

El resultado anterior; teorema 1 expresa que la planificación global sobre el sistema puede ser obtenida desde las planificaciones locales de las componentes , mostrando de esta manera el análisis global desde un punto de vista local.

La descomposición de una planificación en planificaciones locales, direcciona el análisis global desde un punto de vista local, lo cual permite bajo modularidad, unificación de criterios y juicios, flexibilidad, capacidad de gestión, viabilidad e implementación reducida; en consecuencia, un proceso ágil desde el punto de vista de automatización. En efecto, las descomposiciones son

expresadas por lenguajes cerrados y -cerrados respectivamente; de donde, se avanza modularmente a la reducción e implementación óptima. A propósito, enfatizamos que la planificación en SED siempre será una intención que posiblemente no pueda ser llevada a cabo completamente; por ejemplo, cuando estamos en teoría de control, debido a los eventos no controlables. Por otro lado, el modelo construido para la clase de sistemas de manufactura con componentes cooperantes (unidades de producción) puede ser considerado para el estudio de las k-interacciones cuando las unidades del sistema toman opciones cooperativas. Más precisamente, si el número de opciones cooperativas crece, entonces seguramente se generarán nuevas interacciones indeseables entre estas, produciendo problemas de funcionalidad en el sistema; pero nuevamente será establecido el acoplamiento entre las componentes por consenso (reconfiguración del sistema), con lo cual podríamos abordar propiedades de seguridad y no bloqueo desde un punto de vista local.

En relación a los trabajos futuros se puede considerar el desarrollo de programas de software para ejecutar cálculos referentes al algoritmo de planificación. También, comparar la planificación por consenso con diseños establecidos por Redes de Peri, representadas por bases de Gröbner, por razones de explosión de estados. Finalmente, se pueden extender nuestros argumentos teóricos de planificación, como una herramienta a un nivel de abstracción temporal para el análisis de SED.