Variance of the throughput of an N-station production line with no intermediate buffers and time dependent failures

In this study, the variance of the throughput of an N-station production line with no intermediate buffers and time dependent failures is analytically determined. Time to failure and time to repair distributions are assumed to be exponential. The analytical method yields a closed-form expression for the variance of the throughput. The method is based on determining the limiting variance of the total residence (sojourn) time in a specific state of an irreducible recurrent Markov process from the probability of visiting that state at time t given an initial state. This probability function is the instantaneous availability of a production system in the reliability context. A production line with no interstation buffers and time-dependent failures is basically a series system with hot standby. The same procedure can be applied to determine the variance of the throughputs of various arrangements of workstations including series, parallel, series-parallel systems provided that the instantaneous availabilities of these systems can be written explicitly. Numerical experiments show that, although the expected throughput decreases monotonically, the variance of the throughput may increase and then decrease as the number of stations in the line increases depending on the system parameters. Numerical experiments that investigate this phenomenon and also the dependence of the coefficient of variation on the number of stations are also presented in this study.     

Multi-state throughput analysis of a two-stage manufacturing system with parallel unreliable machines and a finite buffer

This paper models and analyzes the throughput of a two-stage manufacturing system with multiple independent unreliable machines at each stage and one finite-sized buffer between the stages. The machines follow exponential operation, failure, and repair processes. Most of the literature uses binary random variables to model unreliable machines in transfer lines and other production lines. This paper first illustrates the importance of using more than two states to model parallel unreliable machines because of their independent and asynchronous operations in the parallel system. The system balance equations are then formulated based on a set of new notations of vector manipulations, and are transformed into a matrix form fitting the properties of the Quasi-Birth–Death (QBD) process. The Matrix-Analytic (MA) method for solving the generic QBD processes is used to calculate the system state probability and throughput. Numerical cases demonstrate that solution method is fast and accurate in analyzing parallel manufacturing systems, and thus prove the applicability of the new model and the effectiveness of the MA-based method. Such multi-state models and their solution techniques can be used as a building block for analyzing larger, more complex manufacturing systems.     

On Passive and Conservative State/Signal Systems

This article is devoted to a study of continuous-time passive and conservative systems within the state/signal framework. The main idea of the state/signal approach is to not a priori distinguish between inputs and outputs, but rather to combine these two into a single external signal. The so-called node space is introduced as the product of two copies of the state space of the system and one copy of the space where the external signals of the system live. This node space is equipped with a sesquilinear product that makes it a Kre?n space. A generating subspace is defined as a closed subspace of the node space, and the node space determines the trajectories of a state/signal system. One of the main results of this article is that a subspace of the node space generates a passive state/signal system if and only if it is a maximally nonnegative subspace of the node space and it satisfies a certain nondegeneracy condition. In this case the generating subspace can be interpreted as the graph of a scattering-passive input/state/output system node.     

A construction of unitary linear systems

A construction is made of a unitary linear system whose transfer function is a given power seriesB(z) with operator coefficients such that multiplication byB(z) is an everywhere defined transformation in the space of square summable power series with vector coefficients. A condition is also given for the existence of an observable linear system with such a transfer function. For both constructions properties of the spaces are given which imply essential uniqueness of linear systems with given transfer functions. A canonical conjugate-isometric linear system is uniquely determined by its transfer function whenever the state space is a Pontryagin space.     

Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems

We study a processing system comprised of parallel queues, whose individual service rates are specified by a global service mode (configuration). The issue is how to switch the system between various possible service modes, so as to maximize its throughput and maintain stability under the most workload-intensive input traffic traces (arrival processes). Stability preserves the job inflow–outflow balance at each queue on the traffic traces. Two key families of service policies are shown to maximize throughput, under the mild condition that traffic traces have long-term average workload rates. In the first family of cone policies, the service mode is chosen based on the system backlog state belonging to a corresponding cone. Two distinct policy classes of that nature are investigated, MaxProduct and FastEmpty. In the second family of batch policies (BatchAdapt), jobs are collectively scheduled over adaptively chosen horizons, according to an asymptotically optimal, robust schedule. The issues of nonpreemptive job processing and non-negligible switching times between service modes are addressed. The analysis is extended to cover feed-forward networks of such processing systems/nodes. The approach taken unifies and generalizes prior studies, by developing a general trace-based modeling framework (sample-path approach) for addressing the queueing stability problem. It treats the queueing structure as a deterministic dynamical system and analyzes directly its evolution trajectories. It does not require any probabilistic superstructure, which is typically used in previous approaches. Probability can be superposed later to address finer performance questions (e.g., delay). The throughput maximization problem is seen to be primarily of structural nature. The developed methodology appears to have broader applicability to other queueing systems.     

On the stabilizability problem in Banach space

