The problem of min-time coverage in constricted environments concerns the employment of robotic fleets to support routine inspection and service operations within well-structured but constricted environments. In our previous work we have provided a detailed definition of this problem, specifying the objectives and the constraints involved, a Mixed Integer Programming (MIP) formulation for it, a formal analysis of its worst-case computational complexity, and additional structural properties of the optimal solutions that enable a partial relaxation of the original MIP formulation which preserves optimal performance. We have further employed these structural results towards the development of a construction heuristic for this problem. But while the worst-case computational complexity of the construction heuristic is polynomial with respect to the size of the problem-defining elements, its practical scalability has been limited by the requirement to formulate and solve a large number of linear programming formulations. In order to address this issue, this work presents a modified version of the heuristic that significantly reduces the computational times involved. Furthermore, we develop a local search method that further improves the solution obtained from the modified heuristic.Note to Practitioners—This paper concerns the application of the current and the emergent robotic technologies in the inspection and monitoring of remote and difficult-to access facilities, like underground utility networks and oil and gas pipeline networks. The constricted and remote nature of these environments necessitates the careful preservation of a wireless ad hoc communication network among the deployed robots and a command-&-control center that supervises the entire operation, and this need gives rise to some novel, very interesting and very challenging coordination and scheduling problems. We have undertaken the investigation of these problems in a recent series of papers, providing a systematic formal characterization of them, and some analytical results that have identified important underlying structure and have also led to the development of a pertinent heuristic approach. This work complements and extends those earlier developments by enhancing significantly the computational expediency of the aforementioned heuristic method, and further augmenting the resulting computational capability to a systematic search method that can iteratively improve any available initial solution.

The problem of min-time coverage in constricted environments concerns the employment of networked robotic fleets for the support of routine inspection and service operations taking place in well-structured but constricted environments. In a series of previous works, we have provided a detailed definition of this problem, a Mixed Integer Programming (MIP) formulation for it, a formal analysis of its worst-case computational complexity, additional structural results for its optimal solutions that also enable the solution of the problem through a partial relaxation of the original MIP formulation, and we have further employed these structural results towards the development of a construction heuristic for this problem. But while the worst-case computational complexity of this heuristic is polynomial with respect to the size of the problem-defining elements, its practical scalability has been challenged by the need to solve a large (super-linear) number of linear programming formulations. This work introduces a modified version of the heuristic that has reduced very drastically the involved computational times.

The notion of the “$h$-ordered” traffic state provides an efficient approach for maintaining liveness in an open, irreversible, dynamically routed zone-controlled guidepath-based transport system. The restriction of these transport systems in their class of$h$-ordered states can be performed with polynomial complexity with respect to the size of these systems, while the resulting supervisory control policy retains high levels of operational latitude. The work presented in this article provides novel efficient algorithms for the following two problems: 1) assessing whether a given traffic state is$h$-ordered; and 2) bringing the underlying transport system from some general traffic state to the class of its$h$-ordered states in a way that minimizes a certain measure of “operational disruption.” The developed algorithms are motivated by, and find immediate applicability, in the model predictive control (MPC) scheme for the considered transport systems that was developed in[1].Note to Practitioners—Open and irreversible, zone-controlled, guidepath-based transport systems is a natural abstraction of the traffic dynamics taking place in many unit-load material handling systems (MHSs), like the automated guided vehicle (AGV) systems and the overhead monorail systems that are used in many industrial facilities. In these environments, vehicles are circulating in a “guidepath network” that is defined either by the physical structure of the corresponding MHS (as in the case of the overhead monorail systems) or more artificially, in an effort to isolate the traffic of these vehicles from the surrounding environment (as in the case of the AGV systems). Furthermore, in order to ensure collision-free motion for the traveling vehicles, the edges of this guidepath network are divided into zones, and it is stipulated that each zone is allocated to at most one vehicle at any time. This restriction renders the considered transport systems susceptible to deadlock, and therefore, their traffic controller must control the generated traffic for ensuring high productivity, but also for ensuring “traffic liveness,” i.e., the ability of every vehicle to complete successfully its current assignment and engage in similar assignments in the future. An effective and computationally efficient manner to maintain traffic liveness is by restricting the considered transport systems within a particular subclass of traffic states that is known as$h$-ordered. The considered article provides streamlined, customized algorithms for effecting this restriction.

