Virtual waiting times in priority-M/G/1 queues with vacations

In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting timeW _k(t) at timet of classk is derived by the method of collective marks. A sufficient condition for , whereU has the standard normal distribution, is also given.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

Optimal admission control in a queueing system with heterogeneous traffic

We consider optimal admission control of the GI/PH/1-type queueing system. The problem is then reduced to that of determining multi-threshold strategies. Some numerical examples are presented. The results have applications in the optimal input control of information flow in a computer communication network with heterogeneous traffic.     

Steady state analysis of an M/G/1 queue with two phase service and Bernoulli vacation schedule under multiple vacation policy

This paper examines the steady state behaviour of a batch arrival queue with two phases of heterogeneous service along and Bernoulli schedule vacation under multiple vacation policy, where after two successive phases service or first vacation the server may go for further vacations until it finds a new batch of customer in the system. We carry out an extensive stationary analysis of the system, including existence of stationary regime, queue size distribution of idle period process, embedded Markov chain steady state distribution of stationary queue size, busy period distribution along with some system characteristics.     

Asymptotic properties of nonlinear autoregressive Markov processes with state-dependent switching

In this paper, we consider a class of nonlinear autoregressive (AR) processes with state-dependent switching, which are two-component Markov processes. The state-dependent switching model is a nontrivial generalization of Markovian switching formulation and it includes the Markovian switching as a special case. We prove the Feller and strong Feller continuity by means of introducing auxiliary processes and making use of the Radon-Nikodym derivatives. Then, we investigate the geometric ergodicity by the Foster-Lyapunov inequality. Moreover, we establish the V-uniform ergodicity by means of introducing additional auxiliary processes and by virtue of constructing certain order-preserving couplings of the original as well as the auxiliary processes. In addition, illustrative examples are provided for demonstration.     

Level-crossing approach to a time-limited service system with two types of vacations

We consider an M^X/G/1 queue with nonpreemptive time-limited service and timer and exhaustive vacations. We analyze the waiting time distribution in this multiple vacation model by applying the level-crossing method to a workload process with two types of vacations.     

The equivalence of the transient behaviour formulae for the single server queue

It is indeed obvious to expect that the different results obtained for some problem are equal, but it needs to established. For the M/M/1/N queue, using a simple algebraic approach we will prove that the results obtained by Takâcs [17] Takâcs, L. 1960. Introduction to the Theory of Queues Oxford University Press.  [Google Scholar] and Sharma and Gupta [13] Sharma, O.P. and Gupta, U.C. 1982. Transient Behaviour of an M/M/l/N Queue. Stoch. Process Appl., 13: 327–331. [Crossref] , [Google Scholar] are equal. Furthermore, a direct proof to the equivalence between all formulae of the M/M/l/∞ queue is established. At the end of this paper, we will show that the time-dependent state probabilities for M/M/l/N queue can be written in series form; its coefficients satisfy simple recurrence relations which would allow for the rapid and efficient evaluation of the state probabilities. Moreover, a brief comparison of our technique, Sharma and Gupta's formula and Takâcs result is also given, for the CPU time computing the state probabilities.     

Iterative methods for overflow queueing models I

Summary Markovian queueing networks having overflow capacity are discussed. The Kolmogorov balance equations result in a linear homogeneous system, where the right null-vector is the steady-state probability distribution for the network. Preconditioned conjugate gradient methods are employed to find the null-vector. The preconditioner is a singular matrix which can be handled by separation of variables. The resulting preconditioned system is nonsingular. Numerical results show that the number of iterations required for convergence is roughly constant independent of the queue sizes. Analytic results are given to explain this fast convergence.     

Stability of solutions for a class of nonlinear cone constrained optimization problems,part 2: Application to parameter estimation

In this paper we study a problem of parameter estimation in two point boundary value problems. Using a stability theorem for nonlinear cone constrained optimization problems derived in Part 1 of this paper we investigate stability properties of the solutions of the parameter estimation problem in the output-least-squares formulation.     

Regenerative simulation of TES processes

Regenerative simulation has become a familiar and established tool for simulation-based estimation. However, many applications (e.g., traffic in high-speed communications networks) call for autocorrelated stochastic models to which traditional regenerative theory is not directly applicable. Consequently, extensions of regenerative simulation to dependent time series is increasingly gaining in theoretical and practical interest, with Markov chains constituting an important case. Fortunately, a regenerative structure can be identified in Harris-recurrent Markov chains with minor modification, and this structure can be exploited for standard regenerative estimation. In this paper we focus on a versatile class of Harris-recurrent Markov chains, called TES (Transform-Expand-Sample). TES processes can generate a variety of sample paths with arbitrary marginal distributions, and autocorrelation functions with a variety of functional forms (monotone, oscillating and alternating). A practical advantage of TES processes is that they can simultaneously capture the first and second order statistics of empirical sample paths (raw field measurements). Specifically, the TES modeling methodology can simultaneously match the empirical marginal distribution (histogram), as well as approximate the empirical autocorrelation function. We explicitly identify regenerative structures in TES processes and proceed to address efficiency and accuracy issues of prospective simulations. To show the efficacy of our approach, we report on a TES/M/1 case study. In this study, we used the likelihood ratio method to calculate the mean waiting time performance as a function of the regenerative structure and the intrinsic TES parameter controlling burstiness (degree of autocorrelation) in the arrival process. The score function method was used to estimate the corresponding sensitivity (gradient) with respect to the service rate. Finally, we demonstrated the importance of the particular regenerative structure selected in regard to the estimation efficiency and accuracy induced by the regeneration cycle length.     

Heavy-traffic asymptotics for the single-server queue with random order of service

We consider the GI/GI/1 queue with customers served in random order, and derive the heavy-traffic limit of the waiting-time distribution. Our proof is probabilistic, requires no finite-variance assumptions, and makes the intuition provided by Kingman (Math. Oper. Res. 7 (1982) 262) rigorous.     

An implicit finite difference scheme for the nonlinear size-structured population model

In this paper we consider the "fully nonlinear" size structured population model. We develop an implicit finite difference scheme to approximate the solution of this nonlinear partial differential equation. The convergence of this approximation to a unique bounded variation solution of this model is obtained. Numerical results to an example problem are presented.     

Asymptotic behaviour of a phase-field model with three coupled equations without uniqueness

We prove the existence of weak solutions for a phase-field model with three coupled equations with unknown uniqueness, and state several dynamical systems depending on the regularity of the initial data. Then, the existence of families of global attractors (level-set depending) for the corresponding multi-valued semiflows is established, applying an energy method. Finally, using the regularizing effect of the problem, we prove that these attractors are in fact the same.     

Queueing systems on a circle

Consider a ring on which customers arrive according to a Poisson process. Arriving customers drop somewhere on the circle and wait there for a server who travels on the ring. Whenever this server encounters a customer, he stops and serves the customer according to an arbitrary service time distribution. After the service is completed, the server removes the client from the circle and resumes his journey.We are interested in the number and the locations of customers that are waiting for service. These locations are modeled as random counting measures on the circle. Two different types of servers are considered: The polling server and the Brownian (or drunken) server. It is shown that under both server motions the system is stable if the traffic intensity is less than 1. Furthermore, several earlier results on the configuration of waiting customers are extended, by combining results from random measure theory, stochastic integration and renewal theory.