A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

A fluid system with coupled input and output,and its application to bottlenecks in ad hoc networks

This paper studies a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when n flows are present, each of them transmits traffic into the queue at a rate c/(n+1), where the remaining c/(n+1) is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy. We consider four performance metrics: (i) the stationary workload of the queue, (ii) the queueing delay, i.e., the delay of a ‘packet’ (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii) the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv) the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis. F. Roijers’ work has been carried out partly in the SENTER-NOVEM funded project Easy Wireless.     

Fluid queues with synchronized output

We present a model of parallel Lévy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.     

A stochastic system with MMPP input and an access function

In classical studies of loss systems with restricted availability, the utilization was suggested of a probabilistic loss function, defining the conditional probability of an incoming call being rejected, as a function of the number of occupations in the destination group of servers. This paper gives an exact analysis of stochastic processes of practical relevance, associated with a system with MMPP (Markov Modulated Poisson Process) input, finite queueing capacity and a general loss function, assuming exponential service times. In addition to the process defining the state of the system at any instant, the analysis of the overflow point process (associated with the rejected arriving customers), the accepted point process (associated with the accepted arriving customers), and of the departure process will be presented. Together with the exact analysis of this system, based on the matrix analytical methodology of Neuts, (1981), we will derive expressions for calculating some key-parameters of pertinent associated processes, which may also be used for their approximate modelling. Also, examples of applications and of blocking probability calculations in specific models of this class will be presented.     

On the output process of an M/M/1 queue with randomly varying system parameters

In this paper an analysis of the output process from an M/M/1 queue where the arrival and service rates vary randomly is presented. The results include expressions for the mean, variance and distribution of the interdeparture interval, the joint density function of two successive interdeparture intervals and their correlation. An interesting feature of the results is that the moments of the interdeparture time are expressed in terms of the expected times to first and second departures from an arbitrary point in time.     

Analysis at service completion times of buffers with output interruptions

In an earlier paper [Bruneel, 1983a]we investigated a discrete-time buffer system with infinite waiting room and one single output channel, subjected to stochastic interruptions. For this system, the probability generating function of the number of messages in the buffer at service completion times was derived, under rather general assumptions concerning the arrival process and the server interruption process. However, at a certain point in the analysis, we tacitly introduced an approximation, by neglecting the (statistical) information available on the first customer of a busy period.In the present paper we show that this simplifying assumption is not really necessary in order to keep the problem analytically tractable, and the exact (but rather tedious) derivations are given. As a result, an expression is found for the probability generating function of the buffer contents, which is even less complicated than the one obtained in the previous paper.The results of the two studies are compared and are found to be substantially different from each other for realistic values of the parameters of the system.

---

Zusammenfassung In einer früheren Arbeit [Bruneel, 1983a] wurde ein Puffersystem in diskreter Zeit mit einem unbeschränkten Speicherraum und einem zufälligen Unterbrechungen ausgesetzten Ausgabekanal untersucht. Für dieses System wurde die erzeugende Funktion der Anzahl der Aufträge im Puffer zu den Zeitpunkten der Abfertigung eines Auftrags berechnet, wobei recht allgemeine Annahmen über den Ankunftstrom und den Prozeß der Bedienungs-Unterbrechungen zugrundelagen. Dabei wurde auch implizit eine Approximation benutzt, indem (statistische) Information über den ersten Kunden einer Arbeitsperiode nicht berücksichtigt wurde.In der vorliegenden Arbeit wird nun gezeigt, daß mit beträchtlichem Mehraufwand die Analyse auch ohne diese Approximation durchführbar ist.Der resultierende Ausdruck für die erzeugende Funktion des Pufferinhalts ist sogar einfacher. Ein Vergleich zeigt, daß die neuen Ergebnisse bei realistischer Parameterwahl von den früher erzielten beträchtlich abweichen.

     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

A generalized inefficiency model with input and output dependence

