On some relations between stationary time and customer state probabilities for qneueing systems G/GI/s/r

By means of a general formula for stochastic processes with imbedded marked point processes (PMP) some necessary and sufficient condition is given for the validity of a relationship, which is well-known in the case of exponentially distributed service times, between stationary time and customer state probabilities for loss systems G/GI/s/O (Theorem 3). A result of Miyazawa for the GI/GI/l/∞ queue is generalized to the case of non-recurrent interarrival times (Theorem 4)-. Furthermore, bounds are derived for the mean increment of the waiting time process at arrival epochs and for the mean actual waiting time in multi-server queues.     

Stochastic cyclic flow lines: non-blocking,Markovian models

In this paper we consider stochastic cyclic flow lines where identical sets of jobs are repeatedly produced in the same loading and processing sequence. Each machine has an input buffer with enough capacity. Processing times are stochastic. We model the shop as a stochastic event graph, a class of Petri nets. We characterise the ergodicity condition and the cycle time. For the case where processing times are exponentially distributed, we present a way of computing queue length distributions. For two-machine cases, by the matrix geometric method, we compute the exact queue length distributions. For general cases, we present two methods for approximately decomposing the line model into two-machine submodels, one based on starvation propagation and the other based on transition enabling probability propagation. We experiment our approximate methods for various stochastic cyclic flow lines and discuss performance characteristics as well as accuracy of the approximate methods. Finally, we discuss the effects of job processing sequences of stochastic cyclic flow lines.     

Stochastic stability of positive Markov jump linear systems with fixed dwell time

This paper studies the stochastic stability of positive Markov jump linear systems with a fixed dwell time. By constructing an auxiliary system that originated from the initial system with state jumps, sufficient and necessary conditions of stochastic stability for positive Markov jump linear systems are obtained with both exactly known and partially known transition rates. The main idea in the latter case is applying a convex combination to convert bilinear programming into linear programming problems. On this basis, multiple piecewise linear co-positive Lyapunov functions are provided to achieve less conservative results. Then state feedback controller is designed to stabilize the positive Markov jump linear systems by solving linear programming problems. Numerical examples are presented to illustrate the viability of our conclusions.     

Estimating the cycle time of three-stage material handling systems

Because of high investment costs, the productivity of material handling systems must be accurately estimated before various logistical, industrial, or transportation systems can be implemented. This paper proposes analytical models for three-stage material handling systems. Two possible approaches to the estimation of the productivity of three-stage material handling systems are considered: one, the continuous Markov chain model, and two, approximated mathematical models. The approximated models are based on the probability theory and permit very accurate calculations of the compound cycle time in cases when the probability distribution of the “technical” cycle times of each stage is known. Finally, some numerical results obtained by the proposed models are compared with those results obtained by a simulation study.     

An exact minimum variance filter for a class of discrete time systems with random parameter perturbations

An exact, closed-form minimum variance filter is designed for a class of discrete time uncertain systems which allows for both multiplicative and additive noise sources. The multiplicative noise model includes a popular class of models (Cox-Ingersoll-Ross type models) in econometrics. The parameters of the system under consideration which describe the state transition are assumed to be subject to stochastic uncertainties. The problem addressed is the design of a filter that minimizes the trace of the estimation error variance. Sensitivity of the new filter to the size of parameter uncertainty, in terms of the variance of parameter perturbations, is also considered. We refer to the new filter as the ‘perturbed Kalman filter’ (PKF) since it reduces to the traditional (or unperturbed) Kalman filter as the size of stochastic perturbation approaches zero. We also consider a related approximate filtering heuristic for univariate time series and we refer to filter based on this heuristic as approximate perturbed Kalman filter (APKF). We test the performance of our new filters on three simulated numerical examples and compare the results with unperturbed Kalman filter that ignores the uncertainty in the transition equation. Through numerical examples, PKF and APKF are shown to outperform the traditional (or unperturbed) Kalman filter in terms of the size of the estimation error when stochastic uncertainties are present, even when the size of stochastic uncertainty is inaccurately identified.     

Finite-time synchronization for coupled systems with time delay and stochastic disturbance under feedback control