Zone-controlled, guidepath-based transport system (ZC-GBTS) is a modeling abstraction that has been used extensively for the modeling of the safe interaction of a number of agents that circulate in a constricted medium. The traffic scheduling problem in these transport systems is very hard, and in some recent work of ours, we have proposed a model predictive control (MPC) scheme for simplifying this problem. The detailed implementation of this MPC scheme depends on certain structural and operational properties of the underlying ZC-GBTS. In this article, we detail the aforementioned MPC scheme for a ZC-GBTS subclass that is characterized as “open and irreversible”; the presented results leverage some earlier similar developments of ours for the subclass of “open and reversible” ZC-GBTS.

Fluid-relaxation-based scheduling is a powerful scheduling method with a long history in the context of scheduling of complex stochastic networks. In a recent work of ours, we have shown that this method holds extensive potential to provide near-optimal policies even when it is applied to scheduling problems that involve stochastic networks with blocking and deadlocking effects. However, those results were developed under the ad hoc representations for the continuous - or “fluid” - dynamics that define the “relaxation” of the original scheduling problem, that have been used traditionally by the various research communities that have investigated and/or employed this method. This document reports on our ongoing effort to recast our aforementioned results in the more formal modeling framework of timed-continuous Petri nets. We argue that this modeling framework provides a structured and natural framework for the implementation of this method in the context of the complex resource allocation that is the focus of our work, and we highlight the potential advantages of such a more structured approach.

This paper presents a heuristic algorithm for minimizing the makespan required to route a set of agents inhabiting a shared guidepath network from their initial locations to their respective destinations while observing a set of regulations that seek to ensure the safety and the integrity of the generated traffic. From an application standpoint, the presented developments are motivated by the traffic coordination challenges that arise in the context of many automated unit-load material handling systems and also in the transport of the ionized atoms that takes place in the context of quantum computing. From a methodological standpoint, our developments constitute a customization of the general “local-search” framework of combinatorial optimization theory to the traffic management problem that is considered in this paper. Hence, the presented results include a rigorous characterization of the considered problem and its solution space, detailed algorithms for the construction of the necessary initial solutions and the improving step for the pursued search, a complexity analysis of these algorithms, and a set of computational experiments that reveal and assess the computational efficiency of the presented algorithms and the efficacy of the derived solutions. The paper concludes with some suggestions for potential extensions of the presented results.

This paper extends the scheduling methodology for complex stochastic networks that is based on the solution of a “fluid” relaxation (FR) at each decision point of the original scheduling problem to stochastic networks with blocking and deadlocking effects. For a clearer and more concrete treatment, the presented results are developed in the operational context of a re-entrant line (RL) with finite buffering capacity at each workstation; these RLs are characterized as “capacitated RLs (CRLs).” From a methodological standpoint, the paper results are enabled by a pre-established ability to control the underlying resource allocation for deadlock freedom and by the further ability to express the corresponding deadlock avoidance policy as a set of linear inequalities on the system state. Also, the employed FR for this new regime differs from the FRs that have been employed in past implementations of the method since it must account for the blocking effects that take place in the considered CRLs. The efficacy of the presented scheduling method is assessed through numerical experimentation that compares, for a set of “benchmark” CRLs, the performance of the scheduling policies obtained through this method to 1) the performance of the corresponding optimal scheduling policies and also to 2) the performance of some other heuristic scheduling policies for these systems that are adapted from the relevant literature. Finally, an additional set of experiments demonstrates and assesses the scalability of the presented method by applying it to some pretty large system configurations.

