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.     

Analysing the operation of the basic pass transistor structure

Pass transistor logic has become important for the design of low‐power high‐performance digital circuits due to the smaller node capacitances and reduced transistors count it offers. However, the acceptance and application of this logic depends on the availability of supporting automation tools, e.g. timing simulators, that can accurately analyse the performance of large circuits at a speed, significantly faster than that of SPICE based tools. In this paper, a simple and robust modelling technique for the basic pass transistor structure is presented, which offers the possibility of fast timing analysis for circuits that employ pass transistors as controlled switches. The proposed methodology takes advantage of the physical mechanisms in the pass transistor operation. The obtained accuracy compared to SPICE simulation results is sufficient for a wide range of input and circuit parameters. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

A simple cost-effective sputtering-based method for micropatterning and materials microstructuring

Patterning of semiconductors results in the fabrication of micro- and nano-structures, which are desired in modern technologies. Such a patterning is usually realized with the help of e-beam-, high-energy ion-, X-ray- or laser-assisted techniques, which demand expensive equipments. In this work we present a simple cost-effective method realized via a radio-frequency driven magnetron-sputtering head in high vacuum. The target is a silicon wafer masked with metallic grids. If the grid is magnetic, e.g., nickel, it is attracted by the magnetic forces of the magnetron, otherwise, magnetic clamps are used. Soft sputtering conditions, i.e., 30-100 Watts are used and the result is a well-ordered micropatterning of the surface with nicely formed pits the size of which is entirely determined by the grid size and the depth by the sputtering power and time. The pits are monitored with the help of Optical and Atomic Force Microscopy. If the masked micropatterned silicon wafer is then used as a substrate, the pits may be partially filled by a material. As a first example we present square-like Co microstructures. The magnetic signal of these Co microstructures is recorded with the help of a computer-driven magneto-optic Kerr effect home-made magnetometer. This patterned material may be used in magnetic recording technology. More examples include the formation of Cu-microcolumns and Pt film microframeworks. For the latter ones, an etching process is applied to prepare porous silicon networks with photoluminescence, which may be used in optoelectronics.     

Structure and magnetic properties of hcp and fcc nanocrystalline thin Ni films and nanoparticles produced by radio frequency magnetron sputtering

We report on the growth of thin Ni films by radio frequency magnetron sputtering in Ar-plasma. The growth temperature was about 350 K and the films were deposited on various substrates such as glass, silicon, sapphire and alumina. The thickness of the thinnest films was estimated by the appearance of Kiessig fringes up to about 2theta = 8 degrees in the small-angle X-ray diffraction pattern, as expected for high-quality atomically-flat thin films. With the help of this, a quartz balance system was calibrated and used for measuring the thickness of thicker samples with an accuracy of better than 5%. Structural characterization via X-ray diffraction and high resolution transmission electron microscopy revealed an Ar-gas pressure window, where single phase hcp Ni films may be grown. The magnetic response of the Ni films was checked at room temperature via a newly established and fully automatic polar magneto-optic Kerr effect magnetometer. The hcp films show no magnetic response. Interestingly, the magnetic saturation field of fcc films deposited at low Ar pressure is comparable to the one of bulk Ni, while the one of fcc films deposited at high Ar pressures is decreased, revealing the presence of residual strain in the films. Finally, it is shown that it is possible to form films which contain magnetic Ni fcc nanoparticles in a non-magnetic hcp matrix, i.e., a system interesting for technological applications demanding a single Ni target for its production.