This paper proposes a framework for finite-time synchronization of coupled systems with time delay and stochastic disturbance under feedback control. Combining Kirchhoff"s Matrix Tree Theorem with Lyapunov method as well as stochastic analysis techniques, several sufficient conditions are derived. Differing from previous references, the finite time provided by us is related to topological structure of networks. In addition, two concrete applications about stochastic coupled oscillators with time delay and stochastic Lorenz chaotic coupled systems with time delay are presented, respectively. Besides, two synchronization criteria are provided. Ultimately, two numerical examples are given to illustrate the effectiveness and feasibility of the obtained results.     

The long time behavior for partly dissipative stochastic systems

In this paper, we consider the long time behaviors for the partly dissipative stochastic reaction diffusion equations in \(D\in\mathbb{R}^n\). The main purpose of thie paper is to establish the existence of a compact global random attractor. The existence of a random absorbing set is first discussed for the systems and then an estimate on the solutions is derived when the time is large enough, which ensures the asymptotic compactness of solutions. Finally, establish the existence of the global attractor in \(L^2(D)\times L^2(D)\).     

A continuity theorem and some counterexamples for the theory of maintained systems

The reliability of maintained systems is considered. A “continuity theorem” is presented which states that the stochastic behavior of a maintained system depends continuously on the stochastic behavior of its components. Examples of maintained systems with IFR component lifetimes and exponential repair times are presented for which time until first system failure is not NBU.     

The impact of stochastic lead time reduction on inventory cost under order crossover

We use exponential lead times to demonstrate that reducing mean lead time has a secondary reduction of the variance due to order crossover. The net effect is that of reducing the inventory cost, and if the reduction in inventory cost overrides the investment in lead time reduction, then the lead time reduction strategy would be tenable.We define lead time reduction as the process of decreasing lead time at an increased cost. To date, decreasing lead times has been confined to deterministic instances. We examine the case where lead times are exponential, for when lead times are stochastic, deliveries are subject to order crossover, so that we must consider effective lead times rather than the actual lead times. The result is that the variance of these lead times is less than the variance of the original replenishment lead times.Here we present a two-stage procedure for reducing the mean and variance for exponentially distributed lead times. We assume that the lead time is made of one or several components and is the time between when the need of a replenishment order is determined to the time of receipt.     

Stability,monotonicity and invariant quantities in general polling systems

Consider a polling system withK1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.     

Expected waiting time in symmetric polling systems with correlated walking times

Polling systems have been extensively studied, and have found many applications. They have often been used for studying wired local area networks such as token passing rings and wireless local area networks such as bluetooth. In this contribution we relax one of the main restrictions on the statistical assumptions under which polling systems have been analyzed. Namely, we allow correlation between walking times. We consider (i) the gated regime where a gate closes whenever the server arrives at a queue. It then serves at that queue all customers who were present when the gate closes. (ii) The exhaustive regime in which the server remains at a queue till it empties. Our analysis is based on stochastic recursive equations related to branching processes with migration with a random environment. In addition to our derivation of expected waiting times for polling systems with correlated walking times, we set the foundations for computing second order statistics of the general multi-dimensional stochastic recursions.      

Determining the optimal run time for EPQ model with scrap,rework, and stochastic breakdowns

This paper is concerned with determination of optimal run time for an economic production quantity (EPQ) model with scrap, rework, and stochastic machine breakdowns. In real life manufacturing systems, generation of defective items and random breakdown of production equipment are inevitable. In this study, a portion of the defective items is considered to be scrap, while the other is assumed to be repairable. Total production-inventory cost functions are derived respectively for both EPQ models with breakdown (no-resumption policy is adopted) and without breakdown taking place. These cost functions are integrated and the renewal reward theorem is used to cope with the variable cycle length. Theorems on conditional convexity of the integrated overall costs and bounds of the production run time are proposed and proved. We conclude that the optimal run time falls within the range of bounds and it can be pinpointed by the use of the bisection method based on the intermediate value theorem. Numerical example is provided to demonstrate its practical usages.     

From Polling to Snowplowing

We study the limiting behavior of gated polling systems, as their dimension (the number of queues) tends to infinity, while the system's total incoming workflow and total switchover time (per cycle) remain unchanged. The polling systems are assumed asymmetric, with incoming workflow obeying general Lévy statistics, and with general inter-dependent switchover times. We prove convergence, in law, to a limiting polling system on the circle. The derivation is based on an asymptotic analysis of the stochastic Poincaré maps of the polling systems. The obtained polling limit is identified as a snowplowing system on the circle—whose evolution, steady-state equilibrium, and statistics have been recently investigated and are known.     

Generalized average dwell time approach to stability and input-to-state stability of hybrid impulsive stochastic differential systems