While the supervisory control (SC) problem of (maximally permissive) deadlock avoidance for sequential resource allocation systems (RASs) has been extensively studied in the literature, the corresponding results that are able to address potential resource outages are quite limited, both, in terms of their volume and their control capability. This paper leverages the recently developed SC theory for switched discrete event systems (s-DES) in order to provide a novel systematic treatment of this more complicated version of the RAS deadlock avoidance problem. Following the modeling paradigm of s-DES, both the operation of the considered RAS and the corresponding maximally permissive SC policy are decomposed over a number of operational modes that are defined by the running sets of the failing resources. In particular, the target supervisor must be decomposed to a set of “localized predicates,” where each predicate is associated with one of the operational modes. A significant part, and a primary contribution, of this paper concerns the development of these localized predicates that will enable the formal characterization and the effective computation of the sought supervisor. With these predicates available, a distributed representation for the sought supervisor that is appropriate for real-time implementation is eventually obtained through an adaptation of the relevant distributed algorithm that is provided by the current s-DES SC theory.

In order to develop a computationally efficient implementation of the maximally permissive deadlock avoidance policy (DAP) for complex resource allocation systems (RAS), a recent approach focuses on the identification of a set of critical states of the underlying RAS state-space, referred to as minimal boundary unsafe states. The availability of this information enables an expedient one-step-lookahead scheme that prevents the RAS from reaching outside its safe region. The work presented in this paper seeks to develop a symbolic approach, based on binary decision diagrams (BDDs), for efficiently retrieving the (minimal) boundary unsafe states from the underlying RAS state-space. The presented results clearly demonstrate that symbolic computation enables the deployment of the maximally permissive DAP for complex RAS with very large structure and state-spaces with limited time and memory requirements. Furthermore, the involved computational costs are substantially reduced through the pertinent exploitation of the special structure that exists in the considered problem. Note to Practitioners-A key component of the real-time control of many flexibly automated operations is the management of the allocation of a finite set of reusable resources among a set of concurrently executing processes so that this allocation remains deadlock-free. The corresponding problem is known as deadlock avoidance, and its resolution in a way that retains the sought operational flexibilities has been a challenging problem due to: (i) the inability to easily foresee the longer-term implications of an imminent allocation and (ii) the very large sizes of the relevant state spaces that prevent an online assessment of these implications through exhaustive enumeration. A recent methodology has sought to address these complications through the offline identification and storage of a set of critical states in the underlying state space that renders efficient the safety assessment of any given resource allocation. The results presented in this paper further extend and strengthen this methodology by complementing it with techniques borrowed from the area of symbolic computation; these techniques enable a more compressed representation of the underlying state spaces and of the various subsets and operations that are involved in the pursued computation.

The 12 papers in this special section can be divided into two sets. The first eight papers deal with general DES control problems, while the second set of four papers addresses other particular DES problems such as diagnosability analysis, state estimation, deadlock avoidance and testing.

An earlier work of ours has proposed a novel approach for the deployment of the maximally permissive deadlock avoidance policy for complex resource allocation systems (RAS), that is based on the identification and the efficient storage of a critical subset of states of the underlying RAS state space; the availability of this information enables an expedient one-step-lookahead scheme for the identification and blockage of transitions that will take the system behavior outside its safe region. This paper complements the aforementioned results by introducing a novel algorithm that provides those critical states while avoiding the complete enumeration of the RAS state space.

Past works towards the effective deployment of the maximally permissive liveness-enforcing supervisor (LES) for sequential resource allocation systems (RAS) have been stalled by: (i) the NP-Hardness of the computation of this policy for the majority of the considered RAS classes and (ii) the inability of the adopted more compact representations of the underlying RAS dynamics to provide an effective representation of the target policy for all RAS instantiations. This paper proposes a novel approach to the aforementioned problem, that can be perceived as a two-stage process: The first stage computes the maximally permissive LES by employing an automaton-based representation of the RAS behavior and techniques borrowed from the Ramadge & Wonham (R&W) Supervisory Control framework. The second stage seeks the development of a more compact representation for the dichotomy into admissible and inadmissible—or “safe” and “unsafe”—subspaces of the RAS state space, that is effected by the LES developed in the first stage. This compact representation is obtained by: (i) taking advantage of certain properties of the underlying subspaces and (ii) the employment of pertinent data structures. The resulting approach is also “complete,” i.e., it will return an effectively implementable LES for any given RAS instantiation. Numerical experimentation demonstrates the efficacy of the approach and establishes its ability to support the deployment of maximally permissive LES for RAS with very large structure and state spaces.

