Logical Control of Complex Resource Allocation Systems

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.