Foundations and Trends® in Systems and Control > Vol 4 > Issue 1-2

Logical Control of Complex Resource Allocation Systems

Spyros Reveliotis, Georgia Institute of Technology, USA, spyros.reveliotis@isye.gatech.edu
 
Suggested Citation
Spyros Reveliotis (2017), "Logical Control of Complex Resource Allocation Systems", Foundations and TrendsĀ® in Systems and Control: Vol. 4: No. 1-2, pp 1-223. http://dx.doi.org/10.1561/2600000010

Published: 05 Apr 2017
© 2017 S. Reveliotis
 
Subjects
Control of Hybrid and Discrete Event Systems,  Systems Theory,  Control Applications,  Planning and Control:Multi-Robot Systems,  Program Synthesis,  Program Verification
 
Keywords
Resource AllocationDeadlock AvoidanceSupervisory Control
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Sequential Resource Allocation Systems and their Supervisory Control Problem of Deadlock Avoidance
3. RAS Classes Admitting Maximally Permissive Deadlock Avoidance of Polynomial Complexity
4. Efficient Implementations of the Maximally Permissive DAP as a Classifier
5. RAS Logical Analysis and Control through Petri Net Theory
6. Suboptimal Deadlock Avoidance for the Considered RAS
7. Some Concluding Remarks
Appendices
References

Abstract

The problem addressed in this document concerns the coordinated allocation of a finite set of reusable resources to a set of concurrently running processes. These processes execute in a staged manner, and each stage requires a different subset of the system resources for its support. Furthermore, processes will hold upon the resources currently allocated to them until they will secure the necessary resources for their next processing stage. Such resource allocation dynamics currently arise in the context of many flexibly automated operations: from the workflow that takes place in various production shop floors and certain internet-supported platforms that seek to automate various service operations; to the traffic coordination in guidepath-based transport systems like industrial monorail and urban railway systems; to the resource allocation that takes place in the context of the contemporary multi-core computer architectures. From a theoretical standpoint, the resource allocation problems that are abstracted from the aforementioned applications, correspond to the problem of scheduling a stochastic network with blocking and deadlocking effects. This is an area of the modern scheduling theory with very limited results. To a large extent, this lack of results is due to the intricacies that arise from the blocking, and especially the deadlocking effects that take place in these networks, and prevents a tractable analysis of these problems through the classical modeling frameworks. Hence, the departing thesis of the work that is presented in this document, is the decomposition of the aforementioned scheduling problems to (i) a supervisory control problem that will seek to prevent the deadlock formation in the underlying resource allocation dynamics, and (ii) a scheduling problem that will be formulated on the admissible subspace to be defined by the adopted supervisory control policy. Each of these two subproblems can be further structured and addressed using some formal modeling frameworks borrowed, respectively, from the qualitative and the quantitative theory of Discrete Event Systems. At the same time, the above two subproblems possess considerable special structure that can be leveraged towards their effective and efficient solution. The presented material provides a comprehensive tutorial exposition of the current achievements of the corresponding research community with respect to the first of the two subproblems mentioned above. As it will be revealed by this exposition, the corresponding results are pretty rich in their theoretical developments and practically potent. At the same time, it is expected and hoped that the resulting awareness regarding the aforementioned results will also set the stage for undertaking a more orchestrated effort on the second of the two subproblems mentioned above.

DOI:10.1561/2600000010
ISBN: 978-1-68083-250-1
236 pp. $99.00
Buy book
 
ISBN: 978-1-68083-251-8
236 pp. $260.00
Buy E-book
Table of contents:
1. Introduction
2. Sequential Resource Allocation Systems and their Supervisory Control Problem of Deadlock Avoidance
3. RAS Classes Admitting Maximally Permissive Deadlock Avoidance of Polynomial Complexity
4. Efficient Implementations of the Maximally Permissive DAP as a Classifier
5. RAS Logical Analysis and Control through Petri Net Theory
6. Suboptimal Deadlock Avoidance for the Considered RAS
7. Some Concluding Remarks
Appendices
References

Logical Control of Complex Resource Allocation Systems

Scheduling in a stochastic network is an issue in many applications such as the workflow on production shop floors, automated service operations on internet platforms, traffic coordination in guidepath-based transport systems, and resource allocation in multi-core computer architectures. It is an area of the modern scheduling theory with very limited results. To a large extent, the lack of results is due to the intricacies that arise from the blocking and deadlocking effects that take place in these networks which prevent analysis using classical modeling frameworks. These type of scheduling problems can be resolved by breaking them into a supervisory control problem that seeks to prevent the deadlock formation in the underlying resource allocation dynamics, and a scheduling problem formulated on the admissible subspace to be defined by the adopted supervisory control policy.

Logical Control of Complex Resource Allocation Systems provides a comprehensive tutorial on solutions to the supervisory control problem. The reader is shown results that are theoretically rigorous yet offer rich practical applications. These resource allocation techniques have major implications for many modern-day and future applications. They also point the way forward for the necessary further research to successfully solve the scheduling problems in such systems.

Logical Control of Complex Resource Allocation Systems is a comprehensive introduction for students, researchers, and practitioners into a significant development at the core of many control systems.

 
SYS-010