This paper is concerned with the stability properties of a class of impulsive stochastic differential systems with Markovian switching. Employing the generalized average dwell time (gADT) approach, some criteria on the global asymptotic stability in probability and the stochastic input-to-state stability of the systems under consideration are established. Two numerical examples are given to illustrate the effectiveness of the theoretical results, as well as the effects of the impulses and the Markovian switching on the systems stability.     

Exponential stabilization of stochastic interval system with time dependent parameters

There has been growing interest in analyzing stability in design controls of stochastic systems. This interest arises out of the need to develop robust control strategies for systems with uncertain dynamics. This paper is concerned with the examination of conditions under which the desired structure of a stochastic interval system with time dependent parameters is stabilizable. Necessary and sufficient condition under which two-level preconditioner guarantees quadratic mean exponential stability of the desired structure of uncontrolled stochastic interval system is presented. Sufficient condition for exponential stability of the equilibrium solution of uncontrolled stochastic interval system is also presented.     

Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms

Run time distributions or time-to-target plots are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. We further explore run time distributions and describe a new tool to compare two algorithms based on stochastic local search. For the case where the running times of both algorithms fit exponential distributions, we derive a closed form index that gives the probability that one of them finds a solution at least as good as a given target value in a smaller computation time than the other. This result is extended to the case of general run time distributions and a numerical iterative procedure is described for the computation of the above probability value. Numerical examples illustrate the application of this tool in the comparison of different sequential and parallel algorithms for a number of distinct problems.     

Optimal estimation of parameters and states in stochastic time-varying systems with time delay

In this study estimation of parameters and states in stochastic linear and nonlinear delay differential systems with time-varying coefficients and constant delay is explored. The approach consists of first employing a continuous time approximation to approximate the stochastic delay differential equation with a set of stochastic ordinary differential equations. Then the problem of parameter estimation in the resulting stochastic differential system is represented as an optimal filtering problem using a state augmentation technique. By adapting the extended Kalman–Bucy filter to the resulting system, the unknown parameters of the time-delayed system are estimated from noise-corrupted, possibly incomplete measurements of the states.     

On the Hamiltonicity Gap and doubly stochastic matrices

We consider the Hamiltonian cycle problem embedded in singularly perturbed (controlled) Markov chains. We also consider a functional on the space of stationary policies of the process that consists of the (1,1)‐entry of the fundamental matrices of the Markov chains induced by these policies. We focus on the subset of these policies that induce doubly stochastic probability transition matrices which we refer to as the “doubly stochastic policies.” We show that when the perturbation parameter, ε, is sufficiently small, the minimum of this functional over the space of the doubly stochastic policies is attained at a Hamiltonian cycle, provided that the graph is Hamiltonian. We also show that when the graph is non‐Hamiltonian, the above minimum is strictly greater than that in a Hamiltonian case. We call the size of this difference the “Hamiltonicity Gap” and derive a conservative lower bound for this gap. Our results imply that the Hamiltonian cycle problem is equivalent to the problem of minimizing the variance of the first hitting time of the home node, over doubly stochastic policies. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Unreliable M/G/1 retrial queue: monotonicity and comparability

In this paper we investigate the monotonicity properties of an unreliable M/G/1 retrial queue using the general theory of stochastic ordering. We show the monotonicity of the transition operator of the embedded Markov chain relative to the strong stochastic ordering and increasing convex ordering. We obtain conditions of comparability of two transition operators and we obtain comparability conditions of the number of customers in the system. Inequalities are derived for the mean characteristics of the busy period, number of customers served during a busy period, number of orbit busy periods and waiting times. Inequalities are also obtained for some probabilities of the steady-state distribution of the server state. An illustrative numerical example is presented.     

Modelling and evaluation of time aspects in business processes

There is a need for modelling and performance evaluation techniques and tools for a fast and reliable design of workflow systems. This paper introduces a modelling methodology based on coloured stochastic Petri nets. It allows the integration of control flow, organizational, information related and timing aspects in one modelling framework. The processing delays include stochastic distributions in addition to deterministic times. Several workflows and the effects of constrained shared resources needed for different tasks can easily be described and analysed together. Control flow and organizational aspects are modelled separately in resource and workflow models. These models are automatically compiled into one model, which can then be used for qualitative analysis or performance evaluation. The proposed modelling and evaluation method is supported by the software tool TimeNET. An application example shows its use.