In this paper we propose a general inefficiency model, in the sense that technical inefficiency is, simultaneously, a function of all inputs, outputs, and contextual variables. We recognize that change in inefficiency is endogenous or rational, and we propose an adjustment costs model with firm-specific but unknown adjustment cost parameters. When inefficiency depends on inputs and outputs, the firm's optimization problem changes as the first order conditions must take into account the dependence of inefficiency on the endogenous variables of the problem. The new formulation introduces statistical challenges which are successfully resolved. The model is estimated using Maximum Simulated Likelihood and an empirical application to U.S. banking is provided.     

Two parallel insurance lines with simultaneous arrivals and risks correlated with inter-arrival times

We investigate an insurance risk model that consists of two reserves which receive income at fixed rates. Claims are being requested at random epochs from each reserve and the interclaim times are generally distributed. The two reserves are coupled in the sense that at a claim arrival epoch, claims are being requested from both reserves and the amounts requested are correlated. In addition, the claim amounts are correlated with the time elapsed since the previous claim arrival.We focus on the probability that this bivariate reserve process survives indefinitely. The infinite-horizon survival problem is shown to be related to the problem of determining the equilibrium distribution of a random walk with vector-valued increments with ‘reflecting’ boundary. This reflected random walk is actually the waiting time process in a queueing system dual to the bivariate ruin process.Under assumptions on the arrival process and the claim amounts, and using Wiener–Hopf factorization with one parameter, we explicitly determine the Laplace–Stieltjes transform of the survival function, c.q., the two-dimensional equilibrium waiting time distribution.Finally, the bivariate transforms are evaluated for some examples, including for proportional reinsurance, and the bivariate ruin functions are numerically calculated using an efficient inversion scheme.     

Estimating variance of output from cyclic exponential queueing systems

Production systems, particularly those making use of a pull production control mechanism, are well-modeled as closed queueing networks. Average throughput is clearly one important performance measure for these systems. However, many control decisions require information concerning the variability of the output process as well as throughput. Because of this, the standard deviation of the number of outputs during a specified interval is a practical performance measure for production systems.In this paper, we consider the standard deviation of the number of outputs during a time interval from a closed queueing network consisting ofM single server exponential queues. Because computing this quantity exactly is extremely cumbersome, we introduce a simple approximation that makes use of (1) known results for the variance of the time a marked job takes to complete a round trip and (2) an approximate correction term for the covariance between successive round trips. We show through comparisons with simulation that our method is quite accurate under a variety of conditions.     

相关噪声下多步无序量测状态估计更新算法

在多传感器系统中,由于通信时间的延迟性,常常会出现无序量测情况.为了提高估计精度,系统须对无序量测进行更新估计.状态估计更新算法是处理无序量测问题的一种有效方法.在过程噪声和量测噪声相关条件下,给出了含无序量测的传感器系统状态估计更新算法.仿真计算验证了该算法的有效性.     

Optimal control of a queueing system with an exponential and an Erlangian server and renewal input stream

Customers arrive in a renewal process at a queue which is served by an exponential and a two-stage Erlangian server. We prove the optimal policy for assignment of customers to the servers which for any t maximizes the expected number of served customers in [0,t].     

A second-order fluid queue with subordinator input and Markov-modulated linear output

We consider an infinite capacity second-order fluid queue with subordinator input and Markovmodulated linear release rate. The fluid queue level is described by a generalized Langevin stochastic differential equation （SDE）. Applying infinitesimal generator, we obtain the stationary distribution that satisfies an integro-differential equation. We derive the solution of the SDE and study the transient level＇s convergence in distribution. When the coefficients of the SDE are constants, we deduce the system transient property.     

Maximally productive input–output units

Technical or Pareto–Koopmans efficiency models can be based on ratios of weighted sums of outputs to weighted sums of inputs. Differing meanings have been considered for such factor weights. In this paper, we use value or cost rate meanings depending on model orientation. These meanings permit considering the simultaneous assignment of input and output factor weights along with optimal intensity values for a virtual composite unit constructed from the observed units. An optimization principle we call the winners-take-all criterion is proposed for determining the maximally productive unit(s). No assumptions are required on the internal transformation processes of the units. The model simultaneously determines the intensities and factor weights and results in indefinite quadratic programming problems that simplify to linear programming in certain cases. For the general case, genetic search is applied. Numerical illustrations are provided for faculty merit scoring and for the 15 hospital dataset of Sherman.     