We propose a novel paradigm for conflict resolution in multivehicle traffic systems, where a number of mobile agents move freely in a finite area, with each agent following a prespecified-motion profile. The key idea behind the proposed method is the tessellation of the underlying motion area in a number of cells and the treatment of these cells as resources that must be acquired by the mobile agents for the execution of their motion profiles, according to an appropriate resource allocation protocol. We capitalize upon the existing literature on the real-time management of sequential resource allocation systems (RASs) and develop such protocols that can formally guarantee the safe and live operation of the underlying traffic system, while they remain scalable with respect to the number of the moving agents. Collective past experience with the considered policies indicates that they also provide a pretty large coverage of the RAS behavioral space that characterizes its safe and live operation. Finally, we also establish that the aforementioned approach is applicable even in traffic systems where all vehicles must be in perpetual motion until their retirement.

The safety problem in multi-vehicle systems seeks to establish collision-free and live vehicle motion, and it is a prominent problem for many configurations of these environments. Past work studying this problem in the context of free-range vehicular systems through abstractions based on Resource Allocation System (RAS) theory, has implicitly assumed that its resolution through maximally permissive supervision is NP-hard, and therefore, it has typically pursued suboptimal (i.e., more restrictive) solutions. The work presented in this paper offers formal proof to this implicit assumption, closing the apparent gap in the existing literature.

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 work presented in this paper seeks 1) to correct and generalize some previously published results regarding the siphon control in PT-ordinary Petri nets (PNs) and, subsequently, 2) to employ this generalized framework in order to provide an alternative explanation of the way in which certain methodologies that have been proposed in the past enforce the liveness of a particular class of PT-ordinary PN-modeling resource allocation. The derived characterizations provide a unifying framework for analyzing and interpreting the aforementioned methodologies, and also, they reveal that approaches that have been considered as disparate in the current literature can actually be "mixed" toward the development of an ever richer set of liveness-enforcing supervisory-control policies for the considered class of PNs

The first part of this paper develops a linear characterization for the space of the Petri net markings that are reachable from the initial marking M0through bounded-length fireable transition sequences. The second part discusses the practical implications of this result for the liveness and reversibility analysis of a particular class of Petri nets known as process-resource nets with acyclic, quasi-live, serializable, and reversible process subnets. Note to Practitioners-One of the main challenges in the analysis and design of the resource allocation taking place in modern technological systems is the verification of certain properties of the system behavior such as liveness and deadlock freedom. The last decade has seen the development of a number of computational tests that can evaluate the aforementioned properties for a large class of resource allocation systems. The tests that are most promising essentially verify the target properties by establishing the absence of some undesirable structure from the states that are reachable during system operation. As a result, the effective execution of these tests necessitates the effective representation of the underlying reachability space. Yet, in the past, the development of a concise and computationally manageable representation of the system reachability space has been considered to be a challenging proposition and a factor that compromises the resolution power of the aforementioned tests. The work presented in this paper establishes that for a very large class of the considered resource allocation systems, the underlying reachability space admits a precise and computationally efficient characterization, which subsequently leads to more powerful verification tools of the target behavioral properties

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.

Currently there is increasing consensus that one of the main issues differentiating the remanufacturing from the more traditional manufacturing processes is the need to effectively model and manage the high levels of uncertainty inherent in these new processes. The work presented in this paper formally establishes that the theory of reinforcement learning, one of the most actively researched areas in computational learning theory, constitutes a rigorous, effectively implementable modelling framework for providing (near) optimal solutions to the optimal disassembly planning (ODP) problem, one of the key problems to be addressed by remanufacturing processes, in the face of the aforementioned uncertainties. The developed results are exemplified and validated by application on a case study borrowed from the relevant literature.

