Resumen

Este artículo considera el problema de establecer la asignación de recursos en vivo en flujos de trabajo con etapas de sincronización. Establecer la asignación de recursos vivos en esta clase de sistemas es un reto, ya que decidir si un nivel dado de capacidades de recursos es suficiente para completar un único proceso es NP-completo. En este artículo, desarrollamos dos condiciones necesarias y una condición suficiente que proporcionan pruebas rápidamente computables para la existencia de secuencias de finalización de procesos. Las condiciones necesarias se basan en la secuencia de finalización de n subprocesos que se fusionan en una sincronización. Aunque la complejidad en el peor de los casos es O(2n), esperamos que el número de subprocesos combinados en cualquier sincronización sea lo suficientemente pequeño como para que el tiempo total de cálculo siga siendo manejable. La condición suficiente utiliza un esquema de reducción que calcula un nivel de capacidad suficiente de cada tipo de recurso para completar y combinar todos los n subprocesos. La complejidad en el peor de los casos es O(n-m), donde m es el número de sincronizaciones. Por último, el artículo desarrolla límites de capacidad y métodos polinómicos para generar secuencias factibles de asignación de recursos para fusionar sistemas con asignación de una sola unidad. Este método se basa en el look-ahead de un solo paso para sifones marcados mortalmente y es O(2n). A lo largo del artículo, utilizamos una clase de redes de Petri denominadas grafos marcados aumentados generalizados para representar nuestros sistemas de asignación de recursos.

• Materias:Automatización Control del proceso Sistemas no lineales Modelo lineal Regulación automática Diagnóstico de fallos
• Subjects:Automation Nonlinear systems Linear model Automatic regulation Fault diagnosis
• Palabras claves:asignación de recursos en vivo, complejidad en el peor de los casos, papel, n subprocesos, condiciones necesarias, condición suficiente, grafos marcados aumentados generalizados, secuencias factibles de asignación de recursos, sistemas de asignación de recursos, asignación de una sola unidad.
• Keywords:live resource allocation, worst case complexity, paper, n subprocesses, necessary conditions, sufficient condition, generalized augmented marked graphs, feasible resource allocation sequences, resource allocation systems, single unit allocation