The model is a linear system defined on Banach (state and control) spaces, with the operator acting on the state only the infinitesimal generator of a strongly continuous semigroup. The stabilizability problem of expressing the control through a bounded operator acting on the state as to make the resulting feedback system globally asymptotically stable is considered. On the negative side, and in contrast with the finite dimensional theory, a few counter examples are given of systems which are densely controllable in the space and yet are not stabilizable, even if some further “nice properties” hold. Use is made of the notion of essential spectrum and its stability under relatively compact perturbations. On the positive side, it is shown, however, that for large classes of systems of physical interest (classical selfadjoint boundary value problems, delay equations, etc.) controllability on a suitable finite dimensional subspace still yields stabilizability on the whole space.     

Mixed-width aisle configurations for order picking in distribution centers

Space required for the order picking area and labor required to perform the picking activity are two significant costs for a distribution center (DC). Traditionally, DCs employ either entirely wide or entirely narrow aisles in their picking systems. Wide aisles allow pickers to pass each other, which reduces blocking, and requires fewer pickers than their narrow-aisle counterpart for the same throughput. However, the amount of space required for wide-aisle configurations is high. Narrow aisles utilize less space than wide aisles, but are less efficient because of the increased likelihood of congestion experienced by pickers. We propose a variation to the traditional orthogonal aisle designs where both wide and narrow aisles are mixed within the configuration, with a view that mixed-width aisles may provide a compromise between space and labor. To analyze these new mixed-width aisle configurations, we develop analytical models for space and travel time considering randomized storage and traversal routing policies. Through a cost-based optimization model, we identify system parameters for which mixed-width aisle configurations are optimal. Experimental results indicate that annual cost savings of up to $48,000 can be realized over systems with pure wide or narrow aisle configurations.     

Identification of switched linear systems using subspace and integer programming techniques

We consider the identification of a switched linear system which consists of linear sub-models, with a rule that orchestrates the switching mechanism between the sub-models. Taking a set of switched linear systems and using a state space framework, we show that it is possible to combine subspace methods with mixed integer programming for system identification. The states of the system are first extracted from input–output data using sub-space methods. Once the state variables are known, the switched system is re-written as a mixed logical dynamical (MLD) system and the model parameters are calculated for via mixed integer programming. We report an example at the end of this paper together with simulation results in the presence of noise.     

Digital modeling and control of multiple time-delayed distributed power grid

Distributed power grid (DPG) control systems are so highly interconnected that the effects of local disturbances as well as transmission time delays can be amplified as they propagate through a complex network of transmission lines. These effects deteriorate control performance and could possibly destabilize the overall system. In this paper, a new approximated discretization method and digital design for DPG control systems with multiple state, input and output delays as well as a generalized bilinear transformation method are presented. Based on a procedure for the generation of impulse response data, the multiple fractional/integer time-delayed continuous-time system is transformed to a discrete-time model with multiple integer time delays. To implement the digital modeling, the singular value decomposition (SVD) of a Hankel matrix together with an energy loss level is employed to obtain an extended discrete-time state space model. Then, the extended discrete-time state space model of the DPG control system is reformulated as an integer time-delayed discrete-time system by computing its observable canonical form. The proposed method can closely approximate the step response of the original continuous time-delayed DPG control system by choosing various energy loss levels. For completeness, an optimal digital controller design for the DPG control system and a generalized bilinear transformation method with a tunable parameter are also provided, which can re-transform the integer time-delayed discrete-time model to its continuous-time model. Illustrative examples are given to demonstrate the effectiveness of the developed method.     

Bucket brigades revisited: Are they always effective?

Previous work on the dynamics of bucket brigades has focused on systems in which workers can be ordered with respect to their speeds and where this ordering does not change throughout the line. While this assumption is valid in most environments, it may not be satisfied in some. We consider such environments and explore the conditions under which bucket brigades continue to be effective (compared to a traditional static allocation) with respect to self-balancing behavior and throughput performance. A two worker bucket brigade is studied where one worker is faster than the other over some part of the production line and slower over another part of the line. We analyze the dynamics and throughput of the bucket brigade in two environments with passing and blocking. We present the dynamics of the system in each region of the parameter space and provide insights and operating principles for the implementation and management of the bucket brigades under various scenarios.     

Linear stabilization of the programmed motions of non-linear controlled dynamical systems under parametric perturbations