The work presented in this paper extends recently developed in the theory of resource allocation systems (RAS) to RAS behaviors that present synchronization requirements in the underlying process flows. More specifically, the paper first provides a formal definition of the considered RAS structures and behaviors by introducing the Petri net sub-class of generalized augmented marked graphs (G-AMG), and subsequently, it proceeds to the analysis of the liveness properties of the resource allocation underlying the G-AMG operation. It is shown that similar to the case of some previously studied RAS structures, non-liveness of the resource allocation taking place in the G-AMG context can be attributed to a structural object known as resource-induced deadly marked siphon, that is developed in a properly defined projection of the net reachability space. Beyond its theoretical significance in terms of formally characterizing and understanding the nature of deadlock or livelock that can occur in the considered resource allocation context, the aforementioned result is also deemed to be important from the practical standpoint of synthesizing liveness-enforcing supervisors (LES), since it is expected to enable LES synthesis through application of the correctness verification methodology originally developed in (J. Park and S. Reveliotis, 2001); the actual potential of this approach is currently under investigation.

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.

Although liveness enforcing supervision (LES) of sequential resource allocation systems (RAS) is currently a well-established problem in the discrete event system literature, all prior work on it has addressed the underlying LES synthesis problem under the assumption that the system event set is totally controllable. The first part of this work. seeks to relax the controllability assumption, by developing correct and scaleable LES for RAS in which some of the requested resource allocations are uncontrollable. The second part of the presented work addresses the accommodation in the original LES synthesis problem of additional logical constraints, that constitute "forbidden state" specifications and possess a linear characterization with respect to the system resource allocation state. Both problems are addressed in the context of conjunctive/disjunctive-RAS, that constitutes one of the broadest RAS classes investigated in the literature, allowing for arbitrarily structured resource allocations associated with the various process stages, and process routing flexibility.

Although liveness enforcing supervision (LES) of sequential resource allocation systems (RAS) is currently a well-established problem in the Discrete Event System literature, all prior work on it has addressed the underlying LES synthesis problem under the assumption that the system behavior is totally controllable. The work presented in this paper seeks to develop correct and scaleable LES for RAS that present uncontrollability with respect to: 1) the timing of some requested resource allocations, i.e., these allocations will take place as long as the requested resources are available and/or 2) the routing of certain job instances that, after some processing stages, might request special treatment or rework. In addition, the last part of the paper addresses the accommodation in the original LES synthesis problem of externally imposed logical constraints, that constitute "forbidden state" specifications and possess a linear characterization with respect to the system resource allocation state. All problems are addressed in the context of Conjunctive/Disjunctive (CD)-RAS, that constitutes one of the broadest RAS classes. investigated in the literature, allowing for arbitrarily structured resource allocations associated with the various process stages, and process routing flexibility.

Liveness-enforcing supervisors (LESs) guarantee deadlock-free operations in resource allocation systems (RASs). Given the growing emphasis on higher resource utilization and operational flexibility, it is greatly desirable to obtain the optimal LES that can provide the maximum behavioral latitude. In general, however, computation of the maximally permissive LES is computationally intractable and, accordingly, the class of algebraic LESs has been proposed in the literature as a viable suboptimal alternative for various RAS classes. The objective of this work is to further enhance the permissiveness of algebraic LESs by taking advantage of the routing flexibility inherent in contemporary RASs. Specifically, we consider a class of algebraic LES that allows supervisor parameterizations based on the system routing flexibility, and propose a method to effectively mix the algebraic LESs obtained from the policy instantiation through a set of different parameter values. The resulting policy mixture, to be called dynamic algebraic LES, provides increased permissiveness as it allows flexible online switching among different resource reservation schemes, corresponding to different process routings. The proposed method for constructing the dynamic algebraic LES is presented in the context of the class of conjunctive/disjunctive RASs, which subsumes the major RAS classes currently studied in the literature.

Operational flexibility of deadlock avoidance policies (DAPs) is an essential requirement for achieving high resource utilization of the underlying deadlock-prone resource allocation system. The paper presents computational methods for synthesizing highly flexible DAPs for the class of conjunctive/disjunctive resource allocation systems (CD-RAS), which generalizes the resource allocation model that has been typically studied in the past, by allowing multiple resource acquisitions and flexible routings. Specifically, a linear programming method to compute DAPs for CD-RAS is developed, and subsequently a series of computational tools are provided to enhance the policy permissiveness/flexibility. These methods are based on: (i) the pertinent exploitation of the policy parameterization, (ii) the observation that the considered class of policies is closed under policy disjunctions, and (iii) the systematic relaxation of the policy-imposed constraints through Petri net structural analysis. The presented results are demonstrated through an example modeling an agile automation system.

