Process Completing Sequences for Resource Allocation Systems with Synchronization
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Control Science and Engineering |
| Online Access: | http://dx.doi.org/10.1155/2012/424051 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550353100341248 |
|---|---|
| author | Song Foh Chew Shengyong Wang Mark A. Lawley |
| author_facet | Song Foh Chew Shengyong Wang Mark A. Lawley |
| author_sort | Song Foh Chew |
| collection | DOAJ |
| description | 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 𝑛 subprocesses that merge together at a synchronization. Although the worst case complexity is O(2𝑛), we expect the number of subprocesses combined at any synchronization will be sufficiently small so that 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 𝑛 subprocesses. The worst case complexity is O(𝑛⋅𝑚), where 𝑚 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𝑛). Throughout the paper, we use a class of Petri nets called Generalized Augmented Marked Graphs to represent our resource allocation systems. |
| format | Article |
| id | doaj-art-51dea5d8dab04961afb4235e9f039da8 |
| institution | Kabale University |
| issn | 1687-5249 1687-5257 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Control Science and Engineering |
| spelling | doaj-art-51dea5d8dab04961afb4235e9f039da82025-02-03T06:06:59ZengWileyJournal of Control Science and Engineering1687-52491687-52572012-01-01201210.1155/2012/424051424051Process Completing Sequences for Resource Allocation Systems with SynchronizationSong Foh Chew0Shengyong Wang1Mark A. Lawley2Department of Mathematics and Statistics, Southern Illinois University, Edwardsville, IL 62026, USADepartment of Mechanical Engineering, University of Akron, Akron, OH 44325, USASchool of Biomedical Engineering, Purdue University, West Lafayette, IN 47907, USAThis 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 𝑛 subprocesses that merge together at a synchronization. Although the worst case complexity is O(2𝑛), we expect the number of subprocesses combined at any synchronization will be sufficiently small so that 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 𝑛 subprocesses. The worst case complexity is O(𝑛⋅𝑚), where 𝑚 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𝑛). Throughout the paper, we use a class of Petri nets called Generalized Augmented Marked Graphs to represent our resource allocation systems.http://dx.doi.org/10.1155/2012/424051 |
| spellingShingle | Song Foh Chew Shengyong Wang Mark A. Lawley Process Completing Sequences for Resource Allocation Systems with Synchronization Journal of Control Science and Engineering |
| title | Process Completing Sequences for Resource Allocation Systems with Synchronization |
| title_full | Process Completing Sequences for Resource Allocation Systems with Synchronization |
| title_fullStr | Process Completing Sequences for Resource Allocation Systems with Synchronization |
| title_full_unstemmed | Process Completing Sequences for Resource Allocation Systems with Synchronization |
| title_short | Process Completing Sequences for Resource Allocation Systems with Synchronization |
| title_sort | process completing sequences for resource allocation systems with synchronization |
| url | http://dx.doi.org/10.1155/2012/424051 |
| work_keys_str_mv | AT songfohchew processcompletingsequencesforresourceallocationsystemswithsynchronization AT shengyongwang processcompletingsequencesforresourceallocationsystemswithsynchronization AT markalawley processcompletingsequencesforresourceallocationsystemswithsynchronization |