A new chance-constrained DEA model with birandom input and output data

The purpose of conventional Data Envelopment Analysis (DEA) is to evaluate the performance of a set of firms or Decision-Making Units using deterministic input and output data. However, the input and output data in the real-life performance evaluation problems are often stochastic. The stochastic input and output data in DEA can be represented with random variables. Several methods have been proposed to deal with the random input and output data in DEA. In this paper, we propose a new chance-constrained DEA model with birandom input and output data. A super-efficiency model with birandom constraints is formulated and a non-linear deterministic equivalent model is obtained to solve the super-efficiency model. The non-linear model is converted into a model with quadratic constraints to solve the non-linear deterministic model. Furthermore, a sensitivity analysis is performed to assess the robustness of the proposed super-efficiency model. Finally, two numerical examples are presented to demonstrate the applicability of the proposed chance-constrained DEA model and sensitivity analysis.     

A mathematical model for discrete-time buffer systems with correlated output process

This article considers an infinite buffer system with one or more input channels and multiple output channels. Transmission of messages from the buffer is synchronous and the arrival process of messages to the buffer is general. Each of the output channels is subjected to a random interruption process, i.e., the number of available output channels varies in time and is stochastic. The analysis of this system is carried out under the assumption that the output process can be described as a first order Markov process, i.e., the probability distribution of the number of available output channels during some clock time interval depends only on the number of available output channels during the previous clock time interval.A set of equations describing the behavior of this buffer system is derived. For a number of interesting special cases this set is solved and explicit expressions are obtained for the probability generating function of the number of messages in the buffer. Several prior studies are found as special cases of the present one. An illustrative example is treated and the results are compared to the ones obtained for an uncorrelated output process with the same equilibrium distribution. Some considerable deviations from these results are found.     

Dynamic output guaranteed cost controller for neutral systems with input delay

In this paper, we consider a design problem of dynamic output guaranteed cost controller (GCC) of a class of neutral systems with input delay. A quadratic cost function is considered as a performance measure for the closed-loop system. Based on the Lyapunov second method, two stability criteria for existence of the controller are derived in terms of matrix inequalities. The solutions of the matrix inequalities can be easily obtained using existing efficient convex optimization techniques. A numerical example is given to illustrate the proposed design method.     

The input to and output from risk evaluation models

The work which has been done on analytic approaches to the evaluation of the risk in major capital investment opportunities suggests the following hypotheses: (a) The distributions of NPV and IRR which are output from risk evaluation models are often approximately normal. (b) The only important features of the distributions of the variables which are input to risk evaluation models are their means and standard deviations. The research which is described in this paper tests these hypotheses using five risk simulation case studies.     

Regular linear systems governed by systems with state, input and output delays

^** Email: hadd{at}ucam.ac.ma^*** Email: idrissi{at}ucam.ac.ma In this paper, we give a new reformulation of linear systemswith delays in input, state and output. We show that these systemscan be written as a regular linear system without delays. Thetechnique used here is essentially based on the theory recentlydeveloped by Salamon and Weiss and the shift in semigroup properties.Our framework can be applied, in particular, when the delayoperators are given by Riemann–Stieltjes integrals.     

Exact analysis of asymmetric random polling systems with single buffers and correlated input process

We introduce a simple approach for modeling and analyzing asymmetric random polling systems with single buffers and correlated input process. We consider two variations of single buffers system: the conventional system and the buffer relaxation system. In the conventional system, at most one customer may be resided in any queue at any time. In the buffer relaxation system, a buffer becomes available to new customers as soon as the current customer is being served. Previous studies concentrate on conventional single buffer system with independent Poisson process input process. It has been shown that the asymmetric system requires the solution ofm 2 ^m –1) linear equations; and the symmetric system requires the solution of 2 ^m–1–1 linear equations, wherem is the number of stations in the system. For both the conventional system and the buffer relaxation system, we give the exact solution to the more general case and show that our analysis requires the solution of 2 ^m –1 linear equations. For the symmetric case, we obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, loss probability, throughput, and the expected delay observed by a customer.