As the effective deployment of system production capacity and operational capability becomes critical for competitive semiconductor manufacturing, there is an increasing interest toward the development of a control framework which allows effective and efficient operation of the emerging 300 mm wafer fabs. In the paper, a colored Petri net-based approach is taken to develop such a distributed event-driven 300 mm fab controller. The key element of the proposed controller design is the distribution of control function, to the constituent components of the 300 mm fab, while maintaining the logical correctness and efficiency of the fab behavior. Furthermore, in order to achieve the viability of the resulting control scheme, the proposed approach seeks to incorporate detailed operational characteristics of the 300 mm fabs, including batching, setups, reworks, maintenance, machine failures, and complex resource allocation dynamics due to the routing flexibility and auxiliary resource sharing. The proposed approach is demonstrated through a small-scale example, modeling the operation of a 300 mm fab bay.

Semiconductor fabs are capital intensive. The rate of capital return heavily depends on their productivity. Accordingly, simulation has been adopted in many cases as a viable design and analysis tool to achieve better productivity. However, the gap between the simplistic simulation models and real complex systems has limited the confidence to apply simulation results directly to real systems. Ideally, the simulator should support the rapid modeling and fast execution of high-fidelity fab models in order to be able to provide more realistic simulation results. In this paper, we present our current research effort to develop a high-fidelity web-based simulator for the 300 mm wafer fabs. We take a model-view-control approach that allows us to develop modular and reusable fab simulation objects. The proposed approach is implemented as a distributed system that uses a message-based event synchronization mechanism to coordinate the simulation objects as well as to support distributed simulation execution. The presented simulator also provides a high quality VRML animation for visualization of real time paced simulation execution.

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.

Deadlock avoidance in sequential resource allocation systems is a well-defined problem in discrete event system literature, as it underlies the operation of many contemporary technological systems. In the past, the problem has been studied by means of a number of formal frameworks, including the finite state automata (FSA) and Petri nets (PN). In this paper, it is shown that a significant class of deadlock avoidance policies (DAP), known as algebraic PK-DAP, originally developed in the FSA paradigm, can be analyzed using recent results from PN structural analysis. Furthermore, the approach to DAP analysis and design taken in this paper has led to the effective generalization of the currently available algebraic PK-DAP, and to their enrichment with new and more flexible policy implementations.

Deadlock avoidance in sequential resource allocation systems is a well-defined problem in discrete event system literature, as it underlies the operation of many contemporary technological systems. In the past, the problem has been studied by means of a number of formal frameworks, including the finite-state automata (FSA) and Petri nets (PNs). In this paper, it is shown that a significant class of deadlock avoidance policies (DAPs), known as algebraic polynomial kernel (PK)-DAPs, originally developed in the FSA paradigm, can be analyzed using recent results from PN structural analysis. Furthermore, the approach to DAP analysis and design taken in this paper has led to the effective generalization of the currently available algebraic PK-DAPs, and to their enrichment with new and more flexible policy implementations.

Motivated by recent developments in the semiconductor manufacturing industry, this paper undertakes an analytical investigation of the problem of selecting optimally the deadlock resolution strategy for buffer space allocation in flexibly automated production systems. In the process, it extends the behavioral models for the aforementioned systems currently considered in the literature, to account for probabilistic uncontrollable effects like the requirement for extra finishing steps and/or rework, and it introduces a new deadlock resolution scheme, characterized as randomized deadlock avoidance. The combination of these two extensions brings the considered system behavior(s) to the realm of probabilistic automata, an area of increasing academic interest. For the resulting model, and under the assumption of Markovian timings, it develops an analytical methodology for selecting the optimal deadlock resolution strategy that maximizes the steady-state system throughput, and it demonstrates its effectiveness through application to a "prototype" system configuration. The obtained results provide an interesting analytical expression of the need to assess the gains obtained by the increased concurrency supported by the deadlock detection and recovery strategy versus the productivity losses experienced under this approach due to increased system blocking, and/or additional material handling overheads. It turns out that, for the considered system configuration, the optimal selection scheme switches between detection and recovery and pure deadlock avoidance, every time that the time cost of deadlock recovery, tau(d), crosses a threshold Theta, which is a function of the remaining system behavioral and timing parameters. Beyond its own theoretical merit, this last result raises also the question of whether the policy randomization introduced in this work will ever enhance the performance of any configuration in the considered class of Resource Allocation Systems (RAS); this issue will be investigated in a sequel paper.

