Generalized algebraic deadlock avoidance policies (DAPs) for sequential resource allocation systems (RASs) have recently been proposed as an interesting extension of the class of algebraic DAPs, that maintains the analytical representation and computational simplicity of the latter, while it guarantees completeness with respect to the maximally permissive DAP. The authors' original work that introduced these policies also provided a design methodology for them, but this methodology is limited by the fact that it necessitates the deployment of the entire state space of the considered RAS. Hence, this paper seeks the development of an alternative computational tool that can support the synthesis of correct generalized algebraic DAPs, while controlling the underlying computational complexity. More specifically, the presented correctness verification test possesses the convenient form of a mixed integer programming (MIP) formulation that employs a number of variables and constraints polynomially related to the size of the underlying RAS, and it can be readily solved through canned optimization software. Furthermore, since generalized algebraic DAPs do not admit a convenient representation in the Petri net modeling framework, an additional contribution of the presented results is that they effect the migration of the relevant past insights and developments with respect to simpler DAP classes, from the representational framework of Petri nets to that of the Deterministic Finite-State Automata.

Currently, one of the most actively researched approaches regarding the design of deadlock avoidance policies for sequential resource allocation systems is based on concepts and techniques provided by the, so called, theory of regions, that addresses the broader problem of synthesizing PN models with pre-specified behaviors. However, one limitation of the theory of regions and its aforementioned derivatives is that they cannot be applied when the target behavior has a non-convex representation in the underlying state space. In this paper, we show how this problem can be circumvented by appropriately generalizing the employed class of the candidate policies.

The problem addressed in this study is that of determining how to allocate the workstation processing and buffering capacity in a capacitated re-entrant line to the job instances competing for it, in order to maximize its long-run/steady-state throughput, while maintaining the logical correctness of the underlying material flow, i.e., deadlock-free operations. An approximation scheme for the optimal policy that is based on neuro-dynamic programming theory is proposed, and its performance is assessed through a numerical experiment. The derived results indicate that the proposed method holds considerable promise for providing a viable, computationally efficient approach to the problem and highlight directions for further investigation. Note to Practitioners-Sequencing and scheduling problems arising in the context of contemporary manufacturing environments are known to be extremely hard. For this reason, in most practical situations, these problems have been resolved through the application of a number of heuristics-i.e., "rules of thumb" that are expected to provide reasonable performance. Things are complicated even further in the automated versions of these environments, since the applied sequencing and scheduling logic must guarantee, in addition to good performance, logically correct and smooth operation. Both the logical and the performance-oriented control problem of flexibly automated production systems can be-and have been-addressed through formal systems theory. However, a challenging remaining problem is the approximation of the derived optimal policies in a way that will maintain near optimality, and at the same time, it will be computationally tractable in the context of the "real-world" applications. Our past work has addressed this approximation problem primarily with respect to the optimal logical control policy. The work presented in this paper undertakes the complementary problem of approximating the optimal scheduling policy. To this end, we employ some recently emerged results from a field known as neuro-dynamic programming (which is essentially a systematic approximation framework for dynamic programming). Our results indicate that the proposed approximation framework holds considerable promise toward developing a systematic analytical methodology for deriving near-optimal and logically correct scheduling policies for flexibly automated production systems. More specifically, it is shown that, when applied to some prototypical problems concerning the scheduling of re-entrant lines with finite buffering capacity at their workstations, the proposed approximation framework: 1) effectively integrates past results concerning the logical control of these environments and 2) the obtained performance is consistently superior to the performance provided by the typically used heuristics.

The basic definition of the reentrant line, which constitutes the typical abstraction for the formal modeling and analysis of the fabrication (fab) scheduling problem, considers only the job contest for the finite processing capacity of the system workstations, ignoring completely the effects and complications arising from additional operational issues like the finite buffering capacity of the system workstations/production units. Yet, as the semiconductor industry moves to more extensively automated operational modes, the explicit characterization and control of these additional operational features is of paramount importance for the robust and stable operation of the entire system. Moreover, the operational policies developed to control these logical aspects of the system behavior introduce additional constraints to the fab scheduling problem, that complicate it even further and, more importantly, invalidate prior characterizations of its optimal solutions. Motivated by these remarks, the work presented in the paper develops an analytical framework for the modeling, analysis, and control of capacitated, flexibly automated reentrant lines, based on the class of generalized stochastic Petri nets. The proposed framework allows the seamless integration of the logical/structural and the timed-based aspects of the system behavior, provides an analytical formulation for the underlying scheduling problem, and leads to an interesting qualitative characterization of the structure of the optimal scheduling policy. Hence, it provides the analytical basis for addressing the reentrant line scheduling problem in its contemporary, more complex operational context, and it constitutes the starting point for the development of new scheduling tools and policies for it.

The basic definition of the re-entrant line ignores completely the effects and complications arising from additional operational issues like the finite buffering capacity of the system workstations/production units. Yet, as the semiconductor industry moves to more extensive modes of automation, the explicit characterization and control of these additional operational features is of paramount importance for the robust and stable operation of the entire system. The work presented undertakes an analytical treatment of the scheduling problem of capacitated re-entrant lines, providing (i) a formal framework for the systematic integrated modeling of the system behavior and the super-imposed operational control logic, (ii) an analytical formulation of the scheduling problem in the context of this framework, and (iii) a qualitative characterization of the structure of the optimal scheduling policy. The proposed methodology is exemplified through application on a small system configuration, and while it suffers from a very high computational complexity, it is expected that the obtained characterizations will provide valuable analytical insights for developing pertinent approximating techniques.

Revisits the problem of the optimality of randomized deadlock avoidance policies for sequential resource allocation systems. The undertaken problem assumes that the various timing distributions are exponential and the performance objective of interest is the maximization of the system throughput. Our main finding is that under the aforestated assumptions, the randomization of the deadlock resolution policy does not lead to any efficiency increases. In other words, there will always exist an optimal solution in which each of the critical transitions from the safe to the unsafe region will always remain enabled or disabled. It is also shown, however, that randomization of the control of (some of) these transitions can provide an effective mechanism for accommodating additional operational constraints, like the observation of certain production ratios. Finally, an additional outcome of the presented work is the explicit characterization of the functional dependence of the considered objective function(s) to the system transition rates and the associated control variables, which provides broader insights regarding the (performance) control of continuous-time Markov chains under steady-state operation.