Abstract Theoretical analyses of a set of iterated‐tour partitioning vehicle routing algorithms applicable to a wide variety of commonly used vehicle routing problem variants are presented. We analyze the worst‐case performance of the algorithms and establish tightness of the derived bounds. Among other variants, we capture the cases of pick‐up and delivery and multiple depots. We also introduce brand new concepts such as mobile depots, partitioning of customer nodes into groups, and potential opportunistic under‐utilization of vehicle capacity by only partially loading the vehicle, among others, which arise from a printed circuit board application. The problems studied are of critical importance in many practical applications. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Presents a framework for accommodating human intervention in a computer supervised discrete-event system. The basic mechanism for allowing such hybrid supervision by a computer and a human operator is by switching priorities between events controlled by each according to some specified schedule. To synthesize a computer supervisor under such conditions, a transformation that maps the problem to one that satisfies the model stipulations of the supervisory control theory is presented. The aforementioned framework introduces a parameter that can be tuned to provide for different levels of co-operation between the human and computer supervisors. Several important properties of the resulting supervisors are presented.

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.

The determination of a set of geometric entities that satisfy a series of geometric relations (constraints) constitutes the Geometric Constraint Satisfaction or Scene Feasibility (GCS/SF) problem. This problem appears in different forms in Assembly Planning, Constraint Driven Design, Computer Vision, etc. Its solution is related to the existence of roots to systems of polynomial equations. Previous attempts using exclusively numerical (geometry) or symbolic (topology) solutions for this problem present shortcomings regarding characterization of solution space, incapability to deal with geometric and topological inconsistencies, and very high computational expenses. In this investigation Grobner Bases are used for the characterization of the algebraic variety of the ideal generated by the set of polynomials. Properties of Grobner Bases provide a theoretical framework responding to questions about consistency, ambiguity, and dimension of the solution space. It also allows for the integration of geometric and topological reasoning. The high computational cost of Buchberger's algorithm for the Grobner Basis is compensated by the choice of a non redundant set of variables, determined by the characterization of constraints based on the subgroups of the group of Euclidean displacements SE(3). Examples have shown the advantage of using group based variables. One of those examples is discussed.