Process completing sequences for resource allocation systems with synchronization
type: Item
instance of: scholarly article
title: Process completing sequences for resource allocation systems with synchronization
zbMATH Open document ID: 1248.93060
DOI: 10.1155/2012/424051
author: Song Foh Chew
author: Shengyong Wang
author: Mark A. Lawley
published in: Journal of Control Science and Engineering
publication date: 2012-09-06T00:00:00Z
review text: Summary: This paper considers the problem of establishing live resource allocation in workflows with synchronization stages. Establishing live resource allocation in this class of systems is challenging since deciding whether a given level of resource capacities is sufficient to complete a single process is NP-complete. In this paper, we develop two necessary conditions and one sufficient condition that provide quickly computable tests for the existence of process completing sequences. The necessary conditions are based on the sequence of completions of \(n\) subprocesses that merge together at a synchronization. Although the worst case complexity is \(O(2^n)\), we expect the number of subprocesses combined at any synchronization will be sufficiently small so that the total computation time remains manageable. The sufficient condition uses a reduction scheme that computes a sufficient capacity level of each resource type to complete and merge all \(n\) subprocesses. The worst case complexity is \(O(n \cdot m)\), where \(m\) is the number of synchronizations. Finally, the paper develops capacity bounds and polynomial methods for generating feasible resource allocation sequences for merging systems with single unit allocation. This method is based on single step look-ahead for deadly marked siphons and is \(O(2^n)\). Throughout the paper, we use a class of Petri nets called Generalized Augmented Marked Graphs to represent our resource allocation systems.
Mathematics Subject Classification ID: 93B40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 93C65
zbMATH DE Number: 6078155
zbMATH Keywords: live resource allocation
zbMATH Keywords: NP-complete
zbMATH Keywords: process completing sequences
zbMATH Keywords: capacity bounds
zbMATH Keywords: polynomial methods
zbMATH Keywords: Petri nets
zbMATH Keywords: Generalized Augmented Marked Graphs
Wikidata QID: Q58907963
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/424051
OpenAlex ID: W2125647292
cites work: Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems
cites work: Q3152841
cites work: Robustness analysis of non-ordinary Petri nets for flexible assembly systems
description: scientific article; zbMATH DE number 6078155