On the behavior of the batch arrival queue Mx/M/1 during a busy period

The queue size process (^t)⁰≤^t≤^t0 of the batch arrival queue M^X/M/1 is studied under the condition that the duration of its busy period is larger than t⁰. Explicit formulas for the transition probabilities are given and the limiting Markov process for t⁰ → ∞ is investigated. Several properties of this process are considered. Its transition probabilities and moments and the distribution of its minimum are derived and a functional limit theorem for the rescaled process is proved. © 1994 John Wiley & Sons, Inc.     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

Arrival and departure state distributions in the general bulk‐service queue

In this paper, we give an explicit relation between steady‐state probability distributions of the buffer occupancy at customer entrance and departure epochs, for the classical single‐server system G/G^[N]/1 with batch services and for the finite capacity case. The method relies on level‐crossing arguments. For the particular case of Poisson input, we also express the loss probability in terms of state probabilities at departure epochs, yielding probabilities observed by arriving customers. This work provides the “bulk queue” version of a result established by Burke, who stated the equality between probabilities at arrival and departure epochs for systems with “unit jumps.” © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 107–118, 1999     

On the (S-1, S) inventory model under compound poisson demands and i.i.d. unit resupply times

We analyze an (S-1, S) inventory model with compound Poisson demands. Resupply times for individual units are independent and identically distributed. Such a model can also be characterized as an M^X/G/∞ queue. We derive expressions of performance measure such as the steady-state distribution and the expectation of the number of backlogged units. In addition, numerical examples are included to reflect the effects of i.i.d. unit resupply times. © 1996 John Wiley & Sons, Inc.     

The queueing system MX/G/1 and its ramifications

This paper deals with the bulk arrival queueing system M^X/G/1 and its ramifications. In the system M^X/G/1, customers arrive in groups of size X (a random variable) by a Poisson process, the service times distribution is general, and there is a single server. Although some results for this queueing system have appeared in various books, no unified account of these, as is being presented here, appears to have been reported so far. The chief objectives of the paper are (i) to unify by an elegant procedure the relationships between the p.g.f.'s

     

On queueing systems with variable service capacities

In some queueing systems the total service capacity utilized at any given time is a variable under the control of a decision maker. Management doctrines are examined which prescribe the actual service capacity as a function of the queue length and the recent history of the system. Steady state probabilities, expected queue lengths and frequencies of change in capacity are evaluated for a wide class of possible control schemes. Optimization procedures are outlined.     

A solution for queues with instantaneous jockeying and other customer selection rules

This paper presents a general solution for the M/M/r queue with instantaneous jockeying and r > 1 servers. The solution is obtained in matrices in closed form without recourse to the generating function arguments usually used. The solution requires the inversion of two (Z^r?1) × (2^r?1) matrices. The method proposed is extended to allow different queue selection preferences of arriving customers, balking of arrivals, jockeying preference rules, and queue dependent selection along with jockeying. To illustrate the results, a problem previously published is studied to show how known results are obtained from the proposed general solution.     

Optimal admission pricing and service rate control of an M[x]/M/s queue with reneging

In this article we consider the optimal control of an M^[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes.     

Sojourn time analysis of a queueing system with two‐phase service and server vacations

We consider a two‐phase service queueing system with batch Poisson arrivals and server vacations denoted by M^X/G₁‐G₂/1. The first phase service is an exhaustive or a gated bulk service, and the second phase is given individually to the members of a batch. By a reduction to an M^X/G/1 vacation system and applying the level‐crossing method to a workload process with two types of vacations, we obtain the Laplace–Stieltjes transform of the sojourn time distribution in the M^X/G₁‐G₂/1 with single or multiple vacations. The decomposition expression is derived for the Laplace–Stieltjes transform of the sojourn time distribution, and the first two moments of the sojourn time are provided. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

Markov chain analyses of multiprogrammed computer systems

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time-shared processing systems. In particular, Markov queueing models are defined and analyzed for round-robin and foreground-background service disciplines. With the round-robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground-background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set-up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.     

Exact expected values of variance estimators for simulation

We formulate exact expressions for the expected values of selected estimators of the variance parameter (that is, the sum of covariances at all lags) of a steady‐state simulation output process. Given in terms of the autocovariance function of the process, these expressions are derived for variance estimators based on the simulation analysis methods of nonoverlapping batch means, overlapping batch means, and standardized time series. Comparing estimator performance in a first‐order autoregressive process and the M/M/1 queue‐waiting‐time process, we find that certain standardized time series estimators outperform their competitors as the sample size becomes large. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Waiting time analysis of the M/G/1 queue with finite retrial group

We consider an M/G/1 retrial queue with finite capacity of the retrial group. First, we obtain equations governing the dynamic of the waiting time. Then, we focus on the numerical inversion of the density function and the computation of moments. These results are used to approximate the waiting time of the M/G/1 queue with infinite retrial group for which direct analysis seems intractable. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Inequalities involving the lifetime of series and parallel systems

Let {Xⁱ} be independent HNBUE (Harmonic New Better Than Used in Expectation) random variables and let {Yⁱ} be independent exponential random variables such that E{Xⁱ}=E{Yⁱ} It is shown that \documentclass{article}\pagestyle{empty}\begin{document}$ E\left[{u\left({\mathop {\min \,X_i}\limits_{l \le i \le n}} \right)} \right] \ge E\left[{u\left({\mathop {\min \,Y_i}\limits_{l \le i \le n}} \right)} \right] $\end{document} for all increasing and concave u. This generalizes a result of Kubat. When comparing two series systems with components of equal cost, one with lifetimes {Xⁱ} and the other with lifetimes {Yⁱ}, it is shown that a risk-averse decision-maker will prefer the HNBUE system. Similar results are obtained for parallel systems.     

混合排队规则的战术装备维修保障系统分析

首先将战术装备维修保障过程描述为M/M/c/k混合规则的排队过程,其损坏装备到达服从相互独立的泊松分布,维修时间服从相互独立的指数分布。同时考虑系统的到达率和维修率随系统中装备数量的变化,重要战损装备等待维修时的不耐烦性以及重要装备对一般装备的强占性优先权情况,结合战术装备维修保障系统的结构和规模,建立战术装备维修保障M/M/3/12排队模型。列出模型的平衡方程,采用矩阵的分析方法得到重要装备和一般装备的稳态分布表达式,并以队长为指标进行了系统性能的计算。     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

A queuing process with bilevel hysteretic service-rate control

The purpose of this paper is to analyze the effect of a particular control doctrine applied to the service mechanism of a queuing process. A bilevel hysteretic control based on queue length control levels is employed in an M/M/1 queuing system. Expressions are obtained for queue length probabilities, the first two factorial moments of queue length and two figures of merit for describing control performance under the assumption of statistical equilibrium. Computational examples illustrate the effects on queuing processes subject to this type of control. Several cost formulae are considered for comparison of costs when the queue control doctrine is varied. Situations in which hysteretic control is useful are discussed.     

The single server queue in discrete time-numerical analysis IV

The nonlinear difference equation for the distribution of the busy period for an unbounded discrete time queue of M|G| 1 type is solved numerically by a monotone iterative procedure. A starting solution is found by computing a first passage time distribution in a truncated version of the queue.