Real-time management of resource allocation systems. A discrete event systems approach. (Q1769928): Difference between revisions

This volume presents a methodology for resource allocation problems based on the control of discrete event systems. A resource allocation system (RAS) is defined by a set of processes which can be activated provided some resources are available. (Notice that the given definition of the size of such a system cannot be understood). The activation procedure involves a sequential logic. More specific situations, which are developed later in the chapters, are considered. The taxonomy is related to the structure of a graph representing the sequential logic (linear RAS (total order), disjunctive RAS (acyclic digraph), coordinating RAS (fork/join acyclic digraph), complex RAS (general case)), or to the resource allocation function (single-unit RAS (one unit of a unique type of resource, i.e. a binary structure), single-type RAS (several units are available), conjunctive RAS (general case)). The main danger is deadlock. To handle this, rather than imposing an order on the resource allocation function, which is too crude and sacrifices many potentially useful policies, or an ad hoc procedure specific to a detected failure, which may not be implementable in all cases, the authors propose a feedback policy based on state information utilization. This leads to nonblocking behaviour (notion of robustness). Flexibility is guaranteed then by maximal permissiveness. From the many remaining policies, an optimal one is associated to a chosen performance function (notion of optimality). Since very often the optimal solution is NP-hard, a third notion of computational realizability (scalability) is crucial in this book. Chapter two examines disjunctive-conjunctive RAS with issues related to computational complexity of optimal solutions. In chapter three, the latter issues are relaxed for single-unit RAS. Chapter four focuses on linear single-unit RAS with more specific and concrete results, which can be connected to other publications. Chapter five models RAS with Petri nets instead of finite state automata as before. In chapter six, implementation of optimal policies with continuous-time Markov decision processes and neurodynamic programming is examined. Here, the disjunctive-conjunctive case is considered. The interest of this book lies in applying the discrete-event systems perspective to resource allocation problems and in proposing a unifying framework for handling such problems (robustness, optimality, computational complexity). For implementation, this framework is not self-sufficient, and the author needs new methods so that this area of research remains quite open.