Polynomial-complexity deadlock avoidance policies for sequentialresource allocation systems

The development of efficient deadlock avoidance policies (DAPs) for sequential resource allocation systems (RASs) is a problem of increasing interest in the scientific community, largely because of its relevance to the design of large-scale flexibly automated manufacturing systems. Much of the work on this problem existing in the literature is focused on the so-called single-unit RAS model, which is the simplest model in the considered class of RASs. Furthermore, due to a well-established result stating that, even for single-unit RASs, the computation of the maximally permissive DAP is intractable (NP-hard), many researchers (including our group) have focused on obtaining good suboptimal policies which are computationally tractable (scalable) and provably correct. In the first part of the paper, it is shown, however, that for a large subset (in fact, a majority) of single-unit RASs, the optimal DAP can be obtained in real-time with a computational cost which is a polynomial function of the system size (i.e., the number of resource types and the distinct route stages of the processes running through the system). The implications of this result for the entire class of single-unit RASs are also explored. With a result on the design of optimal DAPs for single-unit RASs, the second part of the paper concentrates on the development of scalable and provably correct DAPs for the more general case of conjunctive RASs     

Efficient PAC Learning for Episodic Tasks with Acyclic State Spaces

This paper considers the problem of computing an optimal policy for a Markov decision process, under lack of complete a priori knowledge of (1) the branching probability distributions determining the evolution of the process state upon the execution of the different actions, and (2) the probability distributions characterizing the immediate rewards returned by the environment as a result of the execution of these actions at different states of the process. In addition, it is assumed that the underlying process evolves in a repetitive, episodic manner, with each episode starting from a well-defined initial state and evolving over an acyclic state space. A novel efficient algorithm for this problem is proposed, and its convergence properties and computational complexity are rigorously characterized in the formal framework of computational learning theory. Furthermore, in the process of deriving the aforementioned results, the presented work generalizes Bechhofer’s “indifference-zone” approach for the ranking & selection problem, that arises in statistical inference theory, so that it applies to populations with bounded general distributions.

Deadlock avoidance in sequential resource allocation systems withmultiple resource acquisitions and flexible routings

Considers the deadlock avoidance problem for the class of conjunctive/disjunctive (sequential) resource allocation systems (C/D-RAS), which allows for multiple resource acquisitions and flexible routings. First, a siphon-based characterization for the liveness of Petri nets (PNs) modeling C/D-RAS is developed, and subsequently, this characterization facilitates the development of a polynomial-complexity deadlock avoidance policy (DAP) that is appropriate for the considered RAS class. The resulting policy is characterized as C/D-RUN. The last part of the paper exploits the aforementioned siphon-based characterization of C/D-RAS liveness, in order to develop a sufficiency condition for C/D-RAS liveness that takes the convenient form of a mixed integer programming (MIP) formulation. The availability of this MIP formulation subsequently allows the “automatic” correctness verification of any tentative C/D-RAS DAP for which the controlled system behavior remains in the class of PNs modeling C/D-RAS, and the effective flexibility enhancement of the aforementioned C/D-RUN DAP implementations. Finally, we notice that, in addition to extending and complementing the current theory on deadlock-free sequential resource allocation to the most powerful class of C/D-RAS, the presented results also (i) nontrivially generalize important concepts and techniques of ordinary PN structural analysis to the broader class of nonordinary PNs, while (ii) from a practical standpoint, they can find direct application in the (work-) flow management of modern production, service and/or transportation environments     

On the Optimality of Randomized Deadlock Avoidance Policies

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.     

Design Guidelines for Deadlock-Handling Strategies in Flexible Manufacturing Systems

Deadlock-free operation of flexible manufacturing systems (FMSs) is an important goal of manufacturing systems control research. In this work, we develop the criteria that real-time FMS deadlock-handling strategies must satisfy. These criteria are based on a digraph representation of the FMS state space. Control policies for deadlock-free operation are characterized as partitioning cuts on this digraph. We call these structural control policies (SCPs) because, to avoid deadlock, they must guarantee certain structural properties of the subdigraph containing the empty state; namely, that it is strongly connected. A policy providing this guarantee is referred to as correct. Furthermore, an SCP must be configurable and scalable; that is, its correctness must not depend on configuration-specific system characteristics and it must remain computationally tractable as the FMS grows in size. Finally, an SCP must be efficient; that is, it must not overly constrain FMS operation. We formally develop and define these criteria, formulate guidelines for developing policies satisfying these criteria, and then provide an example SCP development using these guidelines. Finally, we present an SCP that guarantees deadlock-free buffer space allocation for FMSs with no route restrictions.     

Scalar quantisation of heavy-tailed signals

Efficient stochastic data processing presupposes proper modelling of the statistics of the data source. The authors address the issues that arise when the data to be processed exhibits statistical properties which depart significantly from those implied under the Gaussianity assumption. First, they present a study on the modelling of coefficient data obtained when applying the wavelet transform (WT) to images. They show that WT coefficients are heavy-tailed and can be modelled with alpha-stable distributions. Then, they introduce an alternative to the common mean-square error (MSE) quantiser for the efficient, scalar quantisation of heavy-tailed data by means of distortion minimisation. The proposed quantiser is based on a particular member of the family of alpha-stable distributions, namely the Cauchy distribution, and it employs a distortion measure based on the mean square root absolute value of the quantisation error. Results of the performance of this quantiser when applied to simulated as well as real data are also presented     

Designing parsimonious scheduling policies for complex resource allocation systems through concurrency theory

In a recent work we have proposed a theoretical framework for developing optimized scheduling policies for complex resource allocation systems (RAS). This framework relies heavily on the expression of the RAS dynamics in the modeling framework of the Generalized Stochastic Petri Nets (GSPNs), and the employment of this GSPN-based representation towards the establishment of a systematic trade-off between the representational economy of the target scheduling policies and their operational efficiency. In this paper, we enhance the representational economy of the target policies in the aforementioned framework by taking advantage of some notions of “(non-)conflict” in the transitional dynamics of the underlying RAS-modeling GSPNs. A series of numerical experiments demonstrate that the representational gains resulting from the presented methodology can be very substantial.