A non-linear controlled dynamical system that describes the dynamics of a broad class of non-linear mechanical and electromechanical systems (in particular, electromechanical robot manipulators) is considered. It is proposed that the real parameter vector of a non-linear controlled dynamical system belongs to an assigned (admissible) constrained closed set and is assumed to be unknown. The programmed motion of the non-linear controlled dynamical system and the programmed control that produces it are assigned (constructed) by using an estimate, that is, the nominal value of the parameter vector of the non-linear controlled dynamical system, which differs from its actual value. A procedure for synthesizing stabilizing control laws with linear feedback with respect to the state that ensure stabilization of the programmed motions of the non-linear controlled dynamical system under parametric perturbations is proposed. A non-singular linear transformation of the coordinates of the state space that transforms the original non-linear controlled dynamical system in deviations (from the programmed motion and programmed control) into a certain non-linear controlled dynamical system of special form, which is convenient for analysing and synthesizing laws for controlling the motion of the system, is constructed. A certain non-linear controlled dynamical system of canonical form is derived in the original non-linear controlled dynamical system in deviations. The transformation of the coordinates of the state space constructed and the Lyapunov function methodology are used to synthesize stabilizing control laws with linear feedback with respect to the state, which ensure asymptotic stability as a whole of the equilibrium position of the non-linear controlled dynamical system of canonical form and dissipativity “in the large” of the non-linear controlled dynamical system of special form and of the original non-linear controlled dynamical system in deviations. In the control laws synthesized, the formulae for the elements of their matrices of the feedback loop gains do not depend on the real parameter vector of the non-linear controlled dynamical system, and they depend solely on the constants from certain estimates that hold for all of its possible values from an assigned set. Estimates of the region of dissipativity “in the large” of the non-linear controlled dynamical system of special form and the original non-linear controlled dynamical system in deviations closed by the stabilizing control laws synthesized are given, and estimates for their limit sets and regions of attraction are presented.     

On factorial states of operator algebras

Results for the factorial state space of a C¹-algebra A which are analogous to results of 11., 12., 572–612),Tomiyama and Takesaki (Tohôku Math. J. (2) 13 (1961), 498–523) for the pure state space. It is shown that A is prime if and only if the (type I) factorial states are dense in the state space. It follows that every factorial state is a w¹-limit of type I factorial states. The factorial state space of a von Neumann algebra is determined, and it is shown that if A is unital and acts non-degenerately on a Hilbert space then the factorial state space of the generated von Neumann algebra restricts precisely to the factorial state space of A. It is shown that the set of factorial states is w¹-compact if and only if A is unital, liminal and has Hausdorff primitive ideal space.     

Transient analysis of a single server queue with catastrophes, failures and repairs

A transient solution is obtained analytically using continued fractions for the system size in an M/M/1 queueing system with catastrophes, server failures and non-zero repair time. The steady state probability of the system size is present. Some key performance measures, namely, throughput, loss probability and response time for the system under consideration are investigated. Further, reliability and availability of the system are analysed. Finally, numerical illustrations are used to discuss the system performance measures.      

Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems

In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.     

Relative controllability of linear stationary completely integrable Pfaff systems

We consider a process described by stationary completely integrable Pfaff systems linear in the input and the control as well as in the output and the state. We study the state controllability properties of the Pfaff system for the case in which an arbitrary initial state (a constant vector) and an arbitrary terminal state (either a constant vector, or an analytic vector function, or a constant vector and an analytic vector function) are given. The terminal states belong to a subspace of the state space of the system. The entire set of Pfaff systems splits into three classes, in each of which we obtain conditions for the controllability of Pfaff systems in the class of analytic controls. The conditions are stated in terms of the rank of some matrices formed from the given matrices of the Pfaff system and the matrix that specifies the subspace of terminal states.     

Asymptotic properties of constrained Markov Decision Processes

We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII     

样条状态变量法分析弹性矩形板的动力响应

应用样条元与状态空间法分析矩形板的动力响应问题.对空间域采用样条元法,对时间域采用现代控制论中的状态空间法.建立了状态变量递推格式,可直接计算结构的动力响应量.文末给出了若干数值算例,计算结果表明,该方法的计算精度与效率是令人满意的.     

Parameter and state estimation algorithm for single-input single-output linear systems using the canonical state space models

This paper presents a new parameter and state estimation algorithm for single-input single-output systems based on canonical state space models from the given input–output data. Difficulties of identification for state space models lie in that there exist unknown noise terms in the formation vector and unknown state variables. By means of the hierarchical identification principle, those noise terms in the information vector are replaced with the estimated residuals and a new least squares algorithm is proposed for parameter estimation and the system states are computed by using the estimated parameters. Finally, an example is provided.     

Feedback stabilization for perturbed linear systems *

In this paper, we consider the questions of stabilization of perturbed (or uncertain) linear systems in Hilbert space. Perturbations of the system operator represent the uncertainty in the modelling process and could be bounded or even unbounded. Sufficient conditions are presented that guarantee stabilizability of the perturbed system given that the nominal (unperturbed) system is stabilizable. In particular it is shown that for certain class of perturbations weak and strong stabilizability properties are preserved for the same state feedback control. Two numerical examples are given to illustrate our theory.