Starting from the observation that currently we lack the control policies to effectively establish and manage the operational flexibilities required by contemporary flexibly automated manufacturing systems, the paper articulates a proposition towards the development of a formal production planning and control framework for these environments. This framework essentially attempts to integrate emerging results on the representation and control of these environments through a bottom-up hierarchical modeling and analysis approach. Open research problems that will underlie such an integration effort are identified, and potential solution approaches are briefly outlined.

Overwhelmed by the complexity of the FMS deadlock avoidance problem, current research has, for the most part, ignored the aspects (and benefits) related to flexible (dynamic) job routing. Extending current structural control policies, based on static job routing, to accommodate routing flexibility is nontrivial, primarily due to the fact that the possible routing options for a single job can grow exponentially fast. Hence, computationally efficient techniques are required to incorporate the inherent FMS routing flexibility to current structural control schemes. This paper undertakes the investigation of the problem of integrating routing flexibility in FMS structural control, by addressing the problem of "optimal" job rerouting in case of operational contingencies. Analytical formulations and efficient solution algorithms are developed for the case that the FMS is structurally controlled by a class of recently emerging polynomial-complexity one-step look ahead deadlock avoidance policies, collectively known as /spl Omega/ DAP.

Overwhelmed by the complexity of the FMS deadlock avoidance problem, current research has essentially ignored the aspects (and benefits) related to flexible (dynamic) job routing. Furthermore, extending the currently existing results along this line is nontrivial, primarily because of the fact that the possible routing options for a single job can grow exponentially fast. Hence, computationally efficient techniques are required to incorporate the inherent FMS routing flexibilty into current structural control schemes. The paper initiates the investigation on the problem of integrating routing flexibility in FMS structural control, by addressing the problem of "optimal" job re-routing in the case of operational contingencies. An analytical problem formulation and an efficient solution algorithm are developed for the case that the FMS is structurally controlled by the resource upstream neighborhood (RUN) policy, a deadlock avoidance policy previously presented in the literature. Beyond the value of the presented results, the paper is intended also to outline a methodological approach to the underlying problems.

We show that the generic logic underlying the classical Banker's algorithm (Habermann, 1969), is a very flexible and powerful tool for developing correct and computationally efficient deadlock avoidance policies for a broad variety of structural control applications arising in contemporary large-scale flexibly automated environments. Although we draw our examples from the manufacturing domain, it can be clearly seen that similar problems arise in the context of other technological applications, e.g., monorail transportation systems.

Configuration flexibility and deadlock-free operation are two essential properties of control systems for highly automated flexible manufacturing systems. Configuration flexibility, the ability to quickly modify manufacturing system components and their logical relationships, requires automatic generation of control executables from high level system specifications. These control executables must guarantee deadlock-free operation. The resource order policy is a configurable controller that provides the deadlock-free guarantee for buffer space allocation. It uses a total ordering of system machines and routing information to generate a set of configuration specific linear constraints. These constraints encode the system state along with a buffer capacity function and define a deadlock-free region of operation. Constraint generation and execution are of polynomial complexity.

The problem of evaluating the capacity of the structurally controlled FMS has been raised previously by us (1996). In that paper, an analytical framework for the problem, and a methodology able to provide accurate performance estimates were developed, but it was also observed that the computational complexity of the approach rendered it inapplicable to most practical situations. Here, we propose an approximating scheme for the performance evaluation of the structurally controlled FMS, which presents polynomial computational complexity, and therefore, is applicable to real-life FMSs. Initial experimentation with the approach indicates that it holds considerable promise for effective evaluation of the production capacity of these systems.

Resolving the problem of the manufacturing system deadlock is emerging as a critical issue for effective planning and control in the agile manufacturing paradigm. It turns out that, in most cases, the problem is of nonpolynomial complexity, and its tractability strongly depends on the structure of the resource requests posed by the processed jobs. The authors have previously (1994, 1995) formally analyzed the problem and provided solutions for the special class of FMS where every job requires a single resource unit at every processing stage, namely, a unit of buffer space on the supporting workstation. In this paper, we extend the analysis and one of the previously developed policies-the resource upstream neighborhood (RUN) policy-so that they apply to FMS's in which every job requires a collection of resources for the execution of a single processing stage.

Defining the capacity of the structurally controlled FMS is an extremely involved task. Most existing evaluation models fail to capture all these features that define the effective capacity of such a system. Recognizing that, under the assumption of exponential processing times, the structurally controlled FMS behaves like a continuous-time Markov chain, this paper proposes an analytical framework for evaluating and optimizing its attained performance. Due to its nonpolynomial computational cost, the approach is applicable only to small FMS configurations, but it seems to be the only known framework able to support the exact solution of the considered problem. Furthermore, it can provide the insight needed for the development of valid approximating techniques that are computationally tractable.

This paper suggests a framework for developing provably correct and scalable avoidance policies for the automated manufacturing cell (AMC) model. We provide a formal description of the AMC operation and establish its correspondence to a finite state automaton (FSA). The AMC model's deadlock characteristics are studied with the aid of the FSA state transition diagram. We provide a new characterization of AMC state safety which serves as the basis of a new framework for systematic development of avoidance policies. We provide two examples of the framework functionality. First, the framework is used to formally prove the correctness of the resource upstream neighborhood (RUN) avoidance policy (Gaarder, 1993). Then, it is used to provide an alternative proof for the correctness of B-K deadlock avoidance algorithm (BKDAA) (Banaszak et al., 1990). Furthermore, an interesting relationship existing between RUN and BKDAA policies is brought out. Finally, the results are summarized, conclusions drawn, and possible extensions and generalizations of the underlying ideas discussed.

In this paper a learning framework to deal with restructurable control of a single-output dynamic plant is proposed. The central concept used to represent the restructurable behavior of the plant, and subsequently for the design of the framework, is the behavioral graph. The nodes of this graph correspond to possible local behaviors of the system while its edges model the switching scheme of the plant among its local behaviors. In the definition of this concept, general dynamical system theory is used. The framework is able to learn the dynamics (models) of a reconfigurable system, select appropriate models, and ultimately control the plant according to given specifications. The framework design borrows concepts and techniques from the active fields of adaptive and learning control. The underlying ideas and the software prototype implementing the framework design are tested through a series of simulated experiments. The simulations demonstrate the feasibility of the approach for controlling plants with unexpectedly and structurally changing behaviors in moderately noisy environments. They also identify a number of constraints that have to be satisfied for successful operation of the framework. This paper also discusses further validation of the approach, real-time application issues, and potential enhancements of the framework's functionality.>

This article is related to the research effort of constructing an intelligent agent, i.e., a computer system that is able to sense its environment (world), reason utilizing its internal knowledge and execute actions upon the world (act). the specific part of this effor presented in this article is reinforcement learning, i.e., the process of acquiring new knowledge based upon an evaluative feedback, called reinforcement, received by tht agent through interactions with the world. This article has two objectives: (1) to give a compact overview of reinforcement learning, and (2) to show that the evolution of the reinforcement learning paradigm has been driven by the need for more efficient learning through the addition of more structure to the learning agent. Therefore, both main ideas of reinforcement learning are introduced, and structural solutions to reinforcemen learning are reviewed. Several architectural enhancements of the RL paradigm are discussed. These include incorporation of state information in the learning process, architectural solutions to learning with delayed reinforcement, dealing with structurally changing worlds through utilization of multiple models of the world, and focusing attention of the learning agent through active perception. the paper closes with an overview of directions for applications and for future research in this area. © 1993 John Wiley & Sons, Inc.